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

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!