Přejít k hlavnímu obsahu
Boční panel
DL 1
Titulní stránka
Kalendář
Podpora uživatelů
Moodleoffice
Moodle tutoriál
Podpora uživatelů
Návody
GDPR
Další
Čeština (cs)
Čeština (cs)
Deutsch (de)
English (en)
Français (fr)
Русский (ru)
Momentálně na stránky přistupujete s právy hosta.
Přihlášení
DL 1
Titulní stránka
Kalendář
Podpora uživatelů
Sbalit
Rozbalit
Moodleoffice
Moodle tutoriál
Podpora uživatelů
Návody
GDPR
Rozbalit vše
Sbalit vše
Otevřít indexu kurzu
Otevřít panel bloku
Matematicko-fyzikální fakulta
Katedra teoretické informatiky a matematické logiky
Informatika-Bc
Automaty a gramatiky
Redukce a ekvivalence automatů
Redukce a ekvivalence automatů
Osnova sekce
◄
Konečné automaty, regulární jazyky, Iterační (pumping) lemma
►
nedeterminismus, λ-NFA, množinové a řetězcové operace nad jazyky
Vybrat aktivitu Slajdy 2 Iterační lemma, Ekvivalentní stavy, Redukce automatu, nedeterministické FA
Slajdy 2 Iterační lemma, Ekvivalentní stavy, Redukce automatu, nedeterministické FA
Soubor
Absolvování
Studenti musí
Označit jako hotovo
Vybrat aktivitu K videopřednášce: 26:37 'první dvě části xy', n...
K videopřednášce:
26:37 'první dvě části xy', ne 'první dvě části xz',
naopak 1:1730-1:19:15 zbytečně zmatkuji.
◄
Konečné automaty, regulární jazyky, Iterační (pumping) lemma
Přejít na...
Hlavní stránka kurzu
Úvod
Cvičení J. Bulín
Cvičení T. Čelko
Cvičení V. Majerech
Cvičení M. Vomlelová
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
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
Deterministické a nedeterministické Turingovy stroje, Gramatiky Typu 0 (obecné gramatiky)
Diagonální jazyk, Univerzální TM
Problém zastavení, PCP, (Ne)rozhodnutelné problémy o CFG
Časová složitost
Prostorová složitost
Archiv testů
Cvičení P. Gregor
►
nedeterminismus, λ-NFA, množinové a řetězcové operace nad jazyky