Die Chomsky-Hierarchie

• Typ-0 (beliebige Regeln)

  (Wortproblem nicht entscheidbar)

• Typ-1 (keine verkürzenden Regeln): $\forall$(l, r) $\in$ R : | l|$\le$| r|.

  ( $\Rightarrow$ Wortproblem entscheidbar, jedoch aufwendig)

• Typ-2 (nur kontextfreie Regeln): $\forall$(l, r) $\in$ R : l $\in$ V

  ( $\Rightarrow$ Wortproblem in Polynomialzeit)

• Typ-3 (nur rechtslineare Regeln):

  $\forall$(l, r) $\in$ R : l $\in$ V $\wedge$ r $\in$ $\Sigma$V $\cup$ $\Sigma$.

  ( $\Rightarrow$ Wortproblem in Linearzeit)