Předmět Regulární a bezkontextové jazyky 1 (KIP / RABJ1)
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 / RABJ1 - Regulární a bezkontextové jazyky 1, 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é KA2. Deterministické a nedeterministické KA3. Zobecněné nedeterministické KA a třída jazyků rozpoznatelných KA4. Uzávěrové vlastnosti třídy jazyků rozpoznatelných KA5. Regulární jazyky, regulární výrazy, jejich vztah k jazykům rozpoznatelným konečnými automaty6. Charakterizace regulárních jazyků pomocí pravých kongruencí7. Algoritmus redukce konečných automatů, ekvivalence KA8. Bezkontextové gramatiky a jazyky, regulární gramatiky a jazyky9. Nevypouštějící a redukované gramatiky, kanonická odvození, jednoznačné gramatiky10. Chomského normální forma, lemma o vkládání (pumping lemma)11. Zásobníkové automaty, vztah k bezkontextovým jazykům12. Uzávěrové vlastnosti třídy bezkontextových jazyků13. Obecné přepisovací systémy, Chomského hierarchie
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ář). H. Habiballa. Regulární a bezkontextové jazyky I., OU Ostrava 2003 (distanční opora). nullwww.fi.muni.cz - http://www.fi.muni.cz/zkusto/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. http://www.cs.vsb.cz/jancar/TJAA/tjaa.htm
Požadavky
2 testy na řešení příkladů (2x25 b.), zkouška z teorie kombinovanou formou - test + pohovor (50 b.); hodnocení dle platných předpisů na základě bodů (škála 0-100 b.)
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.