Formální jazyky a automaty

10. týden: CYK, zásobníkové automaty

Pumping lemma - důkaz
Algoritmus C-Y-K
Zásobníkové automaty - akceptující kocový stavem nebo zásobníkem, rozšířenéů jejich vzájemné transformace

Slidy 9.pdf (17 ff.)

Slidy 10.pdf (pp. 1-16)

Skripta pp. 68-83

Domácí úkoly

Zadání

Svá řešení odevzdávejte prosím na skenovatelném formuláři do 29. 4. 2024 12:00 do příslušné odevzdávárny, a to ve formátech vypsaných v interaktivní osnově. Soubor musí mít vyplněnou hlavičku kvůli automatickému rozpoznávání. Pro tvorbu řešení můžete přímo upravit .tex se zadáním. K němu též potřebujete styl fja.cls a můžete použít přiložený návod na sazbu (cheatsheet.pdf).

Úkol 10, příklad 2

Svá řešení odevzdávejte prosím na skenovatelném formuláři do 6. 5. 2024 12:00 do příslušné odevzdávárny, a to ve formátech vypsaných v interaktivní osnově. Soubor musí mít vyplněnou hlavičku kvůli automatickému rozpoznávání. Pro tvorbu řešení můžete přímo upravit .tex se zadáním. K němu též potřebujete styl fja.cls a můžete použít přiložený návod na sazbu (cheatsheet.pdf).