Surynek 2.6. 2015

Základní přednáška z teorie jazyků a automatů. Důraz je kladen na seznámení se základními pojmy a fakty (konečné a zásobníkové automaty, Turingovy stroje, regulární, bezkontextové a kontextové gramatiky).
rrr

Surynek 2.6. 2015

Příspěvek od rrr »

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.
Uživatelský avatar
CiTrus
Matfyz(ák|ačka) level I
Příspěvky: 19
Registrován: 22. 6. 2014 14:05
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Surynek 2.6. 2015

Příspěvek od CiTrus »

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.
Uživatelský avatar
CiTrus
Matfyz(ák|ačka) level I
Příspěvky: 19
Registrován: 22. 6. 2014 14:05
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Surynek 2.6. 2015

Příspěvek od CiTrus »

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 Lu. 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.
Odpovědět

Zpět na „TIN071 Automaty a gramatiky“