Zum Hauptinhalt
Website-Übersicht
DL 1
Startseite
More
Deutsch (de)
Русский (ru)
Čeština (cs)
Deutsch (de)
English (en)
Français (fr)
Sie sind als Gast angemeldet
Login
DL 1
Startseite
Alle aufklappen
Alle einklappen
Open course index
Open block drawer
Automaty a gramatiky
Cvičení J. Bulín
Cvičení J. Bulín
Section outline
◄
Allgemeines
►
Cvičení V. Majerech
Select activity Informace o cvičení najdete zde: https://jbulin.gi...
Abschluss
Students must
Mark as done
Informace o cvičení najdete zde:
https://jbulin.github.io/teaching/spring/ntin071/cviceni/
◄
Allgemeines
Direkt zu:
Kursübersicht
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
►
Cvičení V. Majerech