Automaty a formálne jazyky

Kategória predmetu:1Ing - LS, Ing

Organizácia

Študijné materiály

Doplnkové materiály

Organizácia predmetu

Prvý test:

Prvý test z predmetu Automaty a formálne jazyky sa uskutoční dňa 7.4. (pondelok) v čase prednášky, t.j. 15:00 – 16:40 v miestnosti AB-150. Náplňou testu bude látka odprednášaná do dňa konania testu, t.j. z prvých siedmich týždňov semestra.

Prednáška a cvičenie:

Prednáška: Pondelok 15:00 – 16:40, AB-150.
Cvičenie: Utorok 13:00 – 14:40, DE-300.

Konzultácie:

Konzultačné hodiny po dohode mailom.

Podmienky absolvovania

Študentstvo absolvuje:

Dva písomné testy, každý test je za 20 bodov, t.j. súhrnne za 2 testy je možné získať 40 bodov,
pričom podmienkou pre účasť na skúške je získať z oboch testov dokopy aspoň 20 bodov.
Písomnú skúšku, 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.

Cieľ predmetu

Cieľom predmetu AFJ je, aby študentstvo získalo 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 študentstvo bolo schopné samostatne študovať práce využívajúce základné poznatky z teoretickej informatiky, aby rozumelo lexikálnej, syntaktickej a sémantickej analýze programu v počítači.

Plán semestra

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

Prednášky

1. 17.2.2025, Formálne jazyky, gramatiky.

2. + 3., 24.2.2025 + 3.3.2025 Konečné automaty deterministické a nedeterministické, konverzia NKA -> DKA.

4. 10.3.2025, prednáška odpadla.

5. 17.3.2025, Regulárne výrazy, vlastnosti regulárnych jazykov.

6. 24.3.2025, Bezkontextové gramatiky, derivačné stromy, jednoznačnosť, transformácie gramatík.

7. 31.3.2025, Zásobníkové automaty.

8. 7.4.2025, Prvý test.

Cvičenia

1. 18.2.2025, Formálne jazyky, gramatiky.
Ďalšie príklady na danú tému môžete nájsť tu.

2. + 3., 25.2.2025 + 4.3.2025 Konečné automaty deterministické a nedeterministické, konverzia NKA -> DKA.
Ďalšie príklady na danú tému môžete nájsť tu.

4. 11.3.2025, cvičenie odpadlo.

5. 18.3.2025, Regulárne výrazy, vlastnosti regulárnych jazykov.
Ďalšie príklady na danú tému môžete nájsť tu.

6. 25.3.2025, Transformácie gramatík, derivačné stromy.
Ďalšie príklady na danú tému môžete nájsť tu.

7. 1.4.2025, Zásobníkové automaty.
Ďalšie príklady na danú tému môžete nájsť tu.

8. 8.4.2025, cvičenie nebude z dôvodu študijného voľna (ŠVOČ).

Literatúra

Aho, A., Lam, M., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques and Tools, 2006.
- Legenda v oblasti prekladačov a kompilátorov, tzv. Dragon-book. Dá sa voľne nájsť na webe, napríklad tu: https://repository.unikom.ac.id/48769/1/Compilers%20-%20Principles,%20Techniques,%20and%20Tools%20(2006).pdf
Dedera, Ľ.: Počítačové jazyky a ich spracovanie, AOS M.R.Štefánika Liptovský Mikuláš, 2014.
- Základná literatúra pre tento predmet. Na webe sa dá nájsť pravdepodobne jej pre-printová verzia. Síce je formátovaná vo Worde, čo nemusí byť úplne oku-lahodiace, ale pravdepodobne pokrýva všetko to, čo je potrebné: https://studentiext.files.wordpress.com/2015/03/prekladac48de-dedera.pdf
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation, 3rd Ed.
- The men, the myth, the legend. Absolútne esenciálna literatúra z oblasti formálnych jazykov, automatov a vypočítateľnosti. Presah aj do teórie zložitosti. Táto kniha JE informatika a informatika JE táto kniha. https://lecture-notes.tiu.edu.iq/wp-content/uploads/2022/02/Introduction-to-Automata-Theory-Languages-and-Computations-by-John-E.-Hopcroft-Rajeev-Motwani-Jeffrey-D.-Ullman-z-lib.org_.pdf
Hromada, V.: ZBIERKA RIEŠENÝCH ÚLOH Z PREDMETU AUTOMATY A FORMÁLNE JAZYKY, Spektrum STU, Bratislava, 2023.
- Zbierka jednoduchých riešených úloh s komentárom na vysvetlenie konceptov. Meh.
Molnár, Ľ., Češka, M., Melichar, B.: Gramatiky a jazyky. ALFA/SNTL, Bratislava, 1987.
- Domáca rokmi overená klasika. Nejaký úžasný dobrodinec dal jej oskenovanú verziu na archive.org, sťahujte, kým sa dá, a.k.a. „Zťahujte kím nesmaźú“, https://archive.org/download/gramatiky-a-jazyky-molnar-et.-al.-alfa-1987/Gramatiky%20a%20jazyky%2C%20Molnar%20et.%20al.%2C%20Alfa%201987_text.pdf

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í…

Alternatívne je k dispozícii napríklad nasledovná softvérová pomôcka, ktorá tiež dokáže konštruovať LL(1), SLR(1), LALR(1), LR(1) parsery. http://www.supereasyfree.com/software/simulators/compilers/principles-techniques-and-tools/parsing-simulator/parsing-simulator.zip

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/