Automaty a gramatiky - cvičení

Rozvrh: středa 15:40-17:10 a čtvrtek 17:20-18:50, 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
zde budou zveřejněny po každém cvičení

• Cvičení 1 - 21. a 22. 2.: Konečné automaty. Myhill-Nerodova věta.
• Cvičení 2 - 28. 2. a 1. 3.: Pumping lemma. Stavová ekvivalence.
• Cvičení 3 - 7. a 8. 3.: Homomorfismy, faktorizace, redukce automatů. Nedeterministické KA.
• Cvičení 4 - 14. a 15. 3.: NKA s lambda-přechody. Uzávěrové vlastnosti třídy regulárních jazyků.
• Cvičení 5 - 21. a 22. 3.: Regulární výrazy, Kleeneho věta.
• Cvičení 6 - 28. a 29. 3.: Test 1. Regulární výrazy.
• Cvičení 7 - 4. a 5. 4.: Gramatiky. Chomského hierarchie.
• Cvičení 8 - 11. a 12. 4.: Pravé lineární gramatiky, lineární gramatiky, nevypouštěcí BKG.
• Cvičení 9 - 18. a 19. 4.: Jednoznačnost, redukce BKG. Chomského normální tvar. Pumping lemma pro BKJ.
• Cvičení 10 - 26. a 27. 4.: Algoritmus CYK. Zásobníkové automaty.
• Cvičení 11 - 2. a 3. 5.: Deterministické a bezprefixové BKJ. Převod BKG na ZA a naopak.
• Cvičení 12 - 9. a 10. 5.: Test 2. Uzávěrové vlastnosti třídy BKJ. Greibachové normální tvar.
• Cvičení 13 - 17. 5.: Opakování látky.
• Cvičení 14 - 23. a 24. 5.:Zápočtová písemka.

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.