BI-AAG.21: Automaty a gramatiky
Základní informace
- Webové stránky
- Rozvrh hodin
- Cvičení 08: čtvrtek 12:45 - 14:15 (T9:302)
- Cvičení 10: čtvrtek 14:30 - 16:00 (T9:302)
- Cvičení 12: čtvrtek 16:15 - 17:45 (T9:302)
- Cvičení 13: čtvrtek 18:00 - 19:30 (T9:302)
- Evidence bodů
- Materiály na cvičení
Plán cvičení
- Čtvrtek 28. 09. 2023: Cvičení zrušeno (Den české státnosti)
- Čtvrtek 05. 10. 2023: 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 12. 10. 2023: Téma 02 - Gramatiky
- Intuitivní návrh gramatik (regulární, bezkontextové, kontextové, neomezené)
- Čtvrtek 19. 10. 2023: 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 26. 10. 2023: Téma 04 - Konečné automaty II
- Determinizace NKA, minimalizace DKA, jazykové operace nad KA (sjednocení, průnik, doplněk, součin, iterace)
- Čtvrtek 02. 11. 2023: 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, derivace RV
- Záznam (167 MB)
- Čtvrtek 09. 11. 2023: Téma 06 - Převody I
- Převody RV->KA/RG (sousedé), KA->RV (levé a pravé RR, eliminace stavů)
- Samostudium: Téma 07 - Převody II
- RG->KA (přímá transformace), KA->RG (přímá transformace), RV->KA (derivace), RV->KA (postupná konstrukce), RG->RV (pravé RR, eliminace neterminálů), RV->RG (derivace)
- Záznam (98 MB)
- Aktivita: středa 15. 11. 2023
- Čtvrtek 16. 11. 2023: Téma 08 - Důkazy I
- Pumping lemma, důkazy neregulárnosti jazyků
- Čtvrtek 23. 11. 2023: Téma 09 - Důkazy II
- Důkazy neregulárnosti jazyků, Myhillova-Nerodova věta, uzávěrové vlastnosti
- Čtvrtek 30. 11. 2023: Téma 10 - 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, odstranění levé rekurze u BG
- Čtvrtek 07. 12. 2023: Zápočtový test
- Čtvrtek 14. 12. 2023: Téma 11 - Bezkontextové jazyky
- Algoritmus CYK, zásobníkové automaty, intuitivní návrh ZA, syntaktická analýza (metody shora dolů, zdola nahoru)
- Čtvrtek 21. 12. 2023: Téma 12 - Překlady
- Formální překlady, intuitivní návrh KPA, ZPA, RPG, BPG, transformace BPG na ZPA
- Samostudium: Téma 13 - 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í)
- Záznam (215 MB)
- Aktivita: středa 03. 01. 2024