Skip to main content
You are not logged in. (
Log in
)
Side panel
Support users
Contact us
Moodle tutorial
English (en)
Čeština (cs)
English (en)
Course info
Home
Courses
Matematicko-fyzikální fakulta
Automaty a gramatiky
Summary
Automaty a gramatiky
Teacher:
Jakub Bulín
Teacher:
Marta Vomlelová
Automaty a gramatiky
General
Obecné
Konečné automaty, regulární jazyky, Iterační (pumping) lemma
Redukce a ekvivalence automatů, nedeterminismus, lambda-NFA
Kleenova věta, množinové a řetězcové operace nad jazyky, regulární výrazy
Homomorfismus, inverzní homomorfismus, Mooreův a Mealyho stroj
Nedeterministické FA, lambda přechody, dvousměrné automaty
Gramatiky, Chomského hierarchie, L3 a FA, lineání gramatiky, CFG
Zásobníkové automaty, přijímání stavem, prázdným zásobníkem, vztah s CFG
Chomského normální forma, Pumping lemma pro CFG
Algoritmus CYK, vlastnosti CFL, Kontextové gramatiky
Deterministické a bezprefixové PDA
Deterministické a nedeterministické Turingovy stroje, Gramatiky Typu 0 (obecné gramatiky)
Diagonální jazyk, Univerzální TM, algoritmicky nerozhodnutelné problémy, Postův korespondenční problém
Předběžné sumáře
Home