Fórum studentů MFF UK

Zařadit jazyk:
[latex]L = \{ ucv | u,v \in \{a,b\}, |u|=|v|\}[/latex]
Poté otázka na vztah kontextových a lineárních gramatik a dokázat.


[u]řešení:[/u]
jazyk je bezkontextový, (dokonce deterministický i bezprefixový) - např. zkonstruovat zásobník

[u]Co jsem slyšela u ostatních:
[/u]
[latex]L = \{ ucv | u,v \in \{a,b\}, u
eq v\}[/latex]

Otázky na Postův korespondenční problém, regulární pumping lemma, něco na Turingův stroj.

[latex]\left\{a^ib^j\:|\: 1\le i\le j \right\}[/latex] (nedá sa regulárne pumpovať, existuje bezkontextová gramatika)

Kontextové jazyky a lineárne obmedzené Turingove stroje.

Odporúčania na skúšku: Cvičenie je najlepšie mať u Surynka, pretože robí tie úlohy na zaradenie do Chomského hierarchie (rovnaké alebo podobné). Pred skúškou si teda je dobré prejsť všetky tie príklady na jeho stránke.