IB 102 - úkol 7 - řešení
Odevzdání: 14.11. 2011
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Navrhněte algoritmus, který pro zadanou regulární gramatiku rozhodne, zda tato gramatika generuje alespoň jedno slovo neobsahující symbol a.
Bonus [2 body] Navrhněte algoritmus, který pro zadanou regulární gramatiku rozhodne, zda tato gramatika generuje alespoň dvě slova neobsahující symbol a.
Řešení mohlo vypadat například takto:
1. Odstraníme z gramatiky všechna pravidla obsahující na pravé straně terminál a, tedy všechna pravidla tvaru A —> aB nebo A —> a pro všechny neterminály A, B.
2. Pro tímto vzniklou novou gramatiku zkonstruujeme ekvivalentní konečný automat. Použijeme konstrukci v důkazu lemmatu 2.69 ze skript.
3. Spočítáme si množinu všech dosažitelných stavů automatu. Obsahuje-li tato množina koncový stav, odpověď je ANO; v opačném případě je odpověď NE.
Bonus: Řešení mohlo vypadat například takto:
1. Odstraníme z gramatiky všechna pravidla obsahující na pravé straně terminál a, tedy všechna pravidla tvaru A —> aB nebo A —> a pro všechny neterminály A, B.
2. Pro tímto vzniklou novou gramatiku zkonstruujeme ekvivalentní konečný automat. Použijeme konstrukci v důkazu lemmatu 2.69 ze skript. Označme si tento automat M.
3. Spočítáme si množinu všech dosažitelných stavů automatu. Obsahuje-li tato množina koncový stav, pokračujeme bodem 4; v opačném případě je odpověď NE a algoritmus končí.
4. Nalezneme nějaké slovo akceptované zkonstruovaným automatem. To provedeme například tak, že pomocí prohledávání do šířky nalezneme cestu z počátečního stavu do stavu koncového (že taková cesta existuje, jsme si zaručili v předchozím bodě). Označme si toto slovo w.
5. Sestrojíme automat Mw akceptující jazyk E* — {w}, kde E je množina terminálů původní gramatiky.
6. Pomocí techniky synchronního paralelního spojení sestrojíme automat M' akceptující jazyk L(M) fl L(MW).
7. Spočítáme si množinu všech dosažitelných stavů automatu M'. Obsahuje-li tato množina koncový stav, odpověď je ANO; v opačném případě je odpověď NE.