Automaty a gramatiky - cvičení

Rozvrh: středa 15:40-17:10 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 - 18. a 20. 2. 2015: Konečné automaty. Myhill-Nerodova věta.
• Cvičení 2 - 25. a 27. 2. 2015: Iterační (pumping) lemma. Homomorfismus automatů.
• Cvičení 3 - 4. a 6. 3. 2015: Stavová ekvivalence, automatová kongruence, redukt.
• Cvičení 4 - 11. a 13. 3. 2015: Nedeterministické konečné automaty.
• Cvičení 5 - 18. a 20. 3. 2015: Uzávěrové vlastnosti třídy regulárních jazyků.
• Cvičení 6 - 25. a 27. 3. 2015: Test 1. Mooreovy a Mealyho automaty. Dvoucestné automaty.
• Cvičení 7 - 1. a 3. 4. 2015: Regulární výrazy. Kleeneho věta.
• Cvičení 8 - 8. a 10. 4. 2015: Převod KA na reg. výraz a naopak, gramatiky.
• Cvičení 9 - 15. a 17. 4. 2015: Pravé lineární gramatiky, lineární gramatiky, nevypouštěcí BKG.
• Cvičení 10 - 22. a 24. 4. 2015: Redukce BKG, jednoznačnost, Chomského normální tvar, pumping lemma pro BKJ.
• Cvičení 11 - 29. 4. a 15. 5. 2015: Test 2. Greibachové normální tvar. Zásobníkové automaty.

Upozornění
Ve středu 29. 4. a v pátek 15. 5. se bude psát druhý test. Mezi 30. 4. a 14. 5. cvičení odpadají (státní svátky, rektorský den, služební cesta). Na posledních cvičeních 20. a 22. 5. 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.