next up previous contents index
Next: Wortproblem 21 Up: Allgemeines zu Sprachen Previous: Grammatiken 13   Contents   Index

Subsections


Chomsky-Hierarchie 17

Die Menge aller Grammatiken (und der dazugehörigen Sprachen) lässt sich in folgende Kategorien unterteilen. Die Sprachen werden abgekürzt mit $ \mathcal{L}_{n}$. Dabei gilt:

$\displaystyle \mathcal{P}\left(\Sigma^{*}\right)\supset\mathcal{L}_{0}\supset\mathcal{L}_{1}\supset\mathcal{L}_{2}\supset\mathcal{L}_{3}$


Typ 0 oder rekursiv aufzählbar

Jede Grammatik ist automatisch vom Typ 0. Es gibt hier also keine Einschränkungen. (Außer das es eine korrekte Grammatik sein muss)


Typ 1 oder kontextsensitiv

wenn: $ \forall_{P}^{\left(w_{1}\rightarrow w_{2}\right)}:\left\vert w_{1}\right\vert\leq\left\vert w_{2}\right\vert$


Typ 2 oder kontextfrei

wenn: $ \forall_{P}^{\left(w_{1}\rightarrow w_{2}\right)}:w_{1}\in V$


Typ 3 oder regulär

wenn: $ \forall_{P}^{\left(w_{1}\rightarrow w_{2}\right)}:w_{1}\in V\wedge w_{2}\in\left(\Sigma\cup\Sigma V\right)$


next up previous contents index
Next: Wortproblem 21 Up: Allgemeines zu Sprachen Previous: Grammatiken 13   Contents   Index
Marco Möller 18:11:27 24.10.2005