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

\begin{slide}{Aufgaben zu Grammatiken}

\kopf{$ $Id: aufgaben.tex,v 1.1 2011-10-16 14:06:17 waldmann Exp $ $}

Sprachen (und ihre Komplemente \verb|Com*|):
\begin{itemize}
\item \verb|Pali|: $\{ w \mid w = \operatorname{reverse}(w) \}$
\item \verb|Gleich|: $\{ w \mid d(w) = 0 \}$,
  wobei $d(x) := |w|_a - |w|_b$
\item \verb|Dyck|-Sprache (korrekt geklammerte Wörter):
 
  $\{ w \mid d(w)=0 \wedge \forall u \sqsubseteq w: d(u)\ge 0 \},$
\end{itemize}


Aufgaben:
\verb|G|: finde CF-Grammatik,
\verb|Ein|: eindeutige CF-Grammatik

\begin{itemize}
\item empfohlen: \verb|Ein-Pali, G-ComPali, Ein-Dyck, G-ComGleich|
\item Highscores: \verb|Ein-(Com)Gleich, {G,Ein}-Com{Pali,Dyck}|
\end{itemize}

\end{slide}
