\documentclass[12pt,a4paper]{article}
\usepackage{german}
\usepackage[latin1]{inputenc}
\usepackage{fancyhdr}
\usepackage{amstext,amssymb}
\usepackage{graphicx}
\pagestyle{fancy}
\textwidth17cm
\textheight23.7cm
\headwidth17cm
\topmargin-0.8cm
\headheight12pt
\headsep36pt
\oddsidemargin-0.5cm
\footskip1.5cm
\parskip2ex
\nonfrenchspacing
\DeclareFontFamily{OT1}{mvs}{}
\DeclareFontShape{OT1}{mvs}{m}{n}{<-> fmvr8x}{}
\def\mvs{\usefont{OT1}{mvs}{m}{n}}
\def\mvchr{\mvs\char}
\def\Lightning{{\mvchr69}}
\newcommand{\blitz}{\text{\Lightning}}\parindent0pt

\begin{document}

% ------------------Kopf- und Fußzeile--------------------------------

\lhead{SS 2000 Theoretische Informatik 2}
\chead{Blatt 4}
\rhead{Seite \thepage}

\lfoot{}
\cfoot{}
\rfoot{}

% ------------------Dokument------------------------------------------

\section*{Aufgabe 12}
$R$ ist eine reguläre Sprache. Es soll gezeigt werden, daß $FH(R)
\stackrel{\text{def}}{=} \{ x | \exists y \in \Sigma^*: (|x| = |y|
\wedge xy \in R) \}$, wobei $FH$ für \emph{"`First Half"'} steht, also
die erste Hälfte des Wortes.

\textbf{Idee:} Sei $M$ ein DFA, der $R$ akzeptiert. Dieser DFA soll
die erste Hälfte des Wortes, $x$, verarbeiten. Sobald $x$ abgearbeitet
ist, befindet sich der DFA in einem Zustand $p$. Ab diesem Zustand ist
der Nachfolgezustand irrelevant, der Automat muß nur nach Abarbeitung
von $y$ mit $|y| = |x|$ in einem akzeptierenden Zustand $F$ sein. Man
kann sich dies so vorstellen, daß man gleichzeitig in $q_0$ und in $F$
startet, wobei von $F$ aus das Reversal-Wort $y^R$ abgearbeitet
wird. Wenn die beiden Teilautomaten sich in $p$ treffen, wird das Wort
akzeptiert.
\begin{center}
\includegraphics{Blatt04-Darstellung-12.eps}
\end{center}
Da $R \subset \Sigma^*$ eine reguläre Sprache ist, gibt es einen DFA
$M = (Q, \Sigma, \delta, q_0, F)$ mit $T(M) = R$. Man kontruiere einen
NFA $M' = (Q', \Sigma, \delta', q_0', F')$ mit $Q' = \{
\underbrace{[p,q]}_{Q \times Q} |p,q \in Q \} \cup \{ q_0' \}, q_0
\notin Q \times Q$.

$\delta'([p,q], \sigma) = \{ [\delta(p,\sigma),q'] | \exists \xi \in
\Sigma: \delta(q,\xi) = q \}$ für alle $[p,q] \in Q', \sigma \in
\Sigma$.

$\delta'(q_0, \sigma) = \bigcup_{f \in F}([q_0,f], \sigma)$ für alle
$\sigma \in \Sigma$. $F' = \{[q,q]|q \in Q \} \cup \{q_0'|q_0 \in F
\}$. Durch Induktion nach $|w|$ zeigt man: $\forall x \in \Sigma^+$
gibt es ein $p,q \in Q$. \footnote{Das leere Wort ist nicht enthalten,
  da es mit $\Sigma$ in $q_0'$ liegt}

$\delta'(q_0',x) = [p,q] \Leftrightarrow \delta(q_0,x) = p \wedge
\exists y \in \Sigma^*, f \in F: (|x|=|y| \wedge \delta(q,y)=f$. Damit
gilt für alle $x \in \Sigma^+$:
\begin{eqnarray*}
  x \in T(M')
  &\Leftrightarrow& \delta'(q_0',x) \cap F' \neq \emptyset\\
  &\Leftrightarrow& \exists [p,q] \in F', [p,q] \in \delta'(q_0',x)\\
  &\Leftrightarrow& \exists [q,q] \in Q': [q,q] \in \delta'(q_0',x)\\
  &\Leftrightarrow& \exists [q,q] \in Q': \delta(q_0,x)=q \wedge
  \exists y \in \Sigma^*, f \in F: |x|=|y|\wedge \delta(q,y)=f\\
  &\Leftrightarrow& \exists y \in \Sigma^*, q \in Q, f \in F:
  \delta(q_0,x) = q \wedge \delta(q,y) = f \wedge |x| = |y|\\
  &\Leftrightarrow& \exists y \in \Sigma^*: |x| = |y| \wedge xy \in
  T(M)\\
  &\Leftrightarrow& x \in FH(T(M))
\end{eqnarray*}
Wegen $\varepsilon \in T(M') \Leftrightarrow \varepsilon \in T(M)$
gilt $T(M') = FH(T(M))$. $\Box$

\section*{Aufgabe 13}
Im Schaubild sieht der NFA wie folgt aus:
\begin{center}
  \includegraphics{Blatt04-NFA-13.eps}
\end{center}
Daraus läßt sich mit der Potenzmengenkonstruktion der folgende DFA
erstellen. Die Zustände werden der Einfachheit halber etwas
"`umgetauft"':
\begin{center}
  \includegraphics{Blatt04-DFA-13.eps}
\end{center}
Dieser Automat wird nach dem bekannten Verfahren minimiert. Die
Klassen der Äquivalenzrelation $\stackrel{0}{\sim}$ entsprechen den
Mengen der Nicht-Ziel- und der Zielzustände:

$\stackrel{0}{\sim}$:\hspace{1cm}$[0,3,5]$\hspace{1cm}$[1,2,4,6,7]$

Für die weiteren Äquivalenzrelationen werden die Klassen gemäß dem
Verfahren aus dem Skript ermittelt, bis sich schließlich keine neuen
Klassen mehr ergeben:

$\stackrel{1}{\sim}$:
\begin{center}
\begin{tabular}{l|l|l}
    & a                                  & b                                  \\ \hline
  0 & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ & $[0,3,5]_{\stackrel{0}{\sim}}$     \\
  1 & $[0,3,5]_{\stackrel{0}{\sim}}$     & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\
  2 & $[0,3,5]_{\stackrel{0}{\sim}}$     & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\
  3 & $[0,3,5]_{\stackrel{0}{\sim}}$     & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\
  4 & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ & $[0,3,5]_{\stackrel{0}{\sim}}$     \\
  5 & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\
  6 & $[0,3,5]_{\stackrel{0}{\sim}}$     & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\
  7 & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ & $[1,2,4,6,7]_{\stackrel{0}{\sim}}$ \\
\end{tabular}
\end{center}
Zu den Klassen von $\stackrel{1}{\sim}$ können nun alle Zustände
zusammengefaßt werden, die gleiche Zeilen haben und bereits bei
$\stackrel{0}{\sim}$ in einer Klasse waren; dies sind hier

\begin{center}
$[0]$\hspace{1cm}$[1,2,6]$\hspace{1cm}$[3]$\hspace{1cm}$[4]$\hspace{1cm}$[5]$
\hspace{1cm}$[6]$\hspace{1cm}$[7]$
\end{center}

$\stackrel{2}{\sim}$:
\begin{center}
\begin{tabular}{l|l|l}
    & a                              & b                              \\ \hline
  0 & $[1,2,6]_{\stackrel{1}{\sim}}$ & $[0]_{\stackrel{1}{\sim}}$     \\
  1 & $[3]_{\stackrel{1}{\sim}}$     & $[1,2,6]_{\stackrel{1}{\sim}}$ \\
  2 & $[3]_{\stackrel{1}{\sim}}$     & $[1,2,6]_{\stackrel{1}{\sim}}$ \\
  3 & $[3]_{\stackrel{1}{\sim}}$     & $[4]_{\stackrel{1}{\sim}}$     \\
  4 & $[1,2,6]_{\stackrel{1}{\sim}}$ & $[5]_{\stackrel{1}{\sim}}$     \\
  5 & $[1,2,6]_{\stackrel{1}{\sim}}$ & $[4]_{\stackrel{1}{\sim}}$     \\
  6 & $[3]_{\stackrel{1}{\sim}}$     & $[7]_{\stackrel{1}{\sim}}$     \\
  7 & $[1,2,6]_{\stackrel{1}{\sim}}$ & $[7]_{\stackrel{1}{\sim}}$     \\
\end{tabular}
\end{center}
Damit sind die Klassen von $\stackrel{2}{\sim}$:
\hspace{1cm}$[0]$\hspace{1cm}$[1,2]$\hspace{1cm}$[3]$\hspace{1cm}$[4]
$\hspace{1cm}$[5]$\hspace{1cm}$[6]$\hspace{1cm}$[7]$

$\stackrel{3}{\sim}$:
\begin{center}
\begin{tabular}{l|l|l}
    & a                            & b                            \\ \hline
  0 & $[1,2]_{\stackrel{2}{\sim}}$ & $[0]_{\stackrel{2}{\sim}}$   \\
  1 & $[3]_{\stackrel{2}{\sim}}$   & $[1,2]_{\stackrel{2}{\sim}}$ \\
  2 & $[3]_{\stackrel{2}{\sim}}$   & $[1,2]_{\stackrel{2}{\sim}}$ \\
  3 & $[3]_{\stackrel{2}{\sim}}$   & $[4]_{\stackrel{2}{\sim}}$   \\
  4 & $[6]_{\stackrel{2}{\sim}}$   & $[5]_{\stackrel{2}{\sim}}$   \\
  5 & $[1,2]_{\stackrel{2}{\sim}}$ & $[4]_{\stackrel{2}{\sim}}$   \\
  6 & $[3]_{\stackrel{2}{\sim}}$   & $[7]_{\stackrel{2}{\sim}}$   \\
  7 & $[1,2]_{\stackrel{2}{\sim}}$ & $[7]_{\stackrel{2}{\sim}}$   \\
\end{tabular}
\end{center}
Damit sind die Klassen von $\stackrel{3}{\sim}$:
\hspace{1cm}$[0]$\hspace{1cm}$[1,2]$\hspace{1cm}$[3]$\hspace{1cm}$[4]
$\hspace{1cm}$[5]$\hspace{1cm}$[6]$\hspace{1cm}$[7]$

Die Klassen von $\stackrel{3}{\sim}$ sind jetzt identisch zu den
Klassen von $\stackrel{2}{\sim}$, d.h.~$\stackrel{3}{\sim} =
\stackrel{2}{\sim} = \sim$, das Verfahren endet hier. Der minimierte
Automat sieht also so aus:
\begin{center}
  \includegraphics{Blatt04-DFA-minimiert-13.eps}
\end{center}

\section*{Aufgabe 14}
\textbf{a)} Der NFA, der $L_n$ akzeptiert, könnte wie folgt aussehen:
\begin{center}
  \includegraphics{Blatt04-Darstellung-14.eps}
\end{center}
Nach dem Startzustand $q_0$ kommen zunächst maximal $n-1$ Zustände
$q_i$, in denen das Teilwort $x$ verarbeitet wird. Spätestens nach
$q_{n-1}$ muß dann die 1 kommen. Mit der 1 wird in Zustand $p_0$
gewechselt, ab dem die Abarbeitung von $y$ beginnt. Nach $p_0$ müssen
genau $n$ Zeichen kommen, damit der Automat im akzeptierenden Zustand
$p_n$ landet.

Durch Induktion wird für alle $w \in \Sigma^*$ gezeigt: $q_i \in
\delta(q_0,w) \Leftrightarrow |w| = i \wedge 0 \leq |w| \leq n-1$.

$p_i \in \delta(q_0,w) \Leftrightarrow w = w'1w'' \wedge |w''| = i, 0
\leq |w''| \leq n, 0 \leq |w'| \leq n-1$.
\begin{eqnarray*}
  w \in T(M)
  &\Leftrightarrow& \delta(q_0,w) \cap F \neq \emptyset\\
  &\Leftrightarrow& p_n \in \delta(q_0,w)\\
  &\Leftrightarrow& w = w'1w'', |w''| = n, 0 \leq |w'| \leq n-1\\
  &\Leftrightarrow& w \in L_n~~\Box
\end{eqnarray*}

\textbf{b)} Sei $M = (Q, \Sigma, \delta, q_0, F)$ ein beliebiger NFA
für $L_n$. Zu zeigen: $|Q| \geq 2n + 1$.

\emph{Annahme:} $|Q| \leq 2n + 1$. Offensichtlich ist $L_n$ endlich
und die maximale Länge eines $w \in L$ beträgt $|w| = 2n$. Man
betrachte ein solches $w$ mit maximaler Länge.

\emph{Behauptung:}
\begin{displaymath}
\forall i: 0 \leq i \leq 2n: w = w_i'w_i'', |w_i'|
= i, |w_i''| = 2n - i: \exists q_i \in Q: \delta(q_0, w_i') \ni q_i
\wedge \delta(q_0,w) \cap F \neq \emptyset
\end{displaymath}
\emph{Beweis:} Angenommen, $q_i$ existiert nicht. Dann ist
$\delta(q_0,w) \cap F = \emptyset~~\blitz$. Wegen $|Q| < 2n+1$ gibt es 
ein $i,j,i < j$ mit $q_i = q_j = p$. Es folgt
\begin{eqnarray}
  &&p \in \delta(q_0,w_j') \wedge |w_j'| = j \\
  &&p \in \delta(q_0,w_i') \wedge |w_i'| = i \\
  &&\delta(p, w_j'') \cap F \neq \emptyset \wedge |w_j''| = 2n-j\\
  &&\delta(p,w_i'') \cap F \neq \emptyset \wedge |w_i''| = 2n-i\\
  &\text{Aus (1) und (4) folgt} 
  &\delta(q_0, w_j'w_i'') \supseteq \delta(p,w_i'')\\
  &\Rightarrow& \delta(q_0, w_j'w_i'') \cap F \neq \emptyset
\end{eqnarray}
Also folgt $w_j'w_i'' \in T(M)$. Es ist aber $|w_j'w_i''| = 2n - i + j 
> 2n+1~~\blitz$

\textbf{c)} Jeder DFA für $L_n$ hat mehr als $2^{n+1}$ Zustände. Seien
$w_1, w_2 \in L_n$ mit $w_1 \neq w_2$. Dann ist $w_1 = a_ra_{r-1}\dots
a_2a_1$ und $w_2 = b_sb_{s-1}\dots b_2b_1$ mit o.B.d.A.~$1 \leq r, s
\leq n, a_i, b_i \in \Sigma$.
\begin{itemize}
\item $r \neq s$: mit $u = 0^{n-r-1}$ gilt $w_1u \in L_n$ aber $w_2u
  \notin L_n$ wegen $|w_2u| > 2n \\ \Rightarrow \delta(q_0,w_1) \neq
  \delta(q_0, w_2)$
\item $r = s: u = 0^{n-i-1}$. $\delta(q_0,w_1u) \neq \delta(q_0,w_2u)$
\end{itemize}
Also $2^{n+1}-2$ Worte plus akzeptierender Zustand plus Startzustand
sind $2^{n+1}$. Rest analog zu Skript.

\section*{Aufgabe 15}
Die drei Aussagen entsprechen im Wesentlichen dem Satz von
Myhill-Nerode, bis auf die Definition der Relation. Der Beweis kann
daher in weiten Teilen analog zum Skript geführt werden.

"`$1 \Rightarrow 2$"': Sei $R \subseteq \Sigma^*$ eine reguläre
Sprache. Dann existiert ein DFA $M = (Q, \Sigma, \delta, q_0, F)$ mit
$T(M) = R$.

Für jedes $x \in \Sigma^*$ definiert man $\delta_x: Q \rightarrow Q$
vermöge $\delta_x(q) = \delta(q,x)$ für alle $q \in Q$. Man definiere
die Relation $\sim: \sim \subseteq (\Sigma^* \times \Sigma^*)$ wie
folgt:
\begin{eqnarray*}
  x \sim y
  &\Leftrightarrow& \delta_x = \delta_y \\
  &\Leftrightarrow& \forall q \in Q: \delta(q,x) = \delta(q,y)
\end{eqnarray*}
Reflexivität und Symmetrie: $\checkmark$

Transitivität: Sei $x \sim y$ und $y \sim z$. Dann ist $\delta_x =
\delta_y$ und $\delta_y = \delta_z$, d.h.~es gilt auch $\delta_x =
\delta_z$ und damit $x \sim z$. Also ist $\sim$ transitiv und eine
Äquivalenzrelation.

Für jedes $x,y \in \Sigma^*$ und $q \in Q$ gilt $\delta_{xy}(q) =
\delta(q,xy) = \delta(\delta(q,x),y) = \delta_y(\delta_x(q)) =
\delta_x \circ d_y(q)$.

Also ist $\delta_{xy} = \delta_x \circ \delta_y$. Sei $x \sim y$ und
$z \in \Sigma^*$ beliebig. Es gilt $\delta_{xz} = \delta_x \circ
\delta_z = \delta_y \circ \delta_z = \delta_{yz}$. Damit ist $xz \sim
yz$, und $\sim$ ist rechtsinvariant. Ebenso gilt $\delta_{zx} =
\delta_z = \delta_x = \delta_z \circ \delta_y = \delta_{zy}$. Damit
ist $\sim$ linksinvariant, also eine Kongruenzrelation.

$Q \rightarrow Q$: Es gibt $|Q| \cdot |Q|$ viele verschiedene
Funktionen von $Q \rightarrow Q$. Damit ist der Index von $\sim$
endlich. Es ist außerdem $T(M) = \{ \langle x
\rangle_{\sim}|\delta_x(q_0) \in F \}~~\Box$
\end{document}