Chomsky-Hierarchie
SkriptAtfsEckNr2, S. 49
Allgemeine Grammatiken (Typ 0)
A → ε Reduktion
A → t Termination
A → tB Expansion
A → BC Expansion
A →B CD Doppelte Substitution
Turing Maschine
Nichtverkürzte Grammatiken (Typ 1)
kontextsensitiv
A → t Termination
A → BC Expansion
AB → CD Doppelte Substitution
Linear platzbeschränkte nichtdeterministische Turingmaschine.
Kontextfreie Grammatiken (Typ 2)
A → t Termination
A → BC Expansion
Kellerautomaten
(rechts-)lineare Grammatiken (Typ 3)
A → t Termination
A → tB Expansion
Wobei A,B,C,D ∈ N und t ∈ T ist.
EndlicherAutomat Endlicher Automaten (FSM)
Siehe auch •
