BI-AAG: Automaty a gramatiky
Základní informace
- Web předmětu
- Rozvržení hodin
- Cvičení 7: čtvrtek 12:45 - 14:15 (TH:A-1242)
- Cvičení 8: čtvrtek 14:30 - 16:00 (TH:A-1242)
- Cvičení 10: čtvrtek 16:15 - 17:45 (TH:A-1242)
- Cvičení 12: čtvrtek 18:00 - 19:30 (TH:A-1242)
- Příklady na aktivitu
- Řešení je vždy potřeba poslat jako PDF soubor v příloze mailu na adresu martin.svoboda@fit.cvut.cz
- Název souboru: #P.pdf (kde #P je osobní číslo přidělené na začátku semestru, např. 1234.pdf)
- Pro případnou konverzi do formátu PDF můžete použít například službu CloudConvert.com
- Předmět mailu: BI-AAG aktivita #C (kde #C je pořadové číslo cvičení, např. BI-AAG aktivita 1)
- Termín odevzdání: v den cvičení do 23:59
- Záznamy ze cvičení
- Níže uvedené záznamy cvičení byly vytvořeny v průběhu předchozího akademického roku 2020/21
- Pro jejich stažení použijte vygenerované osobní číslo a heslo, které jste obdrželi mailem na začátku listopadu
- Záznamy můžete použít pouze pro osobní studijní potřebu a nesmíte je jakýmkoli způsobem zveřejňovat nebo jinak šířit
- Evidence bodů
- Materiály na cvičení
Plán cvičení
- Čtvrtek 23. 09. 2021: 01 - Formální jazyky, Chomského hierarchie, gramatiky, jazykové operace nad BG (sjednocení, součin, iterace), derivační stromy
- Čtvrtek 30. 09. 2021: 02 - Intuitivní návrh gramatik (regulární, bezkontextové, kontextové, neomezené)
- Čtvrtek 07. 10. 2021: 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 14. 10. 2021: 04 - Determinizace NKA, minimalizace DKA, jazykové operace nad KA (sjednocení, průnik, doplněk, součin, iterace)
- Čtvrtek 21. 10. 2021: 05 - Regulární výrazy, návrh RV, zjednodušování RV, pravé a levé regulární rovnice, soustavy RR, derivace RV
- Čtvrtek 28. 10. 2021: Zrušeno (Den vzniku samostatného československého státu)
- Čtvrtek 04. 11. 2021: 06 - Převody RG->KA (metoda přímé transformace), KA->RG (metoda přímé transformace), RV->KA (metoda derivací), RV->KA/RG (metoda sousedů), RV->KA (metoda postupné konstrukce)
- Čtvrtek 11. 11. 2021: 07 - Převody KA->RV (metody levých a pravých RR, metoda eliminace), RG->RV (metoda pravých RR, metoda eliminace neterminálů), RV->RG (metoda derivací)
- Čtvrtek 18. 11. 2021: 08 - Pumping lemma, důkazy neregulárnosti jazyků
- Čtvrtek 25. 11. 2021: 09 - Důkazy neregulárnosti jazyků, Myhillova-Nerodova věta
- Čtvrtek 02. 12. 2021: 10 - 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, algoritmus CYK
- Čtvrtek 09. 12. 2021: Zápočtový test
- Čtvrtek 16. 12. 2021: 11 - Zásobníkové automaty, intuitivní návrh ZA, syntaktická analýza (metody shora dolů, zdola nahoru)
- 12 - Formální překlady, intuitivní návrh KPA, ZPA, RPG, BPG, transformace BPG na ZPA
- 13 - 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í)
Starší záznamy
- Cvičení 01 - Záznam (52 MB) - Jazyky, gramatiky, hierarchie
- Cvičení 02 - Záznam (106 MB) - RG, BG, KG
- Cvičení 03 - Záznam (169 MB) - DKA, NKA, dosažitelné, užitečné
- Cvičení 04 - Záznam (165 MB) - KA: determinizace, minimalizace, sjednocení, průnik
- Cvičení 05 - Záznam (163 MB) - KA: doplněk, součin, iterace; RV, RR
- Cvičení 06 - Záznam (155 MB) - Soustavy RR, derivace RV; RG->KA (transformace), KA->RG (transformace), RV->KA/RG (sousedé)
- Cvičení 07 - Záznam (157 MB) - RV->KA (derivace), RV->KA (konstrukce), KA->RV (LRR, PRR, eliminace), RG->RV (PRR, eliminace)
- Cvičení 08 - Záznam (153 MB) - RV->RG (derivace); PL
- Cvičení 09 - Záznam (178 MB) - PL, MNV
- Cvičení 10 - Záznam (175 MB) - BG: jednoznačnost, prázdnost, negenerující, nedostupné, epsilonová, jednoduchá, CNF, levá rekurze
- Cvičení 11 - Záznam (196 MB) - CYK; ZA, SA
- Cvičení 12 - Záznam (152 MB) - KPA, ZPA, RPG, BPG
- Cvičení 13 - Záznam (215 MB) - DTS, NTS; P, NP, polynomiální redukce, NP-těžké, NP-úplné; kachlíkování