Surynek 2.6. 2015

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.

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.

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_u. 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.