Gramatiky a jazyky – Hashim Habiballa

Formální jazyky a gramatiky (Gramatiky a jazyky, resp. Teorie jazyků a automatů) – GRAJA/XGRJA/2GRJA/XGRAJ/2GRAJ/7GRAJ

jako doplněk lze využít také materiály ke kurzům Vyčíslitelnost a složitost a Gramatiky a jazyky (Formální jazyky a gramatiky)

Záznamy přednášek v systému Mediasite -> mediasite.prf.osu.cz

Speciální balíček multimediálních materiálů -> https://web.osu.cz/~Habiballa/files/uvdoi.zip

Požadavky na studenta

V prezenčním studiu 2 testy za celkem 60 bodů a zkouškový test za 40 bodů na konci semestru. V kombinovaném a distančním studiu 4 korespondenční úkoly za celkem 100 bodů.

Přehled probírané látky

1. Konečný automat a jazyky rozpoznatelné KA, Deterministické a nedeterministické KA, Zobecněné nedeterministické KA a třída jazyků rozpoznatelných KA
2.    Uzávěrové vlastnosti třídy jazyků rozpoznatelných KA
3.    Regulární jazyky, regulární výrazy, jejich vztah k jazykům rozpoznatelným konečnými automaty, redukce konečných automatů
4.    Bezkontextové gramatiky a jazyky, regulární gramatiky a jazyky, Nevypouštějící a redukované gramatiky, kanonická odvození, jednoznačné gramatiky, lemma o vkládání (pumping lemma)
5.    Zásobníkové automaty, vztah k bezkontextovým jazykům, Uzávěrové vlastnosti třídy bezkontextových jazyků
6.    Obecné přepisovací systémy, Chomského hierarchie, Turingovy stroje
7.    Deterministické zásobníkové automaty a jazyky, Základy syntaktické analýzy shora dolů a zdola nahoru
8.    Jednoduché LL(1) gramatiky, q-gramatiky, rozkladové tabulky a algoritmy analýzy
9.    Silné LL(1) a LL(k) gramatiky, slabé LL(k) gramatiky
10.   Syntaktická analýza zdola nahoru, LR gramatiky
11.   LL a LR jazyky
12.   Obecné algoritmy syntaktické analýzy pro bezkontextové jazyky
13.   Algoritmy syntaktické analýzy a jejich implemetace,rekurzivní sestup, Backus-Naurova forma

Literatura

Základní:
HABIBALLA, H. Gramatiky a jazyky. Ostravská Univerzita, 2013.
M. CHYTIL Automaty a gramatiky, SNTL 1984 (matematický seminář).

Rozšiřující:
HABIBALLA, H. Regulární a bezkontextové jazyky I. OU Ostrava, 2007.
HABIBALLA, H. Regulární a bezkontextové jazyky II., OU Ostrava, 2007.
M. ČEŠKA, Z. RÁBOVÁ. Gramatiky a jazyky, VUT Brno 1985.

Doporučená:
L. MOLNÁR, M. ČEŠKA, B. MELICHAR Gramatiky a jazyky, ALFA/SNTL 1987.
JANČAR, PETR Teoretická informatika. VŠB TU Ostrava
http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm