Zápočet Majerech 7.5.2012, 15:40

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: $\alpha X \beta \rightarrow \alpha \gamma \beta$, kde $X \in V_N$ a $\alpha, \beta, \gamma \in (V_N \cup V_T)^*$

3. Sestrojte redukovaný konečný automat přijímající slova tvaru $11(00+11)^*$, jejichž binární interpretace je dělitelná třemi.

4. Převeďte do Chomského normální formy:
   $$S \rightarrow TaL | MRAZ$$
   $$T \rightarrow t | A$$
   $$L \rightarrow a$$
   $$M \rightarrow MLZ | RYM$$
   $$Z \rightarrow az$$
   $$Y \rightarrow y$$
   $$R \rightarrow RYL | MYL$$
   $$A \rightarrow aAa | \lambda$$

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.