Revision [6643]
This is an old revision of ChomskyHierarchie made by ToBo on 2008-11-28 18:23:09.
Chomsky-Hierarchie
S. 49
Allgemeine Grammatiken (Typ 0)
A → ε Reduktion
A → t Termination
A → tB Expansion
A → BC Expansion
A →B CD Doppelte Substitution
Nichtverkürzte Grammatiken (Typ 1)
kontextsensitiv
A → t Termination
A → BC Expansion
AB → CD Doppelte Substitution
Turing Maschine
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.
Endlicher Automaten
Siehe auch •
