# Surynek 16.6.2015

<{ForumPost(poster="VImpaler", timestamp=2015-06-16 11:14:19)}>
$\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.
<{/ForumPost}>

<{ForumPost(poster="Ely", timestamp=2015-06-18 01:02:06)}>
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.
<{/ForumPost}>