Automaty a gramatiky - cvičení

Rozvrh: středa 15:40-17:10, Zoom / S8 a pátek 9:00-10:30, Zoom / 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

Oznámení: Cvičení se budou konat dle rozvrhu na platformě Zoom, viz link výše. Pokud jste nedostali pozvánku s heslem či máte jiné potíže s připojením, napište mi. Využívat budeme sdílenou tabuli Limnu, vyzkoušet si ji můžete zde.

Procvičované příklady

• Cvičení 1 - 03. a 05. 3.: Konečné automaty. Pumping lemma. tabule 3.3., tabule 5.3.
• Cvičení 2 - 10. a 12. 3.: Myhill-Nerodova věta. Homomorfismus automatů. tabule 10.3., tabule 12.3.
Cvičení 3 - 17. a 19. 3.: Stavová ekvivalence. Automatová kongruence, redukce automatů. tabule 17.3., tabule 19.3.
• Cvičení 4 - 24. a 26. 3.: Nedeterministické konečné automaty. NKA s lambda-přechody. Uzávěrové vlastnosti třídy regulárních jazyků. tabule 24.3., tabule 26.3.
• Cvičení 5 - 31. 3. a 9. 4.: Řetězcové operace s jazyky. tabule 31. 3., tabule 9. 4.
• Cvičení 6 - 7.4. a 16.4.: Kleeneho věta. Regulární výrazy. tabule 7. 4. tabule 16. 4.
• Cvičení 7 - 14.4. a 23.4.: Automaty s výstupem. Dvoucestné konečné automaty. Gramatiky. tabule 14. 4. tabule 23. 4.
• Cvičení 8 - 21. a 30. 4.: Chomského hierarchie. Pravé lineární gramatiky. tabule 21. 4., tabule 30. 4.
• Cvičení 9 - 28.4. a 7.5.: Lineární a bezkontextové gramatiky. Chomského normální tvar. tabule 28. 4., tabule 7. 5.
• Cvičení 10 - 5. 5. a 14. 5.: Pumping lemma pro bezkontextové jazyky, CYK algoritmus, zásobníkové automaty. tabule 5. 5., tabule 14. 5.
• Cvičení 11 - 19. 5. a 21. 5.: Zásobníkové automaty, Greibachové normální tvar. tabule 19. 5., tabule 21. 5.
• Cvičení 12 - 26. 5. a 28. 5.: Deterministické zásobníkové automaty. Kontextové gramatiky. Turingovy stroje. tabule 26. 5., tabule 28. 5.

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. Domácí úkoly se budou odevzdávat přes Moodle. Přihlašte se do příslušné skupiny v Moodle dle vašeho cvičení.