Formálne jazyky a automaty
(letný semester 2016/2017)

[ oznamy ]
[ rozvrh ]
[ pravidlá ]
[ domáce úlohy ]
[ riešenia ]
[ hodnotenie ]
[ materiály ]
[ odkazy ]
[ TeX ]
[ kontakt ]

Prihlásenie

Meno:
Heslo:

Oznamy

pridané dňaoznam
16. 5. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 14 a medzi materiálmi pribudla druhá časť poznámok k syntaktickej analýze zdola nahor.
9. 5. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 13.
2. 5. 2017Termín veľkej písomky bol stanovený na pondelok 29. mája 2017 o 10:00. Písať sa bude v miestnosti M-III. Na písomke sa môžu objaviť úlohy ku ktorejkoľvek z tém precvičených počas tohto semestra, predovšetkým by však malo ísť o úlohy zodpovedajúce nasledujúcim okruhom:
  • Myhillova-Nerodova veta a jej použitie (sprava invariantné relácie ekvivalencie a ich vzťah k DKA, pravá syntaktická ekvivalencia a jej vzťah k minimálnemu DKA, dokazovanie minimality DKA, vyvracanie regulárnosti pomocou Myhillovej-Nerodovej vety, ...).
  • A-prekladače (definícia, charakterizácia pomocou homomorfizmu, inverzného homomorfizmu a prieniku s regulárnym jazykom, konštrukcie a-prekladačov, (ne)uzavretosť známych tried jazykov na zobrazenie a-prekladačom, dokazovanie neexistencie a-prekladačov pomocou uzáverových vlastností, ...).
  • Substitúcie (definícia, (ne)uzavretosť známych tried jazykov na substitúciu, ...).
  • Greibachovej normálny tvar (definícia, štandardná konštrukcia, vedieť o existencii bezepsilonových PDA, ...).
  • Ogdenova lema a jej použitie.
  • (Rozšírené) kontextové jazyky (definície LBA a kontextových gramatík, konštrukcie, ...).
  • Uzáverové vlastnosti kontextových jazykov (poznať známe vlastnosti vrátane charakterizácie rekurzívne vyčísliteľných jazykov pomocou homomorfných obrazov kontextových jazykov a Szelepcsényiho vety + vedieť dokazovať a vyvracať uzavretosť na neštandardné operácie).
  • Definícia turingovskej redukcie a rovnako ťažkých problémov (stačí neformálne).
  • Postov korešpondenčný problém a jeho varianty (nerozhodnuteľnosť PKP a MPKP, štandardná redukcia MPKP na PKP, vedieť vymýšľať vlastné redukcie pre neštandardné varianty PKP, ...).
  • Rozhodnuteľnosť vlastností jazykov tried Chomského hierarchie (poznať štandardné výsledky a vedieť dokazovať/vyvracať rozhodnuteľnosť neštandardných problémov).
  • Jazyky zodpovedajúce prípadom PKP (ich vlastnosti, použitie pri redukciách, ...).
  • Odstraňovanie reťazových pravidiel a prísny Chomského normálny tvar (štandardné konštrukcie).
  • Algoritmus CYK (predovšetkým vedieť ho odsimulovať na danom vstupe).
  • Riceove vety a ich použitie.
  • Preklad a jednoduché prekladové schémy (definície, konštrukcie, dôkazy neexistencie, ...).
  • Deterministické zásobníkové automaty (definície, konštrukcie, dôkazy neexistencie, DPDA akceptujúce prázdnym zásobníkom, ...).
  • Operácie MIN a MAX (vedieť ich definície).
  • Uzáverové vlastnosti deterministických bezkontextových jazykov (poznať známe vlastnosti vrátane uzavretosti na operácie MIN a MAX + vedieť dokazovať (ne)uzavretosť na neštandardné operácie).
  • Rozhodnuteľnosť vlastností deterministických bezkontextových jazykov (poznať štandardné výsledky a vedieť dokazovať/vyvracať rozhodnuteľnosť neštandardných problémov).
  • Syntaktická analýza zdola nahor (poznať základné pojmy, ...).
  • Jednoducho precedenčné gramatiky (definície, výpočet precedenčných relácií, overovanie jednoduchej precedenčnosti, posuň a redukuj, ...).
  • LR(0) gramatiky (definície, konštrukcie položkových automatov, vedieť zistiť, či je gramatika LR(0), posuň a redukuj, ...).
  • Vedieť o LR(k) gramatikách a o vzťahu LR gramatík k deterministickým zásobníkovým automatom.
2. 5. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 12 a medzi materiálmi pribudla prvá časť poznámok k syntaktickej analýze zdola nahor.
25. 4. 2017Pribudli riešenia druhej sady bodovaných domácich úloh.
25. 4. 2017Medzi zadaniami domácich úloh pribudla tretia sada bodovaných domácich úloh (za 12 bodov). Riešenia treba odovzdať do utorka 23. mája 2017, 16:00 SELČ do krabice, ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254).
25. 4. 2017Medzi zadaniami domácich úloh pribudli dve prémiové úlohy. Body za každú z nich môžu získať prví desiati, ktorí do 23. mája 2017, 23:59:59 SELČ mailom odovzdajú správne (alebo takmer správne) riešenie.
25. 4. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 11 a medzi materiálmi pribudli poznámky k deterministickým zásobníkovým automatom.
20. 4. 2017Pribudli riešenia úloh z malej písomky.
19. 4. 2017V utorok 25. apríla 2017 bude od 11:30 v miestnosti M-213 mimoriadna prednáška.
11. 4. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 10 a medzi materiálmi pribudli poznámky k prekladu.
10. 4. 2017Termín malej písomky bol stanovený na štvrtok 20. apríla 2017 o 8:10. Písať sa bude v miestnosti F1-328. Na písomke sa môžu objaviť úlohy ku ktorejkoľvek z tém precvičených v rámci prvých ôsmich cvičení, predovšetkým by však malo ísť o úlohy zodpovedajúce nasledujúcim okruhom:
  • Myhillova-Nerodova veta a jej použitie (sprava invariantné relácie ekvivalencie a ich vzťah k DKA, pravá syntaktická ekvivalencia a jej vzťah k minimálnemu DKA, dokazovanie minimality DKA, vyvracanie regulárnosti pomocou Myhillovej-Nerodovej vety, ...).
  • A-prekladače (definícia, charakterizácia pomocou homomorfizmu, inverzného homomorfizmu a prieniku s regulárnym jazykom, konštrukcie a-prekladačov, (ne)uzavretosť známych tried jazykov na zobrazenie a-prekladačom, dokazovanie neexistencie a-prekladačov pomocou uzáverových vlastností, ...).
  • Substitúcie (definícia, (ne)uzavretosť známych tried jazykov na substitúciu, ...).
  • Greibachovej normálny tvar (definícia, štandardná konštrukcia, vedieť o existencii bezepsilonových PDA, ...).
  • Ogdenova lema a jej použitie.
  • (Rozšírené) kontextové jazyky (definície LBA a kontextových gramatík, konštrukcie, ...).
  • Uzáverové vlastnosti kontextových jazykov (poznať známe vlastnosti vrátane charakterizácie rekurzívne vyčísliteľných jazykov pomocou homomorfných obrazov kontextových jazykov a Szelepcsényiho vety + vedieť dokazovať a vyvracať uzavretosť na neštandardné operácie).
  • Definícia turingovskej redukcie a rovnako ťažkých problémov (stačí neformálne).
  • Postov korešpondenčný problém a jeho varianty (nerozhodnuteľnosť PKP a MPKP, štandardná redukcia MPKP na PKP, vedieť vymýšľať vlastné redukcie pre neštandardné varianty PKP, ...).
  • Rozhodnuteľnosť vlastností jazykov tried Chomského hierarchie (poznať štandardné výsledky a vedieť dokazovať/vyvracať rozhodnuteľnosť neštandardných problémov).
  • Jazyky zodpovedajúce prípadom PKP (ich vlastnosti, použitie pri redukciách, ...).
  • Odstraňovanie reťazových pravidiel a prísny Chomského normálny tvar (štandardné konštrukcie).
  • Algoritmus CYK (predovšetkým vedieť ho odsimulovať na danom vstupe).
  • Riceove vety a ich použitie.
4. 4. 2017Medzi zadaniami domácich úloh pribudla druhá sada bodovaných domácich úloh (za 12 bodov). Riešenia treba odovzdať do utorka 25. apríla 2017, 16:00 SELČ do krabice, ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254).
4. 4. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 8 a medzi materiálmi pribudli poznámky k Riceovým vetám.
28. 3. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 7 a medzi materiálmi pribudli poznámky k algoritmu CYK.
21. 3. 2017Pribudli riešenia prvej sady bodovaných domácich úloh.
21. 3. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 6 a medzi materiálmi pribudli poznámky k Postovmu korešpondenčnému problému a k redukciám.
14. 3. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 5.
7. 3. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 4 a medzi materiálmi pribudli poznámky ku Greibachovej normálnemu tvaru.
28. 2. 2017Medzi zadaniami domácich úloh pribudla prvá sada bodovaných domácich úloh. Riešenia treba odovzdať do utorka 21. marca 2017, 16:00 SEČ do krabice, ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254).
28. 2. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 3 a medzi materiálmi pribudli poznámky k Myhillovej-Nerodovej vete.
21. 2. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 2 a medzi materiálmi pribudli poznámky k a-prekladačom a k substitúciám.
20. 2. 2017Prihlasovanie na tejto stránke je pre letný semester otvorené. Východzie heslo je buď rovnaké ako minulý semester (študenti, ktorí absolvovali prvý semester tento akademický rok), alebo neutrálne vo voľnom monoide (ostatní študenti).