IA052 Topics in Language Theory

Fakulta informatiky
jaro 2009
Rozsah
2/0. 2 kr. (plus ukončení). Ukončení: k.
Vyučující
prof. RNDr. Branislav Rovan, Ph.D. (přednášející), prof. RNDr. Mojmír Křetínský, CSc. (zástupce)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Branislav Rovan, Ph.D.
Rozvrh
každé sudé úterý 14:00–17:50 B411
Předpoklady
Předpokládají se znalosti odpovídající rozsahu a náplni kursů IB005 Formální jazyky a automaty a IB107 Vyčíslitelnost a složitost.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
předmět má 18 mateřských oborů, zobrazit
Cíle předmětu
Hlavní cíle kurzu jsou: navázat na základní přednášku z teorie formálních jazyků, presentovat úvod do vybraných partií algebraické teorie formálních jazyků, zejména se zaměřením na tzv. abstraktní třídy jazyků a automatů. Dále prezentuje některá rozšíření pojmu gramatiky jako přepisovacího systému.
Osnova
  • Abstraktne triedy jazykov a automatov: definícia tried jazykov pomocou ich uzáverových vlastností, vzájomne vzťahy medzi operáciami nad jazykmi, vlastnosti triedy jazykov plynúce z vlastností triedy automatov, operácie nad automatmi a ich dôsledok na popisované jazyky, triedy jazykov generovaťelné z jednoho prvku.
  • Zovšeobecnenia gramatík: gramatiky s riadeným odvodením, biologicky motivované triedy gramatík, generatívne systémy, paralelne generovanie jazykov, zložitosť gramatík a jazykov.
Literatura
  • GINSBURG, Seymour. Algebraic and automata-theoretic properties of formal languages. Amsterdam: North-Holland Publishing Company, 1975, xii, 313. ISBN 0444105867. info
  • Handbook of formal languages. Vol. 1 Word, language, grammar. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer, 1997, xvii, 873. ISBN 3-540-60420-0. info
  • Handbook of formal languages. background and application. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer, 1997, xxii, 528. ISBN 3540614869. info
  • Salomaa, A.: Formal Languages. Academic Press, New York, 1973
  • Dassow,J., Paun,G.: Regulated Rewriting in Formal Language Theory. Springer, Berlin, 1980
Metody hodnocení
přednášky, volitelné domací úlohy. Závěrečná písemná zkouška.
Vyučovací jazyk
Angličtina
Další komentáře
Předmět je vyučován jednou za dva roky.
Předmět je zařazen také v obdobích jaro 2003, jaro 2006, jaro 2011.