Automaty a gramatiky - cvičení

Rozvrh: úterý 12:20-13:50 a pátek 10:40-12:10, posluchárna S6.
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 21. 2. 2014: Konečné automaty.
• Cvičení 2 - 25. a 28. 2. 2014: Myhill-Nerodova věta, iterační lemma.
• Cvičení 3 - 4. a 14. 3. 2014: Stavová ekvivalence, automatová kongruence, redukt.
• Cvičení 4 - 11. a 21. 3. 2014: Nedeterministické konečné automaty.
• Cvičení 5 - 18. a 29. 3. 2014: Uzávěrové vlastnosti třídy regulárních jazyků.
• Cvičení 6 - 25. 3. a 4. 4. 2014: 1. test, dvoucestné konečné automaty.
• Cvičení 7 - 1. a 11. 4. 2014: Mooreovy a Mealyho automaty. Kleeneova věta, regulární výrazy.
• Cvičení 8 - 8. 4. a 18. 4. 2014: Převod KA na reg. výraz a naopak, gramatiky.
• Cvičení 9 - 15. 4. a 25. 2014: Gramatiky, pravé lineární a lineární.
• Cvičení 10 - 22. 4. a 2. 5. 2014: Bezkontextové gramatiky.
• Cvičení 11 - 29. 4. a 9. 5. 2014: Normální tvary, algoritmus CYK.
• Cvičení 12 - 6. a 16. 5. 2014: Pumping lemma pro BKJ, zásobníkové automaty.
• Cvičení 13 - 14. a 16. 5. 2014: Deterministické a bezprefixové BKJ, převod BKG na ZA a naopak.

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. Bonusové body bude možné získat za obtížnější příklady na cvičeních, případně za domácí úkoly.