% 2. 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}{2}
\let\eps=\varepsilon
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2001 ---
 2.~\"Ubungsblatt\par
}
\medskip
Abgabe bis Montag, 7. Mai 2001
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{6}

\item (0 Punkte)
Entscheiden Sie, ob die folgenden regulären Ausdrücke jeweils
dieselbe Sprache darstellen.
\begin{enumerate}
\item
[(a)]\noindent
\hbox to 0,27\hsize{$\eps^*=\eps$ \hfil}
(b) 
\hbox to 0,27\hsize{
$(01)^*0 = 0(10)^*$
 \hfil}
(c) $\emptyset^* = \eps + (0+\eps)^*\emptyset$
\item
[(d)]$A^* = \eps+A^*A$, wobei $A$ ein beliebiger regulärer
Ausdruck ist.
\item
[(e)]\noindent
\hbox to 0,27\hsize{$(01^*)^* = (01^*0 + 0)^*$ \hfil}
(f) $(00)^* + (00000)^* + (000)^* = 00^*$
\end{enumerate}
\item (6 Punkte)
Eine \emph{Kongruenzrelation} $\sim$ auf einer Menge $\Sigma^*$
von Wörtern ist eine Äquivalenzrelation mit folgender zusätzlicher
Eigenschaft:
$$ a\sim b \,\land\, c\sim d \;\Longrightarrow\; ac\sim bd .$$
Welche der folgenden Relationen sind Kongruenzrelationen? (Beweisen Sie Ihre
Antworten.)
\begin{enumerate}
\item (0 Punkte) $a\sim b \iff a$ und $b$ haben
die gleiche Anzahl von Nullen
und die gleiche Anzahl von Einsen.
\item (0 Punkte) $a\sim b \iff a=\eps$ oder $b=\eps$
oder $a\ne\eps\ne b$ und $a$ und $b$ haben denselben Anfangsbuchstaben.
\item (3 Punkte) $a\sim b \iff a=b=\eps$
oder $a\ne\eps\ne b$ und $a$ und $b$ haben denselben Anfangsbuchstaben.
\item (3 Punkte) $a\sim b \iff {}$das Teilwort 01 kommt in
$a$ und $b$ gleich häufig vor.
\end{enumerate}

\item (5 Punkte)
Für einen Zustand $q\in Q$ des DEA $M=(Q,\Sigma,\delta,q_0,F)$
sei die Sprache $L_q(M)$ so definiert:
$$
L_q(M) =
  \{ \, w\in \Sigma^* \mid \delta(q_0,w)=q \,\}
$$
Beweisen Sie: Wenn $w_1, w_2 \in L_q(M)$ sind, dann gilt
für alle $x\in\Sigma^*$:
\xdef\syntmon{\arabic{enumi}}
$$w_1x \in L(M) \iff w_2x \in L(M) $$


\item (5 Punkte)
Konstruieren Sie, wenn möglich, DEA's, die folgende
Sprachen über dem Alphabet $\{0,1\}$ akzeptieren.
\begin{enumerate}
\item (3 Punkte)
$(0+1)^*010101(0+1)^*$
\item (2 Punkte)
Alle Wörter, die das Teilwort 010101 \emph{nicht} enthalten.
\item (0 Punkte)
Alle Wörter, die das Teilwort 01, aber nicht
das Teilwort 100 enthalten.
\item (0 Punkte)
Alle Wörter, die gleich viele Nullen und Einsen enthalten.
\item (0 Punkte)
Alle Wörter, die das Teilwort 010 \emph{genau einmal} enthalten.
\item (Zusatzfrage, 3 Punkte)
Beweisen Sie, dass jeder Automat, der Aufgabe~(a) löst,
mindestens sechs Zustände haben muss.
[ Hinweis: Sie können Aufgabe~\syntmon\ verwenden. ]
\end{enumerate}

\item (0 Punkte)
Konstruieren Sie, wenn möglich, DEA's, die folgende
Sprachen akzeptieren.
\begin{enumerate}
\item Die durch 5 teilbaren Dezimalzahlen.
\item Die durch 9 teilbaren Dezimalzahlen.
\item Die durch 7 teilbaren Dezimalzahlen.
\end{enumerate}
Untersuchen Sie dabei jeweils beide Möglichkeiten der Reihenfolge,
in der die Dezimalstellen der Zahl eingegeben
werden können: mit der höchsten Stelle zuerst oder mit der Einerstelle
zuerst.
\end{enumerate}
\end{document}






