Surynek 16.6.2015

$\left\{a^ib^j\:|\: 1\le i\le j \right\}$ (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.

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

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

Co jsem slyšela u ostatních:

$$L = \{ ucv | u,v \in \{a,b\}, u eq v\}$$

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