od gejlord » 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: [latex]\alpha X \beta \rightarrow \alpha \gamma \beta[/latex], kde [latex]X \in V_N[/latex] a [latex]\alpha, \beta, \gamma \in (V_N \cup V_T)^*[/latex]
3) Sestrojte redukovaný konečný automat přijímající slova tvaru [latex]11(00+11)^*[/latex], jejichž binární interpretace je dělitelná třemi.
4) Převeďte do Chomského normální formy:
[latex]S \rightarrow TaL | MRAZ[/latex]
[latex]T \rightarrow t | A[/latex]
[latex]L \rightarrow a[/latex]
[latex]M \rightarrow MLZ | RYM[/latex]
[latex]Z \rightarrow az[/latex]
[latex]Y \rightarrow y[/latex]
[latex]R \rightarrow RYL | MYL[/latex]
[latex]A \rightarrow aAa | \lambda[/latex]
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.