BI-AAG.21: Automaty a gramatiky
Základní informace
- Webové stránky
- Rozvrh hodin
- Cvičení 11: čtvrtek 12:45 - 14:15 (TH:A-1442)
- Cvičení 12: čtvrtek 14:30 - 16:00 (TH:A-1442)
- Cvičení 13: čtvrtek 16:15 - 17:45 (TH:A-1442)
- Cvičení 14: čtvrtek 18:00 - 19:30 (TH:A-1442)
- Evidence bodů
- Materiály na cvičení - verze 35 (2025-09-16)
Plán cvičení
- Čtvrtek 25. 09. 2025: Cvičení 01 - Formální jazyky
- Formální jazyky, Chomského hierarchie, gramatiky, jazykové operace nad BG (sjednocení, součin, iterace), derivační stromy
- Čtvrtek 02. 10. 2025: Cvičení 02 - Gramatiky
- Intuitivní návrh gramatik (regulární, bezkontextové, kontextové, neomezené)
- Čtvrtek 09. 10. 2025: Cvičení 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 16. 10. 2025: Cvičení 04 - Konečné automaty II
- Determinizace NKA, minimalizace DKA, jazykové operace nad KA (sjednocení, průnik, doplněk, součin, iterace)
- Čtvrtek 23. 10. 2025: Cvičení 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 30. 10. 2025: Cvičení 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 06. 11. 2025: Cvičení 07 - Důkazy I
- Pumping lemma, důkazy neregulárnosti jazyků
- Čtvrtek 13. 11. 2025: Cvičení 08 - Důkazy II
- Důkazy neregulárnosti jazyků, Myhillova-Nerodova věta, uzávěrové vlastnosti
- Čtvrtek 20. 11. 2025: Cvičení 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 27. 11. 2025: Cvičení 10 - Bezkontextové jazyky
- Algoritmus CYK, zásobníkové automaty, intuitivní návrh ZA, syntaktická analýza (metody shora dolů, zdola nahoru)
- Čtvrtek 04. 12. 2025: Zápočtový test
- Čtvrtek 11. 12. 2025: Cvičení 11 - Překlady
- Formální překlady, intuitivní návrh KPA, ZPA, RPG, BPG, transformace BPG na ZPA
- Čtvrtek 18. 12. 2025: Cvičení 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í)