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 AtfsProduktionen
AutomatentheorieUndFormaleSprachen
Valid XHTML :: Valid CSS: :: Powered by WikkaWiki