Grammatik

Definition

Eine Grammatik ist von der Form $G=(N,\Sigma ,P,S)$ wobei

• $N$ und $\Sigma$ endliche, disjunkte Alphabete von Nichtterminalensymbol bzw Terminalsymbol ist,
• $S\in N$ das Startsymbol ist,
• $P\subseteq (N\cup \Sigma {)}^{+}\times (N\cup \Sigma {)}^{\ast }$ eine endliche Menge von Ersetzungsregeln ist.

Satz

Zwei Grammatiken heißen äquivalent, falls sie dieselbe Sprache erzeugen.

Die Chomsky-Hierarchy

	Name	Grammatik	Sprache	äquivalent
Typ 0		Jede		Turing Maschine
Typ 1	monoton	$w⟶u\Vert w\Vert \le \Vert u\Vert$		linear beschränkte NTM
Typ 2	Kontextfreie Grammatik	$A⟶w$	Kontextfreie Sprache	Kellerautomat
Typ 3	rechtslinear	$A⟶u$ oder $A⟶uB$	Reguläre Sprache	DEA, NEA, ε-NEA, wort-NEA

siehe:
Sprachklasse

Link to original

Chomsky-Normalform
Kuroda-Normalform