Automaty a gramatiky - cvičení

Rozvrh: čtvrtek 12:20-13:50, S7.
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

Oznámení: Cvičení se v tomto semestru budou opět konat prezenčně.

Procvičované příklady

• Cvičení 1 - 17. 2.: Konečné automaty. Pumping lemma.
• Cvičení 2 - 24. 2.: Myhill-Nerodova věta. Homomorfismus automatů.
• Cvičení 3 - 03. 3.: Stavová ekvivalence. Automatová kongruence.
• Cvičení 4 - 10. 3.: Redukce automatů. Nedeterministické konečné automaty. NKA s lambda-přechody.
• Cvičení 5 - 17. 3.: Uzávěrové vlastnosti třídy regulárních jazyků. Řetězcové operace s jazyky.
• Cvičení 6 - 24. 3.: Kvocienty. Kleeneho věta.
• Cvičení 7 - 31. 3.: Regulární výrazy. Dvoucestné KA. Formální gramatiky.
• Cvičení 8 - 07. 4.: Chomského hierarchie, gramatiky.
• Cvičení 9 - 14. 4.: Pravé lineární, lineární a bezkontextové gramatiky. Redukce BKG.
• Cvičení 10 - 21. 4.: Chomského normální tvar. Pumping lemma pro BKJ, CYK algoritmus, zásobníkové automaty.
• Cvičení 11 - 28. 4.: Zásobníkové automaty, determinismus, vztah k BKJ.
• Cvičení 12 - 05. 5.: Greibachové normální tvar. Deterministické a bezprefixové BKJ, uzávěrové vlastnosti. Dyckovy jazyky.
• Cvičení 13 - 12. 5.: Kontextové gramatiky. Turingovy stroje.

Hodnocení
Bude založené na bodech získaných za domácí úkoly v průběhu semestru a zápočtovou písemku na konci. Další bod za aktivitu na cvičeních. Domácí úkoly se budou odevzdávat fyzicky na cvičeních (preferováno) anebo elektronicky přes Moodle. V tom případě je třeba se přihlásit do skupiny v Moodle k tomuto cvičení.