Poznámky
Osnova
Kapitola XIII.
Jazyky složitější než bezkontextové
Turingovy stroje (TS)
Turingovy stroje: Definice
Interpretace pravidel
Grafická reprezentace
Turingův stroj: Příklad 1/2
Turingův stroj: Příklad 1/2
Konfigurace TS
Stacionární přechod
Pravý přechod
Levý přechod
Přechod
Sekvence přechodů 1/2
Sekvence přechodů 2/2
TS jako model pro přijímání jazyků
TS jako model pro přijímání jazyků: Příklad
TS jako výpočetní model
TS jako výpočetní model: Příklad
Deterministický TS (DTS)
k-páskový Turingův stroj
k-hlavý Turingův stroj
TS s oboustranně nekonečnou páskou
Zakódování Turingova stroje
Zakódování Turingova stroje: Příklad
Univerzální Turingův stroj
Neomezené gramatiky: Definice
Derivační krok
Neomezená gramatika: Příklad
Rekurzivně vyčíslitelné jazyky
Kontextová gramatika (KG)
Lineárně ohraničené automaty
Lineárně ohraničené automaty: Definice
Kontextové jazyky
Pravé lineární gramatiky: Definice
Gramatiky pro regulární jazyky
Gramatiky: Shrnutí
Automaty: Shrnutí
Chomského hierarchie
Jazyk L
PřijmeSámSebe
1/2
Jazyk L
PřijmeSámSebe
2/2
Jazyk L
NepřijmeSámSebe
1/3
Jazyk L
NepřijmeSámSebe
2/3
Jazyk L
NepřijmeSámSebe
3/3
Rozhodnutelné jazyky
Další hierarchie jazyků