BI-AAG: Automaty a gramatiky
Základní informace
- Web předmětu
- Rozvržení hodin
Cvičení 11: čtvrtek 12:45 - 14:15 (TH:A-942)
Cvičení 12: čtvrtek 14:30 - 16:00 (TH:A-942)
Cvičení 14: čtvrtek 16:15 - 17:45 (TH:A-942)
Cvičení 16: čtvrtek 18:00 - 19:30 (TH:A-942)
- Všechna cvičení jsou od 24. 9. 2020 až do odvolání vyučována online přes platformu Zoom
- Rozvrh online cvičení od 8. 10. 2020
- Čtvrtek 12:45 - 14:15
- Čtvrtek 14:30 - 16:00
- Čtvrtek 16:15 - 17:45
- Záznamy cvičení
- Zaznamenaná cvičení jsou dostupná pod uživatelským jménem student a stejným heslem jako pro přístup k online cvičením
- Tyto záznamy mohou být použity pouze pro osobní studijní potřebu a nesmí být jakýmkoli způsobem zveřejňovány nebo jinak šířeny
- 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, např. tedy 1234.pdf)
- 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
- Evidence bodů
- Materiály na cvičení
Plán cvičení
- Čtvrtek 24. 09. 2020: 01 - Formální jazyky, Chomského hierarchie, gramatiky, jazykové operace nad BG (sjednocení, součin, iterace), derivační stromy
- Čtvrtek 01. 10. 2020: 02 - Intuitivní návrh gramatik (regulární, bezkontextové, kontextové, neomezené)
- Čtvrtek 08. 10. 2020: 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 15. 10. 2020: 04 - Determinizace NKA, minimalizace DKA, jazykové operace nad KA (sjednocení, průnik, doplněk, součin, iterace)
- Čtvrtek 22. 10. 2020: 05 - Regulární výrazy, návrh RV, zjednodušování RV, pravé a levé regulární rovnice, soustavy RR, derivace RV
- Čtvrtek 29. 10. 2020: 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 05. 11. 2020: 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 12. 11. 2020: 08 - Pumping lemma, důkazy neregulárnosti jazyků
- Čtvrtek 19. 11. 2020: Změna rozvrhu (výuka probíhá jako v liché pondělí)
- Čtvrtek 26. 11. 2020: 09 - Důkazy neregulárnosti jazyků, Myhill-Nerodova věta
- Čtvrtek 03. 12. 2020: 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 10. 12. 2020: 11 - Zásobníkové automaty, intuitivní návrh ZA, syntaktická analýza (metody shora dolů, zdola nahoru)
- Čtvrtek 17. 12. 2020: 12 - Formální překlady, intuitivní návrh KPA, ZPA, RPG, BPG, transformace BPG na ZPA
Úterý 22. 12. 2020 Pátek 18. 12. 2020 (16:15): 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í)
Záznamy cvičení
- 24. 09. 2020: 01 - Video (52 MB) - Poznámky - Jazyky, gramatiky, hierarchie
- 01. 10. 2020: 02 - Video (106 MB) - Poznámky - RG, BG, KG
- 08. 10. 2020: 03 - Video (169 MB) - Poznámky - DKA, NKA, dosažitelné, užitečné
- 15. 10. 2020: 04 - Video (165 MB) - Poznámky - KA: determinizace, minimalizace, sjednocení, průnik
- 22. 10. 2020: 05 - Video (163 MB) - Poznámky - KA: doplněk, součin, iterace; RV, RR
- 29. 10. 2020: 06 - Video (155 MB) - Poznámky - Soustavy RR, derivace RV; RG->KA (transformace), KA->RG (transformace), RV->KA/RG (sousedé)
- 05. 11. 2020: 07 - Video (157 MB) - Poznámky - RV->KA (derivace), RV->KA (konstrukce), KA->RV (LRR, PRR, eliminace), RG->RV (PRR, eliminace)
- 12. 11. 2020: 08 - Video (153 MB) - Poznámky - RV->RG (derivace); PL
- 26. 11. 2020: 09 - Video (178 MB) - Poznámky - PL, MNV
- 03. 12. 2020: 10 - Video (175 MB) - Poznámky - BG: jednoznačnost, prázdnost, negenerující, nedostupné, epsilonová, jednoduchá, CNF, levá rekurze
- 10. 12. 2020: 11 - Video (196 MB) - Poznámky - CYK; ZA, SA
- 17. 12. 2020: 12 - Video (152 MB) - Poznámky - KPA, ZPA, RPG, BPG
- 18. 12. 2020: 13 - Video (215 MB) - Poznámky - DTS, NTS; P, NP, polynomiální redukce, NP-těžké, NP-úplné; kachlíkování