% 2. Uebungsblatt GTI SS 2005
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=15,4cm
\textheight=24,9cm
%\textheight=26cm
\hoffset = -19mm
\voffset = -25mm
\let\eps=\varepsilon

\setcounter{page}{4}
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2005 ---
 2.~\"Ubungsblatt\par
}
\bigskip
Abgabe bis Montag, 2. Mai 2005, 10:15 Uhr
\par \bigskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{10}

\item Kommutierende Wörter:
 Wieviele Paare von Wörter $a\in \Sigma^3$
und  $b\in \Sigma^2$ mit der Eigenschaft
$ab=ba$ gibt es?
 Wieviele Paare von Wörter $a\in \Sigma^6$
und  $b\in \Sigma^9$ mit der Eigenschaft
$ab=ba$ gibt es?
Wie ist es allgemein für $a\in \Sigma^m$
und  $b\in \Sigma^n$? Wodurch kann man solche Wortpaare charakterisieren?

\item
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.)
Die Beziehung $a\sim b$ soll genau dann gelten, wenn folgende Bedingung erfüllt ist:
\begin{enumerate}
\item $a$ und $b$ haben
die gleiche Anzahl von Nullen
und die gleiche Anzahl von Einsen.
\item $a=b=\eps$
oder $a\ne\eps\ne b$ und $a$ und $b$ haben denselben Anfangsbuchstaben.
\item $a=\eps$ oder $b=\eps$
oder $a\ne\eps\ne b$ und $a$ und $b$ haben denselben Anfangsbuchstaben.
\item das Teilwort 100 kommt in
$a$ und $b$ gleich häufig vor.
\end{enumerate}

\item 
Schreiben Sie ein Programm in Haskell (oder Java), das
für einen endlichen Automaten (in einer geeigneten Darstellung)
und ein gegebenes Wort entscheidet, ob es vom Automaten akzeptiert wird.

\item % (10 Punkte)  
\begin{enumerate}
  \item (5 Punkte)
Konstruieren Sie einen endlichen Automaten, der die durch 5
teilbaren
Binärzahlen akzeptiert. Das höchstwertige Bit wird dabei zuerst eingelesen.

  \item (5 Punkte)
Konstruieren Sie einen deterministischen endlichen Automaten, der
genau jene Wörter über dem
Alphabet
$\{a,b,c,d\}$ akzeptiert, die das Teilwort
$abacabadabaca$ enthalten.

  \item (0 Punkte)
Konstruieren Sie einen endlichen Automaten, der die Wörter
% über dem Alphabet $\{a,b,c,d\}$
akzeptiert, die das Teilwort
${abacabadabaca}$ \emph{nicht} enthalten.

\end{enumerate}
Erläutern Sie Ihre Automaten mit einigen Sätzen.
Zeichnen Sie Zustandsdiagramme.

\item 
Konstruieren Sie einen äquivalenten deterministischen
Automaten für den nichtdeterministischen endlichen Automaten mit
 $\Sigma=\{0,1\}$, $Q=\{a,b,c\}$,
 $Q_0=\{a\}$, $F=\{a\}$ und
 $$\delta=\{(a,0,a),(a,0,b),(b,1,b),(b,1,c),(c,0,c),(c,0,a)
\}.$$

\item (Zusatzaufgabe, 0 Punkte)
Beweisen Sie,  dass die von einem DEA akzeptierten Sprachen (die regulären Sprachen) unter
{Präfixbildung} abgeschlossen sind:
Wenn $L$ eine solche Sprache ist, dann gibt es auch einen
DEA, der
$$L' = \{\, x \mid \hbox{es gibt ein $y$ mit $xy\in L$}\,\}$$
akzeptiert.

\item
Konstruieren Sie einen endlichen Automaten
\emph{ohne} $\varepsilon$-Übergänge für die Sprache
$$(a+ba)^+(b+ab)^*+
(bb)^*a^+(bb)^*.$$
%akzeptiert.
\item
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) $$

\end{enumerate}
\eject
\end{document}

