Matematické Fórum

Ahoj, v zkouskove pisemce co budu psat v pondeli bude urcite prevod regularniho vyrazu na DFA.
Neznam na to zadny algoritmus, tak jsem pouzil takovou intuitivni metodu, pri ktery si proste kreslim graf podle moznyho vstupu, nasledne podmnozinovou konstrukci prevedu NFA na DFA. Jenze hned u prveho zkouseneho prikladu jsem narazil na problem. Popisu:

Samotny regv:
(perl regexp by vypadal takhle: (a*[ab]b)* )

coz vicemene dava vstup, ktery muze (ale nemusi) zacinat libovolnym poctem a, nasleduje jedno nebo dve b (v pripade, ze nezacina zadnym ackem). Pote muze byt vstup ukoncen a nebo se opakovat podobna situace nekonecnekrat dokola. Zaroven to "zere" prazdne slovo.

tabulka prechodove fce: z grafu, co jsem stvoril, onim i a o znacim vstupni (i) a vystupni (o) stav.



Podmnozinovou konstrukci z toho dostanu vicemene identickou tabulku (psal jsem to bez {} protoze me to nebavi v latechu escapovat)


Onen radek s tucnou 2,1 je to, co mi pusobi problem: zatimco puvodni regexp prijme maximalne abbb (ab a potom bb), tak tenhle DFA uz je ochotnej (diky te smycce u (2,1)) prijmout i [b]abbbb[b/] k cemuz nema podporu v regexpu. Opravit tuhle konkretni chybu dokazu, misto pouziju , cimz by to melo zacit odpovidat. Jenze podobne chyby si v pisemce treba ani nemusim vsimnout ci mi nepujde tak lehce odstranit. A ted se konecne muzu zacit ptat:

1. Je muj postup prevodu vubec spravny/pouzitelny?
2. Nemam treba dokonce chybu nekde v te podmnozinove konstrukci? 
2. Existuje nejaky prijemnejsi algoritmus pro prevod?

Snad je pochopitelne, co mam za problem a co chci, proto dekuji za odpovedi a preju hezkej den!