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

\begin{slide}{Theorie der Formalen Sprachen}

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

untersucht (Hierarchien von) Sprachfamilien:
\begin{itemize}
\item äquivalente Definitionen für Familien (Grammatiken, Automaten, Ausdrücke)
\item (echte) Inklusionen
  (ist jede Typ-2-Sprache eine Typ-1-Sprache?
  gibt es Typ-2-Sprachen, die keine Typ-3-Sprache sind?)
\item Abschluß der Familien bzgl. Operationen
  (ist der Durchschnitt von zwei Typ-3-Sprachen wieder Typ-3?
  Desgl. für Typ-2?) (Falls ja, wie konstruiert man ihn effektiv?)
\item Entscheidbarkeit/Komplexität (z. b. des Wort-Problems)
\end{itemize}


\end{slide}

\begin{slide}{Theorie (II)}

\newcommand{\Typ}{\operatorname{Typ-}}

$i \ge j \Rightarrow$ Jede Typ-$i$-Sprache ist eine Typ-$j$-Sprache.

$i > j$: es gibt $L$ in Typ-$j$ $\setminus$ Typ-$i$:

$\{ a^n b^n \mid n \ge 0\} \in$ Typ-$2$ $\setminus$ Typ-$3$.

$\{ a^n b^n c^n \mid n \ge 0\} \in$ Typ-$1$ $\setminus$ Typ-$2$.

Wenn $A, B \in \Typ 3$, dann $A\cup B\in \Typ 3$ (trivial)
und $A \cap B\in \Typ 3$  (Aufgabe --- benutze Automaten).

Wenn $A, B \in \Typ 2$, dann $A\cup B\in \Typ 2$ (trivial --- Aufgabe).

Es gibt $A, B \in \Typ 2$ mit $A \cap B \notin \Typ 2$.

\end{slide}
