Automaty a formálne jazyky

Dôležité

Upozorňujem, že na základe pokynov z vedenia ÚIM bude riadny / opravný termín skúšky z AFJ prezenčný!

Opravný termín skúšky sa uskutoční 20.6. o 14:00 v miestnosti AB-300. Bližšie informácie nájdete nižšie.

Riadny termín skúšky sa uskutoční 6.6. o 14:00 v miestnostiach AB-300, BC-300, AB-150. Bližšie informácie o skúške nájdete nižšie.

Dňa 25. apríla 2022 sa o 9:00 uskutoční druhý test z predmetu AFJ. Test bude za 20 bodov a bude realizovaný cez AIS. Náplňou testu bude látka z prednášok a cvičení č. 5, 6, 7, 8, t.j. bezkontextové gramatiky, derivačné stromy, redukované gramatiky, množiny FIRST,FOLLOW, zásobníkové automaty a lexikálna analýza.

Dňa 21. marca 2022 sa o 9:00 uskutoční prvý test z predmetu AFJ. Test bude za 20 bodov a bude realizovaný cez AIS. Náplňou testu bude látka z prvých 4 prednášok a cvičení, t.j. gramatiky, DKA, NKA a regulárne výrazy.

Z dôvodu udelenia rektorského voľna https://www.stuba.sk/sk/diani-na-stu/prehlad-aktualit/rektorske-volno-2.html?page_id=14770 sa prednáška/cvičenie 21. februára 2022 neuskutoční! Ďalšia prednáška a cvičenie teda budú 28.februára 2022 v štandardnom čase.

Prednášajúci:Viliam Hromada
Cvičiaci:Viliam Hromada
Linky:IS Sylabus
Kategória predmetu:,
Organizácia
Študijné materiály
Doplnkové materiály

Opravný termín skúšky, 20. 6. 2022, 14:00:

  • Náplňou skúšky bude problematika z celého semestra.
  • Skúška bude organizovaná v podstate formou testu, kde budete priamo vpisovať odpovede.
  • Na skúšku budete mať 60 minút.
  • Na skúške nie je dovolené používať žiadne ťaháky / materiály / mobily, počítače, tablety a čo ja viem ešte aké elektronické a mechanicko-elektronické zariadenia. Samozrejme akákoľvek forma komunikácie s inými študentkami/študentami je počas skúšky zakázaná.
  • Skúška bude v rovnakom formáte ako riadny termín, v MS Teams nájdete vzor, ako bude skúška vyzerať.
  • Skúška sa bude písať v miestnosti AB-300.
  • Len pripomínam, že podmienkou pre pripustenie na skúšku je súhrnný zisk aspoň 20 bodov z 2 zápočtových testov, ktoré boli počas semestra.
  • Na skúšku môžu ísť taktiež tie študentky/tí študenti, ktoré/ktorí už na riadnom termíne získali známku lepšiu ako FX – t.j. môžu si ísť „opraviť“ známku. Upozorňujem, že v takom prípade to znamená, že neprijímate výsledok riadneho termínu skúšky (študijný poriadok, čl. 15, ods. (9)), riadny termín vám bude spätne ohodnotený ako FX a bude sa vám rátať známka z opravného termínu. V prípade, že chcete využiť túto možnosť, prosím, informujte ma o tom mailom najneskôr deň pred skúškou, aby som si vedel pripraviť dostatočný počet zadaní na skúšku.

Riadny termín skúšky, 6. 6. 2022, 14:00:

  • Náplňou skúšky bude problematika z celého semestra.
  • Skúška bude organizovaná v podstate formou testu, kde budete priamo vpisovať odpovede.
  • Na skúšku budete mať 60 minút.
  • Na skúške nie je dovolené používať žiadne ťaháky / materiály / mobily, počítače, tablety a čo ja viem ešte aké elektronické a mechanicko-elektronické zariadenia. Samozrejme akákoľvek forma komunikácie s inými študentkami/študentami je počas skúšky zakázaná.
  • V MS Teams nájdete vzor, ako bude skúška vyzerať.
  • Skúška sa bude písať v troch miestnostiach: AB-300, BC-300, AB-150. Tu nájdete rozdelenie do jednotlivých miestností. Každá študentka/každý študent teda bude mať pridelenú miestnosť, v ktorej bude skúšku písať.
  • Len pripomínam, že podmienkou pre pripustenie na skúšku je súhrnný zisk aspoň 20 bodov z 2 zápočtových testov, ktoré boli počas semestra.

Organizácia predmetu

Prednáška a cvičenie:
  • Prednáška: Pondelok 9:00 – 10:40. V prípade prezenčnej výuky sa bude prednáška konať v miestnosti AB-150.
  • Cvičenie: Pondelok 11:00 – 12:40. V prípade prezenčnej výuky sa bude cvičenie konať v miestnosti AB-150.
Dištančná forma výuky:

Počas dištančnej formy výuky budú prednášky a cvičenia prebiehať vo vyššie uvedených časoch formou videokonferenčných hovorov na platforme MS Teams. Je preto potrebné, aby ste mali vytvorené študentské kontá. Informácie o vytvorení konta nájdete na príslušnej stránke univerzity.

Po vytvorení konta je možné sa prihlásiť do tímu „Automaty a formálne jazyky LS 2021/2022“ na platforme MS Teams dvomi spôsobmi:

Videozáznam z každej prednášky / cvičenia bude zverejnený na YouTubovom kanáli prednášajúceho. Upozorňujem teda, že každá prednáška/cvičenie bude zaznamená. Ak s tým niekto nesúhlasí, prosím napíšte mi.

Konzultácie:

Konzultačné hodiny po dohode mailom

Podmienky absolvovania

Z dôvodu dištančnej výuky je priebežné hodnotenie študentov počas semestra nasledovné. Študenti absolvujú:

  • 2 testy. Každý test je za 20 bodov, t.j. súhrnne za 2 testy je možné získať 40 bodov.

To znamená, že počas semestra môžu študenti získať súhrnne 40 bodov. Na pustenie ku skúške (po starom „získanie zápočtu“) je potrebné z týchto 40 bodov získať minimálne 20 bodov.

Študenti, ktorí budú pripustení ku skúške (t.j. získajú z testov súhrnne minimálne 20 bodov) následne absolvujú skúšku z predmetu, ktorá je ohodnotená 60 bodmi. Výsledná známka z predmetu je tvorená na základe súčtu bodov získaných na skúške a zo spomínaných testov.  Jej výsledná hodnota je určená podľa platnej klasifikačnej stupnice STU.

Upozorňujem, že v zmysle platného študijného poriadku FEI STU je účasť na všetkých formách výuky na FEI STU povinná. Preto môže byť z dôvodu sledovania účasti na prednáškach/cvičeniach robená „prezenčka“.

Taktiež upozorňujem na platný študijný poriadok STU, konkrétne, čl. 13, odsek (3):

(3) Preukázaná nečestnosť študenta pri hodnotení študijných výsledkov (zistenie opisovania, použitie nedovolených pomôcok a iných praktík, plagiátorstvo a pod.) má za následok hodnotenie klasifikačným stupňom FX – nedostatočne (čl. 16 tohto študijného poriadku). Takéto konanie je porušenie zásad študijnej morálky a môže byť predmetom disciplinárneho konania.

Cieľ predmetu

Cieľom predmetu AFJ je, aby študenti získali rozšírené znalosti ohľadom formálnych jazykov, konečných automatov, zásobníkových automatov a ich využitia pri tvorbe kompilátorov a prekladu programu do strojového jazyka. Rozšíriť ich znalosti z oblasti teoretickej informatiky. Dosiahnuť, aby študenti boli schopní samostatne študovať práce využívajúce základné poznatky z teoretickej informatiky, aby rozumeli lexikálnej, syntaktickej  a sémantickej analýze programu v počítači.

Plán semestra

  1. Jazyky a ich reprezentácia, Gramatiky.
  2. Konečné automaty a regulárne gramatiky. NKA, DKA, ich ekvivalencia.
  3. Bezkontextové gramatiky.Úpravy bezkontextových gramatík. CHNF.  Zásobníkové automaty.
  4. Štruktúra kompilátora, Lexikálna analýza, FLEX.
  5. Syntaktická analýza. CYK algoritmus.
  6. Syntaktická analýza zhora-nadol, LL(1) analyzátor.
  7. Syntaktická analýza zdola-nahor, LR(0) analyzátor, SLR(1) analyzátor, LR(1) analyzátor, LALR(1) analyzátor.
  8. Riešenie konfliktov pri syntaktickej analýze, GLR syntaktický analyzátor.
  9. Sémantická analýza, sémantické podprogramy.

Prednášky

Prednáška č. 1. Úvodné pojmy, gramatiky.

Prednášky č. 2 + 3. Konečné automaty. DKA/DKA a ich konverzia.

Prednáška č. 4. Regulárne výrazy, konverzia Regex -> NKA.

Prednáška č. 5. Bezkontextové gramatiky, derivačné stromy, redukovaná gramatika.

Prednáška č. 6 + 7. Množiny FIRST, FOLLOW; Zásobníkové automaty.

Prednáška č. 8. Lexikálny analyzátor.

Prednáška č. 9. Syntaktická analýza top-down, LL(1)-analyzátor.

Prednáška č. 10 + 11. Syntaktická analýza bottom-up, LR(0)-analyzátor, SLR(1)-analyzátor.

Cvičenia + sady príkladov

Cvičenie č. 1. Úvodné pojmy, gramatiky.
Doplnkové príklady k cvičeniu č. 1.

Cvičenia č. 2 + 3. Konečné automaty, DKA/NKA a ich konverzia.
Doplnkové príklady k cvičeniam č. 2 a č. 3.

Cvičenie č. 4. Regulárne výrazy, konverzia Regex -> NKA, ďalšie príklady na regulárne jazyky.
Doplnkové príklady k cvičeniu č. 4.

Cvičenie č. 5. Derivačné stromy, redukcia gramatiky.
Doplnkové príklady k cvičeniu č. 5.

Cvičenie č. 6 + 7. Množiny FIRST, FOLLOW; Zásobníkové automaty.
Doplnkové príklady k cvičeniu č. 6 a č. 7.

Cvičenie č. 8. Lexikálny analyzátor, FLEX.

Cvičenie č. 9. LL(1)-analyzátor.
Doplnkové príklady k cvičeniu č. 9.

Cvičenie č. 10 + 11. LR(0)-analyzátor.
Doplnkové príklady k cvičeniu č. 10., č. 11.

Literatúra
  • Aho, A., Lam, M., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques and Tools, 2006.
  • Dedera, Ľ.: Počítačové jazyky a ich spracovanie, AOS M.R.Štefánika Liptovský Mikuláš, 2014.
  • Hopcroft, J.E., Ullman, J.D.: Formálne jazyky a automaty. ALFA, Bratislava, 1978.
  • Linz, P.: An Introduction to Formal Languages and Automata, 2001.
  • Molnár, Ľ., Češka, M., Melichar, B.: Gramatiky a jazyky. ALFA/SNTL, Bratislava, 1987.
Web stránka s analýzou gramatík

Na stránke Laboratória programovacích jazykov Katedry počitačových vied Univerzity v Calgary sa nachádza výborný softvérový nástroj pre syntaktickú analýzu gramatík. http://smlweb.cpsc.ucalgary.ca/start.html

Na stránke si viete dať zostrojiť príslušné LL/LR analyzátory pre ľubovoľné gramatiky.

Odporúčam taktiež podstránku http://smlweb.cpsc.ucalgary.ca/example-grammars/ kde sú ukážky rôznych gramatík, aj vzhľadom na ich príslušnosť/nepríslušnosť do LL(1)/LR(0)/SLR(1)/LALR(1)/LR(1)/LL(2)/LR(2) kombinácií…

Softvérová pomôcka

Pri samoštúdiu a príprave na predmet AFJ odporúčam pracovať s programom JFLAP vo verzii 7.1 ktorý je možné stiahnuť z tejto stránky: https://www.jflap.org/jflaptmp/

Autori programu zároveň zverejnili zdarma doplnkovú knihu k programu, ktorá sa dá zároveň použiť aj ako študijný materiál k predmetu AFJ: https://www2.cs.duke.edu/csed/jflap/jflapbook/