BI-AAG: Automaty a gramatiky
Základní informace
- Web předmětu
- Rozvržení hodin
- Cvičení 203: čtvrtek 09:15 - 10:45 (TH:A-1342)
- Cvičení 210: čtvrtek 11:00 - 12:30 (TH:A-1342)
- Cvičení 102: čtvrtek 14:30 - 16:00 (T9:301)
- Cvičení 103: čtvrtek 16:15 - 17:45 (T9:301)
- Materiály na cvičení
Plán cvičení
- Čtvrtek 04. 10. 2018: 01 - Formální jazyky, Chomského hierarchie, gramatiky, jazykové operace nad BG (sjednocení, součin, iterace), derivační stromy
- Čtvrtek 11. 10. 2018: 02 - Intuitivní návrh gramatik (regulární, bezkontextové, kontextové, neomezené)
- Čtvrtek 18. 10. 2018: 03 - Konečné automaty, intuitivní návrh DKA a NKA, úpravy KA (nedosažitelné stavy, zbytečné stavy, epsilon přechody)
- Čtvrtek 25. 10. 2018: 04 - Test #1, úpravy KA (více počátečních stavů), determinizace NKA, minimalizace DKA
- Čtvrtek 01. 11. 2018: 05 - Minimalizace DKA, jazykové operace nad KA (sjednocení, průnik, doplněk, součin, iterace), regulární výrazy, návrh RV
- Čtvrtek 08. 11. 2018: 06 - Test #2, zjednodušování RV, pravé a levé regulární rovnice, soustavy RR, derivace RV
- Čtvrtek 15. 11. 2018: 07 - Převody RG->KA (přímá konstrukce), KA->RG (přímá konstrukce), RV->KA (metoda derivací), RV->KA/RG (metoda sousedů)
- Čtvrtek 22. 11. 2018: 08 - Převody KA->RV (metody levých a pravých RR, metoda eliminace), RG->RV (metoda pravých RR), RV->RG (metoda derivací)
- Čtvrtek 29. 11. 2018: 09 - Pumping lemma, důkazy neregulárnosti jazyků
- Čtvrtek 06. 12. 2018: 10 - Úpravy BG (jednoznačnost, prázdnost, zbytečné symboly, epsilon pravidla, jednoduchá pravidla, vyloučení pravidel), Chomského normální tvar, algoritmus CYK
- Čtvrtek 13. 12. 2018: 11 - Test #3, odstranění levé rekurze u BG, zásobníkové automaty, intuitivní návrh ZA
- Čtvrtek 20. 12. 2018: 12 - Syntaktická analýza (metody shora dolů, zdola nahoru), formální překlady, intuitivní návrh KPA, PG a ZPA
- Čtvrtek 03. 01. 2019: 13 - Intuitivní návrh ZPA, Turingovy stroje, intuitivní návrh DTS, třídy problémů P a NP, polynomiální redukce, důkazy složitosti problémů (Kachlíkování)
Zápočtové testy
- Čtvrtek 25. 10. 2018: Cvičení 04 - Test #1 - Intuitivní návrh konečného automatu a regulární / bezkontextové gramatiky
- Čtvrtek 08. 11. 2018: Cvičení 06 - Test #2 - Operace s konečnými automaty
- Čtvrtek 13. 12. 2018: Cvičení 11 - Test #3 - Důkazy neregulárnosti jazyka, algoritmy nad bezkontextovými gramatikami