BI-AAG: Automaty a gramatiky
Základní informace
- Web předmětu
- Rozvržení hodin
- Cvičení 201: čtvrtek 09:15 - 10:45 (T9:301)
- Cvičení 202: čtvrtek 11:00 - 12:30 (T9:301)
- Cvičení 203: čtvrtek 14:30 - 16:00 (T9:301)
- Cvičení 204: čtvrtek 16:15 - 17:45 (T9:301)
- Materiály na cvičení
Plán cvičení
- ČT 05. 10. 2017: 01 - Formální jazyky, Chomského hierarchie, gramatiky, jazykové operace nad BG (sjednocení, součin, iterace), derivační stromy
- ČT 12. 10. 2017: 02 - Intuitivní návrh gramatik (regulární, bezkontextové, kontextové, neomezené)
- ČT 19. 10. 2017: 03 - Konečné automaty, intuitivní návrh DKA a NKA, úpravy KA (nedosažitelné stavy, zbytečné stavy, epsilon přechody, více počátečních stavů)
- ČT 26. 10. 2017: 04 - Determinizace NKA, minimalizace DKA
- ČT 02. 11. 2017: 05 - Jazykové operace nad KA (sjednocení, průnik, doplněk, součin, iterace), regulární výrazy
- ČT 09. 11. 2017: 06 - Zjednodušování RV, regulární rovnice a soustavy rovnic, derivace RV
- ČT 16. 11. 2017: 07 - Převody RG->KA, KA->RG, RV->KA (metody derivací a sousedů)
- ČT 23. 11. 2017: 08 - Převody KA->RV (metody levých a pravých RR, metoda eliminace), RG->RV (metoda pravých RR), BG (jednoznačnost, prázdnost), úpravy BG (zbytečné symboly)
- ČT 30. 11. 2017: 09 - Úpravy BG (epsilon pravidla, jednoduchá pravidla, vyloučení pravidel), Chomského normální tvar, algoritmus CYK
- ČT 07. 12. 2017: 10 - Odstranění levé rekurze u BG, zásobníkové automaty, intuitivní návrh ZA
- ČT 14. 12. 2017: 11 - Intuitivní návrh ZA, pumping lemma, důkazy neregulárnosti jazyků
- ČT 21. 12. 2017: 12 - Důkazy neregulárnosti jazyků, syntaktická analýza (metody shora dolů, zdola nahoru), formální překlady
- ČT 04. 01. 2018: 13 - Formální překlady, intuitivní návrh KPA, PG a ZPA
Zápočtové testy
- ČT 26. 10. 2017: Cvičení 04 - Test #1 - Návrh BG
- ČT 09. 11. 2017: Cvičení 06 - Test #2 - Determinizace NKA
- ČT 16. 11. 2017: Cvičení 07 - Test #3 - Minimalizace DKA
- ČT 07. 12. 2017: Cvičení 10 - Test #4 - Převody KA, RV, RG
- ČT 21. 12. 2017: Cvičení 12 - Test #5 - Úpravy BG
- ČT 04. 01. 2018: Cvičení 13 - Test #6 - Pumping lemma