456-0906/01 – Teorie jazyků a automatů - Ph.D. (TJA)
| Garantující katedra | Katedra informatiky | Kredity | 10 |
| Garant předmětu | prof. RNDr. Petr Jančar, CSc. | Garant verze předmětu | prof. RNDr. Petr Jančar, CSc. |
| Úroveň studia | postgraduální | Povinnost | povinně volitelný |
| Ročník | | Semestr | zimní + letní |
| | Jazyk výuky | čeština |
| Rok zavedení | 1997/1998 | Rok zrušení | 2009/2010 |
| Určeno pro fakulty | FEI | Určeno pro typy studia | doktorské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
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ů)
Vyučovací metody
Přednášky
Individuální konzultace
Projekt
Anotace
Předmět nejdříve rekapituluje základní znalosti týkajici se konečných automatů, bezkontextových jazyků a Turingových strojů, se kterými se studenti seznámili v magisterském studiu.
Klade se ovšem důraz na exaktní přístup a hlubší pochopení. Dále je kurs věnován pokročilejším partiím v těchto a dalších oblastech (např. vztahu jazyků, automatů a logiky, stromovým jazykům apod.).
Povinná literatura:
J.E.Hopcroft, J.D.Ullman: Introduction to Automata Theory, Languages and
Computation. Addison Wesley, 1978
M.Demlová, V.Koubek: Algebraická teorie automatů. Matematický seminář SNTL,
Praha, 1990
M.Chytil: Automaty a gramatiky. Matematický seminář SNTL, Praha, 1984
Doporučená literatura:
Handbook of formal languages, Vol 1,2,3 (ed. G.Rozenberg) (Springer 1997)
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
E-learning
Další požadavky na studenta
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
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ými automaty. 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ými automaty.
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
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.