=====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 {{backlinks}}