BI-AAG.21: Automaty a gramatiky
Základní informace
- Webové stránky
- Rozvrh hodin
- Cvičení 12: čtvrtek 12:45 - 14:15 (T9:301)
- Cvičení 13: čtvrtek 14:30 - 16:00 (T9:301)
- Cvičení 14: čtvrtek 16:15 - 17:45 (T9:301)
- Cvičení 15: čtvrtek 18:00 - 19:30 (T9:301)
- Evidence bodů
- Materiály na cvičení - verze 33 (2024-10-31)
Plán cvičení
- Čtvrtek 26. 09. 2024: Téma 01 - Formální jazyky
- Formální jazyky, Chomského hierarchie, gramatiky, jazykové operace nad BG (sjednocení, součin, iterace), derivační stromy
- Čtvrtek 03. 10. 2024: Téma 02 - Gramatiky
- Intuitivní návrh gramatik (regulární, bezkontextové, kontextové, neomezené)
- Čtvrtek 10. 10. 2024: Téma 03 - Konečné automaty I
- 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. 2024: Téma 04 - Konečné automaty II
- Determinizace NKA, minimalizace DKA, jazykové operace nad KA (sjednocení, průnik, doplněk, součin, iterace)
- Čtvrtek 24. 10. 2024: Téma 05 - Regulární výrazy
- Regulární výrazy, návrh RV, zjednodušování RV, pravé a levé regulární rovnice, soustavy RR
- Čtvrtek 31. 10. 2024: Téma 06 - Převody
- Převody RG->KA (transformace), KA->RG (transformace), RV->KA (sousedé), KA->RV (pravé RR), RG->RV (pravé RR), RV->RG (konstrukce)
- Čtvrtek 07. 11. 2024: Téma 07 - Důkazy I
- Pumping lemma, důkazy neregulárnosti jazyků
- Čtvrtek 14. 11. 2024: Téma 08 - Důkazy II
- Důkazy neregulárnosti jazyků, Myhillova-Nerodova věta, uzávěrové vlastnosti
- Čtvrtek 21. 11. 2024: Téma 09 - Bezkontextové gramatiky
- Vlastnosti BG (jednoznačnost, prázdnost), úpravy BG (zbytečné symboly, epsilon pravidla, jednoduchá pravidla, vyloučení pravidel), Chomského normální tvar
- Čtvrtek 28. 11. 2024: Zápočtový test
- Čtvrtek 05. 12. 2024: Téma 10 - Bezkontextové jazyky
- Algoritmus CYK, zásobníkové automaty, intuitivní návrh ZA, syntaktická analýza (metody shora dolů, zdola nahoru)
- Čtvrtek 12. 12. 2024: Téma 11 - Překlady
- Formální překlady, intuitivní návrh KPA, ZPA, RPG, BPG, transformace BPG na ZPA
- Čtvrtek 19. 12. 2024: Téma 12 - Turingův stroj
- Turingův stroj, 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í)