Revision [6598]
This is an old revision of ChomskyHierarchie made by ToBo on 2008-11-21 00:31:31.
Chomsky-Hierarchie
S. 49
Allgemeine Grammatiken (Typ 0)
A → ε Reduktion
A → t Termination
A → tB Expansion
A → BC Expansion
A → CD Doppelte Substitution
Nichtverkürzte Grammatiken (Typ 1)
kontextsensitiv
A → t Termination
A → BC Expansion
A → 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 •
