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.

Endlicher Automaten (FSM)


Siehe auch AtfsProduktionenAutomatentheorieUndFormaleSprachen

There are no comments on this page. [Add comment]

Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by WikkaWiki