Předmět Gramatiky a jazyky (KIP / 2GRJA)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KIP / 2GRJA - Gramatiky a jazyky, Přírodovědecká fakulta, Ostravská univerzita v Ostravě (OU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
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 KA3. 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 stroje7. Deterministické zásobníkové automaty a jazyky, Základy syntaktické analýzy shora dolů a zdola nahoru8. Jednoduché LL(1) gramatiky, q-gramatiky, rozkladové tabulky a algoritmy analýzy9. Silné LL(1) a LL(k) gramatiky, slabé LL(k) gramatiky10. Syntaktická analýza zdola nahoru, LR gramatiky11. LL a LR jazyky12. Obecné algoritmy syntaktické analýzy pro bezkontextové jazyky13. Algoritmy syntaktické analýzy a jejich implemetace,rekurzivní sestup, Backus-Naurova forma
Získané způsobilosti
- znalost základů problematiky teorie formálních jazyků a automatů- dobrá znalost vlastností dvou nejjednodušších tříd jazyků (regulárních a bezkontextových)- schopnost konstrukce konečných a zásobníkových automatů, regulárních výrazů, bezkontextových gramatiky- převody automatů a gramatik na reálných případech
Literatura
M. Chytil. Automaty a gramatiky, SNTL 1984 (matematický seminář). Habiballa, H. Regulární a bezkontextové jazyky I. Ostravská Univerzita, 2003. Habiballa, H. Regulární a bezkontextové jazyky II. Ostravská Univerzita, 2003. M. Češka, Z. Rábová. Gramatiky a jazyky, VUT Brno 1985. L. Molnár, M. Češka, B. Melichar. Gramatiky a jazyky, ALFA/SNTL 1987. P. Jančar. Teorie formálních jazyků a automatů, VŠB-TUO, 2004.
Požadavky
Zkoušku student absolvuje v souladu s platným Studijním řádem, zejména s důrazem na č. 32 a čl. 33 Studijního a zkušebního řádu OU.Hodnocení: prakticky orientované korespondenční úkoly celkem 60 bodů, teoretický zkouškový test 40 bodů. Celkově lze získat 100 bodů, pro úspěšné zvládnutí zkoušky je třeba získat celkem alespoň 51 bodů.
Garant
doc. RNDr. PaedDr. Hashim Habiballa, PhD., Ph.D.
Vyučující
doc. RNDr. PaedDr. Hashim Habiballa, PhD., Ph.D.doc. RNDr. PaedDr. Hashim Habiballa, PhD., Ph.D.