Die Chomsky-Hierarchy

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

tags	uni/afs
aliases	—

Quartz 5