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