Formálne jazyky a automaty
(zimný 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
1. 12. 2016Termín veľkej písomky bol stanovený na pondelok 12. decembra 2016 o 14:00. Písať sa bude v miestnosti F1. Na písomke sa môžu objaviť úlohy ku ktorejkoľvek z tém preberaných v rámci prvých jedenástich prednášok a prvých dvanástich cvičení (vrátane tém zo sady úloh na trináste cvičenie), predovšetkým by však malo ísť o úlohy zodpovedajúce nasledujúcim okruhom:
  • Slová, jazyky a operácie na nich (vrátane homomorfizmov). Úlohy na porovnanie dvojíc jazykov.
  • Bezkontextové gramatiky (definícia, konštrukcie, dôkazy správnosti, ...).
  • Normálne tvary bezkontextových gramatík (redukovaný, Chomského, bezepsilonový).
  • Deterministické konečné automaty (definícia, konštrukcie, dôkazy správnosti, ...).
  • Nedeterministické konečné automaty (definícia, konštrukcie, dôkazy správnosti, ...).
  • Štandardné konštrukcie pre konečné automaty (odepsilonovanie NKA, determinizácia NKA, ...).
  • Ekvivalencia konečných automatov a regulárnych gramatík (prevod z konečného automatu na regulárnu gramatiku a opačne).
  • Pumpovacia lema pre regulárne jazyky a jej použitie na dokazovanie negatívnych výsledkov o regularite jazykov.
  • Uzáverové vlastnosti triedy regulárnych jazykov (poznať štandardné a vedieť zisťovať neštandardné).
  • Zásobníkové automaty (definícia, konštrukcie, ...).
  • Ekvivalencia zásobníkových automatov a bezkontextových gramatík (prevod zo zásobníkového automatu na bezkontextovú gramatiku a opačne).
  • Pumpovacia lema pre bezkontextové jazyky a jej použitie na dokazovanie negatívnych výsledkov o bezkontextovosti jazykov.
  • Uzáverové vlastnosti triedy bezkontextových jazykov (poznať štandardné a vedieť zisťovať neštandardné).
  • Deterministické a nedeterministické Turingove stroje (definícia, konštrukcie, ...).
  • Ekvivalencia deterministických Turingových strojov, nedeterministických Turingových strojov a frázových gramatík (predovšetkým o nej vedieť).
  • Uzáverové vlastnosti triedy rekurzívne vyčísliteľných jazykov (poznať štandardné a vedieť zisťovať neštandardné).
  • Rozhodnuteľnosť (definície, dôkazy pomocou redukcií, ...).
30. 11. 2016Medzi zadaniami domácich úloh pribudla piata sada bodovaných domácich úloh. Riešenia treba odovzdať do stredy 14. decembra 2016, 12:00 SEČ do krabice, ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254).
30. 11. 2016Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 12 a medzi materiálmi pribudli poznámky k cvičeniu č. 11.

[ zobraz všetky oznamy ]