Dokažte, že problém neprázdnosti jazyka Turingového stroje je nerozhodnutelný, ale je jen částečně rozhodnutelný.
Problem neprazdnosti jazyka 1.JPG
Problem neprazdnosti jazyka 2.JPG
Ukažte, že třída jazyků L0 je uzavřena vůči substituci jazyků třídy L0.
Uzavrenost vuci substituci jazyku.JPG
Dokažte, že problém, zda daný TS pro daný vstupní řetězec zastaví není rozhodnutelný, ale je jen částečně rozhodnutelný.
Diagonalizace a nerozhodnutelnost HP 1.JPG
Diagonalizace a nerozhodnutelnost HP 2.JPG
Kleeneova věta (či Kleenova věta, Kleeneho věta), ukázka použití této Kleenovy věty včetně ukázky řešení rovnic nad regulárními výrazy:
kleenova veta.JPG
Příklady a ukázky jak odstranit epsilon pravidla v gramatice může najít zde, jsou na to 3 ukázkové příklady:
odstrante e-pravidla 1.JPG
odstrante e-pravidla 2.JPG
odstrante e-pravidla 3.JPG
Důkaz pomocí Myhill-Nerodovi věty zde:
Myhill nerodova veta.JPG
Dvě ukázky převodu gramatiky do Chomské normální formy
První příklad:
Chomskeho normalni forma (priklad 1) 1.JPG
Chomskeho normalni forma (priklad 1) 2.JPG
Chomskeho normalni forma (priklad 1) 3.JPG
Druhý příklad:
Chomskeho normalni forma (priklad 2).JPG
Chomskeho normalni forma (priklad 2) 2.JPG
Chomskeho normalni forma (priklad 2) 3.JPG
Ukázka převodu gramatiky do Greibachové normální formy, včetně ukázky odstranění přímé levé rekurze a odstranění nepřímé levé rekurze:
Greibachova normalni forma 1.JPG
Greibachova normalni forma 2.JPG
Greibachova normalni forma 3.JPG
Greibachova normalni forma 4.JPG
Syntaktická analýza shora dolů včetně konfigurace:
Syntakticka analyza shora dolu.JPG
Syntaktická analýza zdola nahoru včetně konfigurace:
Syntakticka analyza zdola nahoru.JPG
Syntakticka analyza zdola nahoru (pokracovani).JPG
Ukázka algoritmu Cocke-Kasami-Younger (či Cocke-Younger-Kasami)
Cocke-Kasami-Younger.JPG
Dokažte, že pro daný Turingův stroj lze rozhodnout, zda má alespoň 2009 stavů:
Turinguv stroj alespon 2009 stavu .JPG
Ten stejný dokument můžete být použit pro jakýkoliv množství stavů, které si můžete doplnit podle vlastního uvážení :-), např:
Dokažte, že pro daný Turingův stroj lze rozhodnout, zda má alespoň 2010 stavů
Dokažte, že pro daný Turingův stroj lze rozhodnout, zda má alespoň 2011 stavů
Dokažte, že pro daný Turingův stroj lze rozhodnout, zda má alespoň 2012 stavů
Dokažte, že pro daný Turingův stroj lze rozhodnout, zda má alespoň 2013 stavů
Navrhněte zásobníkový automat, který bude akceptovat jazyk L^1997.
Zasobnikovy automat L1997.JPG
Jak by měl vypadat Konečný automat, který akceptuje jazyk:
L1 = {w; w in {0,1}*, w obsahuje lichý počet symbolů 0 a zároveň sudý (i nulový) počet symbolů 1}
L2= {w; w in {0,1}*, w obsahuje posloupnost 011}
konecny_automat.jpg