\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
\parindent0pt

\begin{document}

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

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

Ein MNFA wird als NFA mit mehreren Anfangszuständen definiert: $M=
(Q,\Sigma, \delta, Q_0, F)$ mit $Q_0=$ Menge von Startzuständen. Die
Sprache, die der Automat akzeptiert, ist
$$T(M) = \{ w \in \Sigma^*|\delta(Q_0, w) \cap F \neq \emptyset \}$$
Die Übergangsfunktion ist $\delta: Q \times E \rightarrow 2^Q$. Diese
wird nun auf Wörter erweitert:
$$\hat{\delta}=2^Q \times \Sigma^*\rightarrow 2^Q$$
\begin{eqnarray*}
  \hat{\delta}(A,\varepsilon) &\stackrel{\text{def}}{=}& A \forall A \in
  2^Q \\
  \hat{\delta}(A,w\sigma) &\stackrel{\text{def}}{=}& \bigcup_{p \in
  \hat{\delta}(A,w)} \delta (p,\sigma) \forall A \in 2^Q,w \in
  \Sigma^*, \sigma \in \Sigma
\end{eqnarray*}
Konventionsgemäß sagt man: $\hat{\delta} = \delta.$

\section*{Aufgabe 9}

Gegeben: MNFA $M=(Q,\Sigma,\delta,Q_0,F)$. Zu zeigen: Die Sprache
$T(M)$, die dieser Automat akzeptiert, ist regulär.

Wie kann man das zeigen?
\begin{itemize}
\item Konstruktion eines DFA $M'$ mit $T(M')=T(M)$
\item Konstruktion eines NFA $M'$ mit $T(M')=T(M)$
\item Zeige, daß der Index der Nerode--Relation endlich ist.
\end{itemize}
Der Beweis wird hier über die Konstruktion eines DFA geführt.

{\bfseries Idee:} Potenzmengenkonstruktion. Konstruiere DFA $M' =
(Q',\Sigma, \delta',[Q_0],F')$.
\begin{eqnarray*}
  Q' &=& \{ [A]|A \in 2^Q \} \\
  F' &=& \{ [A] \in Q' | A \cap F \neq \emptyset \} \\
  \delta'([A],\sigma) &=& [\delta(A,\sigma)] \forall [A] \in Q',
  \sigma \in \Sigma \\ \\
  T(M') &=& T(M)?
\end{eqnarray*}

Durch Induktion zeigt man für alle $w \in \Sigma^*$:
$$\delta(Q_0,w) = A \Leftrightarrow \delta'([Q_0],w) = [A]$$

Für alle $w \in \Sigma^*$:
\begin{eqnarray*}
  w \in T(M) &\Leftrightarrow& \delta(Q_0,w) = A \wedge A \cup F \neq
  \emptyset \\
  &\Leftrightarrow& \delta'([Q_0],w)=[A] \wedge [A] \in F' \\
  &\Leftrightarrow& w \in T(M')
\end{eqnarray*}
Also gilt $T(M')=T(M)~~\Box$

{\bfseries Anmerkung:} Konstruktion eines äquivalenten NFA
\begin{eqnarray*}
  M'' &=& (Q'',\Sigma,\delta'',q_0',F'') \\
  Q'' &=& Q \cup \{ q_0' \}, q_0' \notin Q \\
  F'' &=& F \cup \{ q_0' | \varepsilon \in T(M) \} \\
  \delta''(q_0',\sigma) &=& \delta(Q_0,\sigma) \forall \sigma \in
  \Sigma \\
  \delta''(q,\sigma) &=& \delta(q,\sigma) \forall q \in Q, \sigma \in
  \Sigma
\end{eqnarray*}

\section*{Aufgabe 10}

{\bfseries Idee:} Der Reversal-Automat wird konstruiert, indem die
Kanten im DFA umgedreht und somit seine Zielzustände zu Startzuständen
und der Startzustand zum Zielzustand wird.
\begin{center}
  \includegraphics{Blatt03-Automat-10.eps}
\end{center}
Zu zeigen: $T(M^R) = T(M)^R$.

Durch Induktion nach $|w|$ zeigen wir: Für alle $w \in \Sigma^*,p,q
\in Q$ gilt:
\begin{eqnarray*}
  \delta(p,w) = q &\Leftrightarrow& \delta^R(q,w^R)=p \\
  n=0: \delta(p,\varepsilon)=q &\Leftrightarrow&
  \delta^R(q,\varepsilon)=p \text{, da } p=q
\end{eqnarray*}
$n \rightarrow n+1$: Seien $p,q \in Q$ und $w\sigma \in \Sigma^{n+1},
\sigma \in \Sigma$.
\begin{eqnarray*}
  \delta(p,w\sigma) = q &\Leftrightarrow& \delta(\delta(,p,w),\sigma)
  = q \\
  &\Leftrightarrow& \exists p' \in Q: \delta(p,w)=p' \wedge \delta(p',
  \sigma)=q \\
  &\Leftrightarrow& \exists p' \in Q: p' \in \delta^R(p',w^R) \wedge
  p' \in \delta^R(q,\sigma)\\
  &\Leftrightarrow& p \in \delta^R(q,(w\sigma)^R)\\
  &\Leftrightarrow& p \in \delta^R(q,(w\sigma)^R)~~\Box \\ \\
  w \in T(M) &\Leftrightarrow& \delta(q_0,w) \in F \\
  &\Leftrightarrow& \delta(q_0,w) = f \wedge f \in F\\
  &\Leftrightarrow& q_o \in \delta^R(f,w^R) \wedge f \in F\\
  &\Leftrightarrow& q_0 \in \delta^R(F,w^R)\\
  &\Leftrightarrow& \delta^R(F,w^R) \cap \{q_0\} \neq \emptyset\\
  &\Leftrightarrow& w^R \in T(M^R) \\
  &\Leftrightarrow& T(M^R) = T(M)^R~~\Box
\end{eqnarray*}

\section*{Aufgabe 11}
$M=(Q,\Sigma,\delta,q_0,F)$ ist ein DFA ohne nicht erreichbare
Zustände. Ein Zustand $q$ ist erreichbar, falls es ein $w \in
\Sigma^*$ gibt mit $\delta(q_0,w)=q$. $M^R$ sei ein MNFA mit $T(M^R) =
T(M)^R$ wie in Aufgabe 10. $M'$ sei ein durch Potenzmengenkonstruktion
aus $M^R$ erzeugter DFA. Nach Aufgaben 9 und 10 ist $T(M') = T(M^R) =
T(M)^R$.

Zu zeigen: $M'$ ist ein minimaler DFA. Ein DFA ist minimal, wenn
\begin{itemize}
\item jeder Zustand erreichbar ist
\item $M'$ reduziert ist, d.h. $\forall [A],[B] \in Q', [A] \neq [B]$
  gibt es ein $w^R \in \Sigma^*$ mit $(\delta'([A],w^R) \in F' \wedge
  \delta'([B],w^R) \notin F) \vee (\delta([A],w^R) \notin F' \wedge
  \delta'([B],w^R \in F)$.
\end{itemize}
{\bfseries Beweis:} Jeder Zustand ist erreichbar. Noch zu zeigen: $M'$
ist reduziert.

$M$ ist ein DFA ohne nicht erreichbare Zustände. Es existiert $w \in
\Sigma^*: \delta(q_0,w)=q$. $\delta(q_0,w)=q \Leftrightarrow
\delta^R(q,w) = q_0$. Für alle $p \in Q \setminus \{q\}$:
$\delta(q_0,w) \neq p, q_0 \notin \delta^R(p,w)$.
\begin{center}
  \includegraphics{Blatt03-Darstellung-11.eps}
\end{center}
Seien $[A],[B] \in Q'$ mit $[A] \neq [B]$, dann gibt es ein $q \in R$
mit
\begin{enumerate}
\item $q \in A \wedge q \notin B$ oder
\item $q \notin A \wedge q \in B$.
\end{enumerate}
o.B.d.A. gelte (1). Da in $M$ jeder Zustand erreichbar ist, gibt es
ein $w \in \Sigma^*$ mit $\delta(q_0,w)=q$. Aus Aufgabe 10 folgt $q_0
\in \delta^R(q,w^R)$. Wegen $q_0 \in \delta^R(q,w^R) \Leftrightarrow
\delta(q_0,w)=q$ folgt $q_0 \notin \delta^R(p,w^R) \forall p \in Q$
mit $p \neq q$, denn es ist $\delta(q_0,w) \neq p$.

Damit ist $q_0 \in \delta^R(A,w^R), q_0 \notin \delta^R(B,w^r)$. Also
gilt $\delta'([A],w^R) \in F', \delta'([B],w^R) \notin F'$. Damit ist
$M'$ reduziert.$~~\Box$
\end{document}