Příklady k procvičení

Dokažte, že problém neprázdnosti jazyka Turingového stroje je nerozhodnutelný, ale je jen částečně rozhodnutelný.

Ukažte, že třída jazyků L0 je uzavřena vůči substituci jazyků třídy L0.

Dokažte, že problém, zda daný TS pro daný vstupní řetězec zastaví není rozhodnutelný, ale je jen částečně rozhodnutelný.

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:

Příklady a ukázky jak odstranit epsilon pravidla v gramatice může najít zde, jsou na to 3 ukázkové příklady:

Důkaz pomocí Myhill-Nerodovi věty zde: 

Dvě ukázky převodu gramatiky do Chomské normální formy
První příklad: 

Druhý příklad:

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:

Syntaktická analýza shora dolů včetně konfigurace:

Syntaktická analýza zdola nahoru včetně konfigurace:

Ukázka algoritmu Cocke-Kasami-Younger (či Cocke-Younger-Kasami)

Dokažte, že pro daný Turingův stroj lze rozhodnout, zda má alespoň 2009 stavů:
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.


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}



 



Abyste mohli přidat gadgety, které vidíte pouze vy, musíte se přihlásit.