Automaty a gramatiky - cvičení

Rozvrh: středa 10:40-12:10 a čtvrtek 9:00-10:30, posluchárna S10.
Vyučující: Petr Gregor (gregor(at)ktiml.mff.cuni.cz)
Informace o přednášce: 2/2 Zk/Z NTIN071 v SISu, na stránce k přednášce

Procvičované příklady

• Cvičení 1 - 1. a 2. 3.: Konečné automaty. Myhill-Nerodova věta.
• Cvičení 2 - 8. a 9. 3.: Pumping lemma. Stavová ekvivalence.
• Cvičení 3 - 15. a 16. 3.: Homomorfismy, faktorizace, redukce automatů. Nedeterministické KA.
• Cvičení 4 - 22. a 23. 3.: NKA s lambda-přechody. Uzávěrové vlastnosti třídy regulárních jazyků.
• Cvičení 5 - 29. a 30. 3.: Regulární výrazy, Kleeneho věta.
• Cvičení 6 - 5. a 6. 4.: Test 1. Mooreovy a Mealyho automaty.
• Cvičení 7 - 12. a 13. 4.: Gramatiky. Chomského hierarchie.
• Cvičení 8 - 19. a 20. 4.: Pravé lineární gramatiky, lineární gramatiky, nevypouštěcí BKG, jednoznačnost BKG.
• Cvičení 9 - 26. a 27. 4.: Redukce BKG. Chomského a Greibachové normální tvary. Pumping lemma pro BKJ.
• Cvičení 10 - 3. a 4. 5.: Algoritmus CYK. Zásobníkové automaty.
• Cvičení 11 - 10. a 11. 5.: Test 2. Deterministické a bezprefixové BKJ. Převod BKG na ZA a naopak.
• Cvičení 12 - 18. 5.: Dyckovy jazyky, uzávěrové vlastnosti třídy BKJ. Kontextové gramatiky. Turingovy stroje.

Upozornění
Příští týden 24. a 25. 5. bude zápočtová písemka, bližší popis viz Cvičení 12.

Hodnocení
Bude založené na bodech získaných za dva testy psané v průběhu semestru a zápočtovou písemku na konci. Další body bude možné získat za domácí úkoly, bonusový bod za aktivitu na cvičeních.