Formálne jazyky a automaty
(zimný semester 2017/2018)

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

Prihlásenie

Meno:
Heslo:

Oznamy

pridané dňaoznam
11. 1. 2018V prípade záujmu o druhú opravnú písomku treba napísať mail na adresu kostolanyi zavináč fmph a tak ďalej.
3. 1. 2018Pribudli riešenia piatej sady domácich úloh.
20. 12. 2017Pribudlo riešenie druhej prémiovej úlohy.
19. 12. 2017Pribudli riešenia štvrtej sady domácich úloh.
18. 12. 2017Termín prvej opravnej písomky bol stanovený na štvrtok 11. januára 2018 o 10:00. Písať sa bude v akváriu M-I. Na písomku sa netreba prihlasovať, stačí prísť.
18. 12. 2017Pribudlo riešenie prvej prémiovej úlohy.
15. 12. 2017Pribudli riešenia úloh z veľkej písomky.
13. 12. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 13 a medzi materiálmi pribudli poznámky k výpočtovej zložitosti.
8. 12. 2017Medzi zadaniami domácich úloh pribudla piata sada bodovaných domácich úloh. Riešenia treba odovzdať do piatku 22. decembra 2017, 09:00 SEČ do krabice, ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254).
7. 12. 2017Termíny veľkej písomky boli stanovené na piatok 15. decembra 2017 o 7:45 a o 8:45 (čas na riešenie bude na oboch termínoch 120 minút). Písať sa bude v miestnosti F1-109. Na písomke sa môžu objaviť úlohy ku ktorejkoľvek z tém preberaných v rámci prvých jedenástich cvičení (vrátane tém zo sady úloh na dvaná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ície, konštrukcie, vedieť o ekvivalencii DTS a NTS, ...).
  • Rozhodnuteľnosť a rekurzívna vyčísliteľnosť rozhodovacích problémov (definície, dôkazy pomocou redukcií, ...).
6. 12. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 12 a medzi materiálmi pribudli poznámky ku kódovaniu Turingových strojov a k rozhodnuteľnosti.
29. 11. 2017Pribudli riešenia tretej sady domácich úloh.
29. 11. 2017Medzi zadaniami domácich úloh pribudli dve prémiové úlohy. Body za každú z nich môžu získať prví desiati, ktorí do 19. decembra 2017, 23:59:59 SEČ mailom odovzdajú správne (alebo takmer správne) riešenie.
29. 11. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 11 a medzi materiálmi pribudli poznámky k cvičeniu č. 10.
24. 11. 2017Termíny veľkej písomky boli stanovené na piatok 15. decembra 2017 o 7:45 a o 8:45 (čas na riešenie bude na oboch termínoch 120 minút). Písať sa bude v miestnosti F1-109. Bližšie informácie o písomke pribudnú časom.
23. 11. 2017Medzi zadaniami domácich úloh pribudla štvrtá sada bodovaných domácich úloh. Riešenia treba odovzdať do piatku 8. decembra 2017, 10:00 SEČ do krabice, ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254).
22. 11. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 10 a medzi materiálmi pribudli poznámky k cvičeniu č. 9.
19. 11. 2017Pribudli riešenia druhej sady domácich úloh.
15. 11. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 9 a medzi materiálmi pribudli poznámky k cvičeniu č. 8.
13. 11. 2017Pribudli riešenia úloh z malej písomky.
8. 11. 2017Medzi zadaniami domácich úloh pribudla tretia sada bodovaných domácich úloh. Riešenia treba odovzdať do štvrtka 23. novembra 2017, 10:00 SEČ do krabice, ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254).
8. 11. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 8 a medzi materiálmi pribudli poznámky k cvičeniu č. 7.
2. 11. 2017Termín malej písomky bol stanovený na pondelok 13. novembra 2017 o 18:00. Písať sa bude v miestnosti B. Na písomke sa môžu objaviť úlohy ku ktorejkoľvek z tém prebratých v rámci prvých piatich cvičení (vrátane tém zo sady úloh na siedme 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, ...).
  • Odepsilonovanie nedeterministických konečných automatov.
31. 10. 2017Pribudli riešenia prvej sady bodovaných domácich úloh.
25. 10. 2017Medzi zadaniami domácich úloh pribudla druhá sada bodovaných domácich úloh. Riešenia treba odovzdať do štvrtka 9. novembra 2017, 10:00 SEČ do krabice, ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254).
25. 10. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 7 a medzi materiálmi pribudli poznámky k cvičeniu č. 5.
18. 10. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 5 a medzi materiálmi pribudli poznámky k cvičeniu č. 4.
16. 10. 2017Termín malej písomky bol stanovený na pondelok 13. novembra 2017 o 18:00. Písať sa bude v miestnosti B. Bližšie informácie o písomke pribudnú časom.
11. 10. 2017Medzi zadaniami domácich úloh pribudla prvá sada bodovaných domácich úloh. Riešenia treba odovzdať do štvrtka 26. októbra 2017, 10:00 SELČ do krabice, ktorá bude umiestnená na chodbe pred sekretariátom KI (miestnosť M-254).
11. 10. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 4 a medzi materiálmi pribudli poznámky k cvičeniu č. 3.
6. 10. 2017Ako bolo dohodnuté minule, cvičenie v stredu 11. októbra 2017 bude ešte v starom čase, čiže o 15:40 v M-VI. Od 18. októbra 2017 až do konca semestra budú stredajšie cvičenia bývať v novom termíne o 14:50 v M-VIII.
4. 10. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 3 a medzi materiálmi pribudli poznámky k cvičeniu č. 2.
27. 9. 2017Medzi zadaniami domácich úloh pribudla sada určená na cvičenie č. 2 a medzi materiálmi pribudli poznámky k cvičeniu č. 1.
25. 9. 2017Cvičenie v stredu 27. septembra 2017 o 15:40 bude aj napriek rektorskému voľnu. Účasť na tomto cvičení nie je povinná, ale je silno odporúčaná.
25. 9. 2017Všetkých študentov zapísaných na tento predmet prosíme – najmä v prípade neúčasti na úvodnom cvičení – o oboznámenie sa s pravidlami predmetu. Prihlasovanie na tejto stránke je otvorené; študenti zapísaní na predmet v AISe by mali mať vytvorené používateľské meno. V takom prípade je potrebné zmeniť si heslo, vybrať si skupinu cvičení a nastaviť e-mailovú adresu a zverejňovanie študijných výsledkov. Pre vytvorenie nového používateľa je potrebné poslať mail cvičiacemu.