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
Kolega dostal Postuv korespondencni problem.
Surynek 2.6. 2015
- CiTrus
- Matfyz(ák|ačka) level I
- Příspěvky: 19
- Registrován: 22. 6. 2014 14:05
- Typ studia: Informatika Mgr.
- Login do SIS: manekp
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Surynek 2.6. 2015
Já dnes měl celkem štěstí. Dostal jsem opravdu jednoduché zadání:
Pokud by to někoho zajímalo, zde je náznak mého řešení:
- 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 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 . Prozkoumáme rozklad na xyz a zjistíme, že v souladu s podmínkami musí být , kde . 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: , což ale určitě nepatří do L protože pro neplatí - to je spor. - Viz slides 2-4 ve 12. přednášce.
- CiTrus
- Matfyz(ák|ačka) level I
- Příspěvky: 19
- Registrován: 22. 6. 2014 14:05
- Typ studia: Informatika Mgr.
- Login do SIS: manekp
- Bydliště: Praha
- Kontaktovat uživatele:
Re: Surynek 2.6. 2015
Co jsem slyšel, že dnes dostali ostatní.
1. část:
1. část:
- Najít, popsat a dokázat jazyk, který není rekurzivní. Například Lu. Musela se použít Ricova věta.
- 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.