# Zápočet Majerech 7.5.2012, 15:40

<{ForumPost(poster="gejlord", timestamp=2012-05-07 17:32:51)}>
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.
<{/ForumPost}>