Automaty a formálne jazyky

Organizácia predmetu

Prednáška a cvičenie:

• Prednáška: Utorok 15:00 – 16:40, AB-150.
• Cvičenie: Štvrtok 13:00 – 14:40, CD-150.

Konzultácie:

Konzultačné hodiny po dohode mailom

Podmienky absolvovania

Študentstvo absolvuje:

• 4 zadania. Každé zadanie je za 10 bodov, t.j. súhrnne za 4 zadania je možné získať 40 bodov.

To znamená, že počas semestra môže študentstvo získať súhrnne 40 bodov za všetky zadania. Podmienkou pre vykonanie skúšky je zisk minimálne 20 bodov zo zadaní.

Študentstvo, ktoré splní podmienky pre vykonanie skúšky (t.j. získa zo zadaní súhrnne minimálne 20 bodov) následne absolvuje 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.

Dávam do pozornosti študijný poriadok STU, konkrétne, čl. 13, odsek (5):

(5) Preukázaná nečestnosť študenta pri hodnotení študijných výsledkov (zistenie opisovania, podvádzanie, použitie nedovolených pomôcok a iných praktík vrátane
nedovolenej spolupráce počas písomného alebo ústneho overovania vedomostí študenta, plagiátorstvo a pod.) má za následok neúspešné absolvovanie predmetu (čl. 16 študijného poriadku). Takéto konanie študenta je porušenie zásad študijnej morálky a môže byť predmetom disciplinárneho konania.

Podmienky absolvovania predmetu sú zverejnené aj v Akademickom informačnom systéme na príslušnom Dokumentovom serveri predmetu. Ten istý dokument nájdete aj tu.

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.