Zápočet Majerech 7.5.2012, 15:40
Napsal: 7. 5. 2012 17:32
1) Rozhodněte, zda existuje jazyk L takový, že L i jeho doplněk splňují předpoklady podtrhávacího pumping lemma pro regulární jazyky, ale L není regulární.
2) Rozhodněte, zda lze každou gramatiku ekvivalentně převést (generuje stejný jazyk) do pravidel tvaru: , kde a
3) Sestrojte redukovaný konečný automat přijímající slova tvaru , jejichž binární interpretace je dělitelná třemi.
4) Převeďte do Chomského normální formy:
První úloha prý byla stejná i pro první skupinu (v 14:00). Ostatní nevim. Taky nám napsal na tabuli znění podtrhávacího pumping lemma.
2) Rozhodněte, zda lze každou gramatiku ekvivalentně převést (generuje stejný jazyk) do pravidel tvaru: , kde a
3) Sestrojte redukovaný konečný automat přijímající slova tvaru , jejichž binární interpretace je dělitelná třemi.
4) Převeďte do Chomského normální formy:
První úloha prý byla stejná i pro první skupinu (v 14:00). Ostatní nevim. Taky nám napsal na tabuli znění podtrhávacího pumping lemma.