Předmět Teorie jazyků a automatů (TJA)
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 TJA - Teorie jazyků a automatů, Vysoká škola báňská - Technická univerzita Ostrava (VŠB-TU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Student po úspěšném absolvování předmětu: - rozumí základním pojmům v oblasti teorie jazyků a automatů - umí volit vhodný formální jazyk k popisu praktických problémů a chápe možnosti i omezení různých tříd automatův souvislosti s jejich řešením - prokáže schopnost samostatně zvládnout a odprezentovat pokročilou partii v dané oblasti (např. u verifikace programů)
Osnova
Pojem formálního jazyka. Operace s jazyky. Regulární jazyky. Specifikace jazyků. Přepisovací systémy a gramatiky.Chomského klasifikace gramatik. Konečné automaty: deterministické, nedeterministické, zobecněné nedeterministické. Jazyky rozpoznávané konečnýmiautomaty. Kleeneho věta. Automatové morfismy a minimalizace konečných automatů. Konečné automaty a regulární gramatiky. Bezkontextové gramatiky. Zásobníkové automaty. Jazyky generované bezkontextovými gramatikami a rozhodované zásobníkovýmiautomaty. Kontextové jazyky generované kontextovými gramatikami a rozpoznávané lineárně omezenými automaty. Turingovy stroje.Jazyky rozpoznávané a rozhodované Turingovými stroji /rekurzivně spočetné a rekurzivní jazyky/. Postova věta. Algoritmickářešitelnost. Turingova /Churchova/ téze. Další partie teorie konečných automatů (dvoucestné automaty, automaty s váhami, ...) Další partie teorie bezkontextových jazyků (deterministické bezkontextové jazyky, ...) Stromové jazyky Vztah jazyků, automatů a logických teorií Další vybrané partie
Literatura
M.Sipser: Introduction to the Theory of Computation (2nd ed.), Thomson 2006
Požadavky
Žádné
Garant
prof. RNDr. Petr Jančar, CSc.
Vyučující
prof. RNDr. Petr Jančar, CSc.