Zápočet Majerech 7.5.2012, 15:40

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
gejlord

Zápočet Majerech 7.5.2012, 15:40

Příspěvek od gejlord »

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.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“