

\begin{slide}{Formale Sprachen: Chomsky-Hierarchie}


\begin{itemize} \itemsep 1pt \parskip 1pt
\item (Typ 0) aufzählbare Sprachen
  (beliebige Grammatiken, Turingmaschinen)
\item (Typ 1) kontextsensitive Sprachen
  (monotone Grammatiken, linear beschränkte Automaten)
\item (Typ 2) kontextfreie Sprachen 
  (kontextfreie Grammatiken, Kellerautomaten)
\item (Typ 3) reguläre Sprachen 
  (rechtslineare Grammatiken, reguläre Ausdrücke, endliche Automaten)
\end{itemize}

Tokenklassen sind meist reguläre Sprachen.

Programmiersprachen werden kontextfrei beschrieben
(mit Zusatzbedingungen).

\end{slide}
