Revision [6609]
This is an old revision of ChomskyHierarchie made by ToBo on 2008-11-21 01:33:53.
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
Kontextfreie Grammatiken (Typ 2)
A → t Termination
A → BC Expansion
(rechts-)lineare Grammatiken (Typ 3)
A → t Termination
A → tB Expansion
Wobei A,B,C,D ∈ N und t ∈ T ist.
Siehe auch •
