%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Eingeschränkte Grammatiken}

\kopf{$ $Id: chomsky.tex,v 1.1 2011-10-11 18:13:54 waldmann Exp $ $}

Für allgemeine Grammatiken ist $w \in L(G)$ (\emph{Wortproblem})
gar nicht entscheidbar.

Regelmenge einschränken $\to$ 
\begin{itemize}
\item Vorteil: leichter (automatisch) zu behandeln
\item Nachteil: weniger ausdrucksstark
\end{itemize}

\end{slide}

\begin{slide}{Die Chomsky-Hierarchie}

\begin{itemize}\itemsep 0pt
\item Typ-0 (beliebige Regeln)

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

  ($\Rightarrow$ Wortproblem entscheidbar, jedoch aufwendig)
\item Typ-2 (nur kontextfreie Regeln): 
  $\forall (l,r) \in R: l \in V$

  ($\Rightarrow$ Wortproblem in Polynomialzeit)
\item Typ-3 (nur rechtslineare Regeln):

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

  ($\Rightarrow$ Wortproblem in Linearzeit)
\end{itemize}


\end{slide}
