Automaty a formálne jazyky

Skúšanie AFJ

Prvý test z predmetu AFJ sa uskutoční 12.4. 2021 od 11:00 v Akademickom informačnom systéme. Náplňou testu bude látka dovtedy odprednášaná, t.j. učivo z prvých siedmych týždňov semestra.

Druhý test z predmetu AFJ sa uskutoční 10.5. 2021 od 11:00 v Akademickom informačnom systéme. Náplňou testu bude látka odprednášaná po prvom teste, t.j. učivo z týždňov semestra medzi prvým a druhým testom.

Riadny termín skúšky z predmetu AFJ sa uskutoční 17.5.2021 od 10:00 v Akademickom informačnom systéme. Náplňou testu bude látka odprednášaná počas celého semestra.

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

Organizácia predmetu

Prednáška a cvičenie:
  • Prednášky: Pondelok, 09:00 – 10:40, AB150 (miestnosť v prípade prezenčnej výuky)
  • Cvičenia: Pondelok, 11:00 – 12:40, AB150 (miestnosť v prípade prezenčnej výuky)
Dištančná forma výuky:

Počas dištančnej formy výuky budú prednášky a cvičenia prebiehať 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 2020/2021“ 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.

Konzultácie:

Konzultačné hodiny po dohode mailom

Podmienky absolvovania

Testy: 40 bodov (2 x 20 bodov)
Písomná skúška: 60 bodov

Na pustenie ku skúške (po starom „získanie zápočtu“) je potrebné získať minimálne 20 bodov v priebehu semestra.

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

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, 15.2.2021. Úvod do formálnych jazykov, gramatiky.

Prednáška č. 2, 22.2.2021. Konečné automaty, DKA, NKA, ich ekvivalencia.

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

Prednáška č. 4, 8.3.2021. Derivačný strom, redukovaná gramatika, odstránenie epsilon-pravidla.

Prednáška č. 5, 15.3.2021. Odstránenie jednoduchého pravidla, Chomského normálny tvar, CYK algoritmus.

Prednáška č. 6, 22.3.2021. FIRST, FOLLOW.

Prednáška č. 7, 29.3.2021. Zásobníkové automaty.

Prednáška č. 8 19.4.2021, Lexikálna analýza.

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

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

Cvičenia

Cvičenie č. 1, 15.2.2021. Úvod do formálnych jazykov, gramatiky.

Cvičenie č. 2, 22.2.2021. Konečné automaty, DKA, NKA, ich ekvivalencia.

Cvičenie č. 3, 1.3.2021. Regulárne výrazy, konverzia Regex -> NKA.

Cvičenie č. 4, 8.3.2021. Derivačný strom, redukovaná gramatika, odstránenie epsilon-pravidla.

Cvičenie č. 5, 15.3.2021. Odstránenie jednoduchého pravidla, Chomského normálny tvar, CYK algoritmus.

Cvičenie č. 6, 22.3.2021. FIRST, FOLLOW.

Cvičenie č. 7, 29.3.2021. Zásobníkové automaty.

Cvičenie č. 8, 26.4.2021. LL(1) analyzátory.

Cvičenie č. 9, 3.5.2021. LR(0) analyzátor.

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 ktorý je možné stiahnuť z tejto stránky: http://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/

Zaujímavá hra

Vážení študenti! Pre skrátenie dlhých chvíľ medzi prednáškami – hra aj s prvkami konečných automatov: http://pleasingfungus.com/Manufactoria/

Ďakujem Ing. Jakubovi Kovářovi za link!