Automaty a gramatiky - cvičení

Rozvrh: úterý 12:20-13:50, posluchárna S10 a středa 10:40-12:10, posluchárna 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

Procvičované příklady

• Cvičení 1 - 18. a 19. 2.: Konečné automaty. Pumping lemma.
• Cvičení 2 - 3. a 4. 3. (částečně i 25. 2.): Myhill-Nerodova věta. Homomorfismus automatů. Stavová ekvivalence.
• Cvičení 3 - 10. a 11.3.: Automatová kongruence, redukce automatů. Nedeterministické KA.
• Cvičení 4 - 17. a 18.3.: NKA s lambda-přechody. Uzávěrové vlastnosti třídy regulárních jazyků.
• Cvičení 5 - 24. a 25.3.: Řetězcové operace. Kleeneho věta.
• Cvičení 6 - 31. 3. a 1. 4.: Regulární výrazy.
• Cvičení 7 - 7. a 8. 4.: Dvoucestné konečné automaty. Gramatiky.
• Cvičení 8 - 14. a 15. 4.: Chomského hierarchie. Pravé lineární gramatiky.
• Cvičení 9 - 21. a 22. 4.: Lineární a bezkontextové gramatiky. Chomského normální tvar.
• Cvičení 10 - 28. a 29. 4.: Pumping lemma pro bezkontextové jazyky, CYK algoritmus, Greibachové normální tvar.
• Cvičení 11 - 5. a 6. 5.: Zásobníkové automaty.
• Cvičení 12 - 12. a 13. 5.: Deterministické zásobníkové automaty. Deterministické a bezprefixové BKG.
• Cvičení 13 - 19. a 20. 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.