Automaty a formálne jazyky

Prednášajúci:Viliam Hromada
Cvičiaci:Viliam Hromada
Kategória predmetu:,
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.

Test sa píše v troch behoch, každý beh má 30 minút. Rozdelenie do behov.

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

  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

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.

9. 14.4.2025, Chomského normálny tvar, CYK algoritmus, FIRST a FOLLOW množiny.

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 nebolo z dôvodu študijného voľna (ŠVOČ).

9. 15.4.2025, Chomského normálny tvar, CYK algoritmus; Množiny FIRST a FOLLOW.
Ďalšie príklady na danú tému môžete nájsť tu.

Literatúra
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/