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
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.

[ zobraz všetky oznamy ]