Automaty a gramatiky - cvičení

Rozvrh: čtvrtek 10:40-12:10, posluchárna S11 a pátek 12:20-13: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

• Cvičení 1 - 22. a 28. 2.: Konečné automaty. Pumping lemma.
• Cvičení 2 - 1. a 7.3.: Myhill-Nerodova věta. Ekvivalence stavů.
• Cvičení 3 - 8. a 14.3.: Homomorfismy, faktorizace, redukce automatů. Nedeterministické KA.
• Cvičení 4 - 15. a 21.3.: NKA s lambda-přechody. Uzávěrové vlastnosti třídy regulárních jazyků.
• Cvičení 5 - 22. a 28. 3.: Regulární výrazy, Kleeneho věta.
• Cvičení 6 - 29. 3. a 4. 4.: Test 1. Regulární výrazy, automaty s výstupem.
• Cvičení 7 - 5. a 11. 4.: Dvoucestné automaty. Gramatiky. Chomského hierarchie.
• Cvičení 8 - 12. a 18. 4.: Pravé lineární gramatiky, lineární gramatiky, nevypouštěcí BKG.
• Cvičení 9 - 25. a 26. 4.: Jednoznačnost, redukce BKG. Chomského normální tvar. Pumping lemma pro BKJ.
• Cvičení 10 - 2. a 3. 5.: Greibachové normální tvar. Zásobníkové automaty.
• Cvičení 11 - 9. a 10. 5.: Test 2. Deterministické a bezprefixové BKJ. Převod BKG na ZA.

Upozornění
Příští týden 16. a 17.5. cvičení odpadají, poté bude 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.