Předmět Regulární a bezkontextové jazyky 1 (KIP / 2RAB1)
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 / 2RAB1 - 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 gramatikypř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. http://www.fit.vutbr.cz/study/courses/TI1/public/Texty/ti.pdfJANČAR, Petr. Teorie jazyků a automatů. VŠB TU Ostrava, Dokument dostupný na URL: http://www.cs.vsb.cz/jancar/.
Požadavky
4 korespondenční úkoly dle opory (50 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.