Skip to main content
Side panel
DL 1
Home
Calendar
Support
User support
GDPR
More
English (en)
Čeština (cs)
Deutsch (de)
English (en)
Français (fr)
Русский (ru)
You are currently using guest access
Log in
DL 1
Home
Calendar
Support
Collapse
Expand
User support
GDPR
Expand all
Collapse all
Open course index
Open block drawer
Faculty of Mathematics and Physics
Department of Theoretical Computer Science and Mathematical Logic
Informatics
Automaty a gramatiky
Kleenova věta, regulární výrazy, Homomorfismus, inverzní homomorfismus
Kleenova věta, regulární výrazy, Homomorfismus, inverzní homomorfismus
Section outline
◄
nedeterminismus, λ-NFA, množinové a řetězcové operace nad jazyky
►
Příklad na homomorfizmy, Dvousměrné automaty, Mooreův a Mealyho stroj
Select activity Slajdy 4.přednásky
Slajdy 4.přednásky
File
Completion
Students must
Mark as done
Změna v důkazu Kleeneho věty pomocí eliminací stavů.
Select activity Prezentace rozlozena 4
Prezentace rozlozena 4
File
Completion
Students must
Mark as done
Select activity Kleene
Kleene
Quiz
Completion
You have to add at least one completion condition.
Select activity Python notebook testující regulární výrazy
Python notebook testující regulární výrazy
File
Select activity Kleene, uzávěrové vlastnosti
Kleene, uzávěrové vlastnosti
Quiz
Completion
Students must
Mark as done
◄
nedeterminismus, λ-NFA, množinové a řetězcové operace nad jazyky
Jump to...
Main course page
General
Cvičení J. Bulín
Cvičení V. Majerech
Konečné automaty, regulární jazyky, Iterační (pumping) lemma
Redukce a ekvivalence automatů
nedeterminismus, λ-NFA, množinové a řetězcové operace nad jazyky
Kleenova věta, regulární výrazy, Homomorfismus, inverzní homomorfismus
Příklad na homomorfizmy, Dvousměrné automaty, Mooreův a Mealyho stroj
Gramatiky, Chomského hierarchie, L3 a FA, lineání gramatiky, CFG
Chomského normální forma, Pumping lemma pro CFG
Zásobníkové automaty, přijímání stavem, prázdným zásobníkem, vztah s CFG
Deterministické PDA, Uzávěrové vlastnosti CFL, Dyckovy jazyky
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
Problém zastavení, PCP, (Ne)rozhodnutelné problémy o CFG
Časová složitost
Prostorová složitost
Archiv testů
Cvičení P. Gregor
►
Příklad na homomorfizmy, Dvousměrné automaty, Mooreův a Mealyho stroj