% 4. Uebungsblatt GTI SS 2001
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=16,1cm
\textheight=24cm
\hoffset = -19mm
\voffset = -25mm

\setcounter{page}{4}
\let\eps=\varepsilon
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2001 ---
 4.~\"Ubungsblatt\par
}
\medskip
Abgabe bis Montag, 21. Mai 2001 (Abgabe in Dreiergruppen!)
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{18}

\item (6 Punkte) Produkt von Automaten.\\
Wie kann man zu zwei gegebenen DEA $M_1$ und $M_2$ einen DEA
konstruieren, der die Sprache $L(M_1)\cap L(M_2)$ akzeptiert?
(Hinweis: Der neue Automat soll die Automaten $M_1$ und $M_2$
"`gleichzeitig"' simulieren;
Welche Zustandsmenge muss er haben?)

\item (0 Punkte) Zeigen Sie: Wenn $L=\{ \, x\in\{0,1\}^* \mid
x\hbox{ enthält gleich vielen Nullen und Einsen}\,\}$
regulär wäre, dann wäre auch die Sprache
$L'=\{\,0^n1^n\mid n\ge 0\,\}$ regulär.

\item (4 Punkte) Konstruieren Sie einen NEA für die
 Sprache
$\varepsilon + 0+((01^*0)^*+10^*)^*$.

\item (0 Punkte) Konstruieren Sie einen NEA für die
 Sprache
$(0+1)^*000(0+1+\varepsilon)^*$.

\item (6 Punkte) Bestimmen Sie den Minimalautomaten für
den NEA aus Aufgabe~12. 

\item (0 Punkte)
Wie kann man für einen gegebenen DEA oder NEA $M$ feststellen,
ob $L(M)=\emptyset$ ist?

\item (0 Punkte)
Beweisen Sie, dass die Klasse der regulären Sprachen abgeschlossen
gegenüber \emph{Umkehrung} ist: Wenn $L$ regulär ist,
dann ist auch $L^R$ regulär. ($L^R$ ist die Menge der
von hinten gelesenen Wörter von $L$.)

\end{enumerate}
Nächste Woche entfällt die Vorlesung, und es wird
kein Übungsblatt ausgeteilt. Die Tutorien finden
aber wie gewöhnlich  statt.
\end{document}






