Prevod KA -> RV

Question

0

Prevod KA -> RV

BI-AAG
BI

asked 2014-11-15 11:33:54 +0100

Anonymous

updated 2014-11-15 13:05:11 +0100

Anonymous

Ahojte, nevedel by mi niekto poradit, ako previest konecny automat na regularny vyraz? Konkretne mam problem s ulohou 6 z tohto testu https://www.fit-wiki.cz/škola/předměty/bi-aag/aag_test_2013-11-20_1100v2 snazim sa z tej tabulky dostat nejaku schopnu gramatiku a potom z nej vyskrtat nedosiahnutelne stavy, a nasledne to vyriesit cez rovnice, ale nejak sa mi nedari, a neviem, ci ten postup je prave spravny. Najvacsi problem mam to asi previest na gramatiku, kde som si nie isty, ci to robim spravne. Dakujem pekne za rady.

edit retag flag offensive close delete

Accepted Answer

2

answered 2014-11-15 13:19:05 +0100

Viktor Chlumský
765 ●14 ●24

updated 2014-11-15 13:20:04 +0100

Ano, jeden možný postup je převést automat nejprve na gramatiku, což bych řek, že je poměrně jednoduché, stačí v podstatě přepsat tabulku do tvaru gramatiky:

S -> 0S|1C|2E
A -> 0A|2A
B -> 0B|1D|2A|ε
C -> 0C|1E|2B
D -> 0D|1A
E -> 0E|1B|2D

Jediné, na co se nesmí zapomenout je, že do koncových stavů (B) se přidá ε pravidlo.

Aby to byla regulární gramatika, bylo by potřeba zbavit se ε-pravidel, ale to v tomhle případě není potřeba, protože ji rovnou převedeme na regulární rovnice, kde to nevadí:

S = 0S+1C+2E
A = 0A+2A
B = 0B+1D+2A+ε
C = 0C+1E+2B
D = 0D+1A
E = 0E+1B+2D

Ono už na začátku lze zjistit, že stavy A a D jsou takzvaně zbytečné, ale ukáže se to i tím, že v rovnicích vyjde A = Ø, D = Ø. Celé mi to vyšlo takto:

S = 0*(10*(10*10*+20*)+20*10*)

Ale neručím, že je to správně, protože jsem to dělal dost narychlo.

edit flag offensive delete publish link

Comments

1

Máš to správně, vyšlo mi to stejně. Ještě poznámka k řešení těchto příkladů (KA -> RV) pro dotazujícího: Dá se to řešit třemi metodami - a to metodou příchozích hran, metodou odchozích hran a metodou eliminací stavů. Doporučuji prostudovat metody příchozích/odchozích. Jen zkráceně shrnu nejzajímavější věci o těchto metodách. Odchozích: Přepíšeš do soustavy regulárních rovnic, ke koncovým stavům dáš +eps. Zajímají tě počáteční stavy, tedy to bude i tvůj výsledek. Když tam bude počátečních stavů víc, dejme tomu S a A, tak výsledný RV je R+A. Příchozích: Eps dáš do počátečních stavů, uděláš soustavu reg. rovnic. Zajímají tě koncové stavy, to bude tvůj výsledek. Je dobré umět obě metody. Zvolení té správné ti může usnadnit práci. Hodně poč. stavů -> Příchozí, hodně konc. stavů - Odchozí.

Jan Rubín ( 2014-11-15 16:35:09 +0100 )edit

A když mě někdo naučí, jak v komentářích udělat newline, budu vděčný. :-(

Jan Rubín ( 2014-11-15 16:38:49 +0100 )edit

Dakujem pekne :)

gandalf ( 2014-11-15 20:38:06 +0100 )edit

@Jan Rubín: To jste si měl napsat jako otázku s tagem askfit.

V komentářích nefunguje markdown, ale fungují tam standardní HTML tagy (i neuzavřené), takže <p> pro nový odstavec (a <code><p></code> pro napsání kódu, jak udělat nový odstavec :-)).

Josef Kokeš ( 2014-11-16 09:19:55 +0100 )edit

Prevod KA -> RV

1 Answer

Comments

Your answer

Question tools

Stats

Related questions