Poznámky
Osnova
Part XIII.
Beyond the Context-Free Languages
Turing Machines (TM)
Turing Machines: Definition
Interpretation of Rules
Graphical Representation
Turing Machine: Example 1/2
Turing Machine: Example 2/2
TM Configuration
Stationary Move
Right Move
Left Move
Move
Sequence of Moves 1/2
Sequence of Moves 2/2
TM as a Language Acceptor
TM as an Acceptor: Example
TM as a Computational Model
TM as a Computational Model: Example
Deterministic Turing Machine (DTM)
k-Tape Turing Machine
k-Head Turing Machine
TM with Two-way Infinite Tapes
Description of a Turing Machine
Description of TM: Example
Universal Turing Machine
Unrestricted Grammar: Definition
Derivation Step
Unrestricted Grammar: Example
Recursively Enumerable Languages
Context-Sensitive Grammar
Linear Bounded Automaton
Linear Bounded Automaton: Definition
Context-sensitive Languages
Right-Linear Grammar: Definition
Grammars for Regular Languages
Grammars: Summary
Automata: Summary
Chomsky Hierarchy
Language L
SelfAcceptance
1/2
Language L
SelfAcceptance
2/2
Language L
NonSelfAcceptance
1/3
Language L
NonSelfAcceptance
2/3
Language L
NonSelfAcceptance
3/3
Recursive Language
Other Hierarchy of Languages