Theory of Languages and Automata

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