BI-AAG.21: Automaty a gramatiky
Základní informace
- Web cvičení
- Rozvržení hodin
- Cvičení 7: čtvrtek 12:45 - 14:15 (T9:301)
- Cvičení 8: čtvrtek 14:30 - 16:00 (T9:301)
- Cvičení 9: čtvrtek 16:15 - 17:45 (T9:301)
- Cvičení 10: čtvrtek 18:00 - 19:30 (T9:301)
- 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
- Evidence bodů
- Materiály na cvičení
Plán cvičení
- Čtvrtek 22. 09. 2022: 01 - Formální jazyky, Chomského hierarchie, gramatiky, jazykové operace nad BG (sjednocení, součin, iterace), derivační stromy
- Čtvrtek 29. 09. 2022: 02 - Intuitivní návrh gramatik (regulární, bezkontextové, kontextové, neomezené)
- Čtvrtek 06. 10. 2022: 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 13. 10. 2022: 04 - Determinizace NKA, minimalizace DKA, jazykové operace nad KA (sjednocení, průnik, doplněk, součin, iterace)
- Čtvrtek 20. 10. 2022: 05 - Regulární výrazy, návrh RV, zjednodušování RV, pravé a levé regulární rovnice, soustavy RR, derivace RV
- Čtvrtek 27. 10. 2022: 06 - Převody RV->KA/RG (metoda sousedů), KA->RV (metody levých a pravých RR, metoda eliminace)
- Samostudium: Záznam (98 MB) - RG->KA (metoda přímé transformace), KA->RG (metoda přímé transformace), RV->KA (metoda derivací), RV->KA (metoda postupné konstrukce), RG->RV (metoda pravých RR, metoda eliminace neterminálů), RV->RG (metoda derivací)
- Čtvrtek 03. 11. 2022: 07 - Pumping lemma, důkazy neregulárnosti jazyků
- Čtvrtek 10. 11. 2022: 08 - Důkazy neregulárnosti jazyků, Myhillova-Nerodova věta
- Čtvrtek 17. 11. 2022: Zrušeno (Den boje za svobodu a demokracii)
- Čtvrtek 24. 11. 2022: 09 - 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 01. 12. 2022: 10 - Algoritmus CYK, zásobníkové automaty, intuitivní návrh ZA, syntaktická analýza (metody shora dolů, zdola nahoru)
- Čtvrtek 08. 12. 2022: Zápočtový test
- Čtvrtek 15. 12. 2022: 11 - Formální překlady, intuitivní návrh KPA, ZPA, RPG, BPG, transformace BPG na ZPA
- Samostudium: Záznam (215 MB) - 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í)