# Surynek 2.6. 2015

<{ForumPost(poster="rrr", timestamp=2015-06-02 16:07:47)}>
Jas som dostal: 1. Zaradit do Chomskeho hierarchie jazyk L={ucu| u,v ∈ {a,b}* , |u|=|v|} - bolo treba najst v mojom pripade gramatiku prip. zasobnikovy automat ktory ho prijma a potom Pumping lematem dokazat ze nie je regularny.  
2. Co viem o L_u, celkom sa pytal na to ako pracuje univerzalny turingov stroj (ako zakoduje w a preco ako si drzi stavy kod(T) a preco...) a poto msom dokazal ze L_u nie je rekurzivny tam sa uz nepytal vobec nic co som bol celkom rad :D  
Kolega dostal Postuv korespondencni problem.
<{/ForumPost}>

<{ForumPost(poster="CiTrus", timestamp=2015-06-02 19:15:12)}>
Já dnes měl celkem štěstí. Dostal jsem opravdu jednoduché zadání:

* $L=\{a^ib^ja^kb^l|i,j,k,l=0,1,2,...\wedge i=j\wedge k=l\}$
* Vícepáskový Turingův stroj a vše k němu. Zejména porovnat výpočetní sílu s klasickým Turingovým strojem a všechna tvrzení dokázat.

----

Pokud by to někoho zajímalo, zde je náznak mého řešení:

* Jazyk je bezkontextový. Dá se postavit zásobníkový automat, který pro každé A hodí symbol na zásobník a pro každé B symbol zase sebere. Takový automat akceptuje výše uvedený jazyk prázdným zásobníkem. Kdo si chce ulehčit práci, může automat postavit jenom pro jazyk $L'=\{a^ib^j|i,j=0,1,2,...\wedge i=j\}$ a pak prohlásit, že původní jazyk je vlastně konkatenací L'.L' a protože L' je bezkontextový, z uzávěrových vlastností vyplývá, že i L je bezkontextový.  
  
Lépe to nejde, protože regularita jde jednoduše vyvrátit pumping lemmatem. Pro spor předpokládejme, že existuje přirozené n dle pumping lemmatu pro regulární jazyky. Zvolme slovo $a^nb^na^{42}b^{42}$. Prozkoumáme rozklad na xyz a zjistíme, že v souladu s podmínkami musí být $x=a^p, y=a^q$, kde $p\geq 0,q>0,p+q\leq n$. Nyní můžeme prostřední část slova vynechat a výsledné slovo by opět mělo patřit do jazyka. To slovo ale vypadá takto: $a^pa^{n-p-q}b^na^{42}b^{42}=a^{n-q}b^na^{42}b^{42}$, což ale určitě nepatří do L protože pro $q>0$ neplatí $n-q=n$ - to je spor.
* Viz slides 2-4 ve [12. přednášce](http://ktiml.mff.cuni.cz/%7Esurynek/teaching/2014_2015-LS/automaty_a_gramatiky/files/Prednaska-12_Automaty-a-gramatiky.pdf).

<{/ForumPost}>

<{ForumPost(poster="CiTrus", timestamp=2015-06-02 19:29:18)}>
Co jsem slyšel, že dnes dostali ostatní.  
  
1. část:

* $L=\{a^ib^ja^ka^l|i,j,k,l=0,1,2,...\wedge i=j\wedge j=k \wedge k=l\}$
* Najít, popsat a dokázat jazyk, který není rekurzivní. Například L<sub>u</sub>. Musela se použít Ricova věta.

2. část:

* Popsat úplně algoritmus CYK. Zmínit myšlenku, složitost a způsob výpočtu. Dokázat správnost a ukázat příklad.
* Univerzální Turingův stroj a vše kolem něj.
* Ricova věta - znění a důkaz.

<{/ForumPost}>