\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 5} \rhead{Seite
  \thepage}

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

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

\section*{Aufgabe 16}

Der Automat $M$ sieht im Schaubild wie folgt aus:
\begin{center}
  \includegraphics{Blatt05-DFA-Aufg16.eps}
\end{center}
Damit der Algorithmus aus Hopcroft/Ullman allerdings funktioniert,
\textbf{muß} der Startzustand mit dem Index \textbf{1} beginnen, da es
wegen der Rekursionsbedingung sonst zu Fehlern kommen kann, weil
$R^0_{ij}$ den Zustandsübergang unter Verwendung von \textbf{keinen}
Zwischenzuständen (auch nicht Zustand 0) darstellt. Nach
Hopcroft/Ullman lassen sich bestimmte Abschnitte des Automaten durch
den regulären Ausdruck $R^k_{ij}$ beschreiben. Dieser Ausdruck
beschreibt die Wörter, mit denen man vom Zustand $i$ nach Zustand $j$
gelangen kann, wobei aber keine Zustände als Zwischenschritte benutzt
werden dürfen, die einen höheren Index als $k$ haben. Der gesuchte
reguläre Ausdruck lautet demnach $R^4_{14}$.

Dieser Ausdruck läßt sich rekursiv berechnen. Für $R^0_{ij}$ wird der
Ausdruck wie folgt definiert:
\begin{displaymath}
  R^0_{ij} = \left\{
    \begin{array}{ll}
      \{ a | \delta(q_i,a) = q_j \} & \text{falls } i \neq j \\
      \{ a | \delta(q_i,a) = q_j \} \cup \{ \varepsilon \} &
      \text{falls } i = j
    \end{array}
  \right.
\end{displaymath}

Wenn $i=j$ besteht der reguläre Ausdruck für diesen Zustand (der
Übergang vom Zustand in sich selbst) also immer mindestens aus
$\varepsilon$.

$R^k_{ij}$ wird rekursiv wie folgt definiert:
\[ R^k_{ij} = R^{k-1}_{ik}(R^{k-1}_{kk})^*R^{k-1}_{kj} \cup
R^{k-1}_{ij} \]

Dies bedeutet: $R^k_{ij}$ besteht aus einer Zeichenkette, die von
Zustand $i$ in Zustand $j$ führt, wobei aber nur Zustände kleiner als
$k$ als Zwischenstationen benutzt werden $(= R^{k-1}_{ij})$, oder aus
einer Zeichenkette, die unter Verwendung von Zwischenzuständen
\textbf{kleiner} als $k$ zunächst von $i$ nach $k$ läuft $(=
R^{k-1}_{ik})$, dann beliebig lange (möglicherweise auch gar nicht) in
diesem Zustand bleibt $(= (R^{k-1}_{kk})^*)$, um dann von dort nach
$j$ weiter zu laufen $(= R^{k-1}_{kj})$.

Die 16 Ausdrücke für $R^0_{ij}$ lauten:
\begin{displaymath}
  \begin{array}{llll}
    R^0_{11} = b + \varepsilon  & R^0_{21} = \emptyset        &
    R^0_{31} = a                & R^0_{41} = a                \\
    R^0_{12} = a                & R^0_{22} = a + \varepsilon  &
    R^0_{32} = \emptyset        & R^0_{42} = b                \\
    R^0_{13} = \emptyset        & R^0_{23} = b                &
    R^0_{33} = \varepsilon      & R^0_{43} = \emptyset        \\
    R^0_{14} = \emptyset        & R^0_{24} = \emptyset        &
    R^0_{34} = b                & R^0_{44} = \varepsilon      \\
  \end{array}
\end{displaymath}

Da man nicht unbedingt noch $3 \cdot 16$ Ausdrücke berechnen möchte,
kann man sich ja mal anschauen, was man nun eigentlich effektiv
braucht. Gesucht ist der Ausdruck $R^4_{14}$.

\begin{displaymath}
  \begin{array}{l}
    R^4_{14} = R^3_{14}(R^3_{44})^* R^3_{44} \cup R^3_{14} \\ \hline
    R^3_{14} = R^2_{13}(R^2_{33})^* R^2_{34} \cup R^2_{14} \\
    R^3_{44} = R^2_{43}(R^2_{33})^* R^2_{34} \cup R^2_{44} \\ \hline
    R^2_{13} = R^1_{12}(R^1_{22})^* R^1_{23} \cup R^1_{13} \\
    R^2_{14} = R^1_{12}(R^1_{22})^* R^1_{24} \cup R^1_{14} \\
    R^2_{33} = R^1_{32}(R^1_{22})^* R^1_{23} \cup R^1_{33} \\
    R^2_{34} = R^1_{32}(R^1_{22})^* R^1_{24} \cup R^1_{34} \\
    R^2_{43} = R^1_{42}(R^1_{22})^* R^1_{23} \cup R^1_{43} \\
    R^2_{44} = R^1_{42}(R^1_{22})^* R^1_{24} \cup R^1_{44} \\ \hline
    R^1_{12} = R^0_{11}(R^0_{11})^* R^0_{12} \cup R^0_{12} \\
    R^1_{13} = R^0_{11}(R^0_{11})^* R^0_{13} \cup R^0_{13} \\
    R^1_{14} = R^0_{11}(R^0_{11})^* R^0_{14} \cup R^0_{14} \\
    R^1_{22} = R^0_{21}(R^0_{11})^* R^0_{12} \cup R^0_{22} \\
    R^1_{23} = R^0_{21}(R^0_{11})^* R^0_{13} \cup R^0_{23} \\
    R^1_{24} = R^0_{21}(R^0_{11})^* R^0_{14} \cup R^0_{24} \\
    R^1_{32} = R^0_{31}(R^0_{11})^* R^0_{12} \cup R^0_{32} \\
    R^1_{33} = R^0_{31}(R^0_{11})^* R^0_{13} \cup R^0_{33} \\
    R^1_{34} = R^0_{31}(R^0_{11})^* R^0_{14} \cup R^0_{34} \\
    R^1_{42} = R^0_{41}(R^0_{11})^* R^0_{12} \cup R^0_{42} \\
    R^1_{43} = R^0_{41}(R^0_{11})^* R^0_{13} \cup R^0_{43} \\
    R^1_{44} = R^0_{41}(R^0_{11})^* R^0_{14} \cup R^0_{44} \\
  \end{array}
\end{displaymath}

Die Ergebnisse lauten damit:
\begin{displaymath}
  \begin{array}{ll}
    R^1_{12} = (b + \varepsilon) b^* a + a = b^* a + a = b^* a &
    R^1_{13} = b^* \emptyset + \emptyset = \emptyset   \\
    R^1_{14} = b^* \emptyset + \emptyset = \emptyset   &
    R^1_{22} = \emptyset b^* a + (a + \varepsilon) = a + \varepsilon \\
    R^1_{23} = \emptyset b^* \emptyset + b = b &
    R^1_{24} = \emptyset b^* \emptyset + \emptyset = \emptyset \\
    R^1_{32} = (a b^* a) + \emptyset = ab^*a &
    R^1_{33} = ab^*\emptyset + \varepsilon = \varepsilon \\
    R^1_{34} = ab^* \emptyset + b = b &
    R^1_{42} = (ab^*a) + b \\
    R^1_{43} = ab^* \emptyset + \emptyset = \emptyset &
    R^1_{44} = a b^* \emptyset + \varepsilon = \varepsilon \\ \hline
    R^2_{13} = (b^*a+a)a^*b + \emptyset = b^* a^+ b &
    R^2_{14} = b^*a a^* \emptyset + \emptyset = \emptyset \\
    R^2_{33} = ab^*a a^*b + \varepsilon = ab^*a^+b + \varepsilon &
    R^2_{34} = ab^*a a^* \emptyset + b = b \\
    R^2_{43} = ((ab^*a)+b) a^* b + \emptyset = (ab^*a + b) a^*b &
    R^2_{44} = ((ab^*a) + b) a^* \emptyset + \varepsilon = \varepsilon \\ \hline
    R^3_{14} = b^*a^+b (ab^*a^+b)^* b &
    R^3_{44} = (ab^*a+b)a^*b (ab^*a^+b)^* b + \varepsilon \\ \hline
    \multicolumn{2}{l}
    {R^4_{14} = b^*a^+b(ab^*a^+b)^*b ((ab^*a+b)a^*b (ab^*a^+b)^* b)^* +  b^*a^+b (ab^*a^+b)^* b} \\
    \multicolumn{2}{l}
    {\mathbf {R^4_{14} = b^*a^+b(ab^*a^+b)^*b ((ab^*a+b)a^*b (ab^*a^+b)^* b)^*}}
  \end{array}
\end{displaymath}

Anmerkung: $(a + \varepsilon)^*$ läßt sich auskürzen zu $a^*$. Eine
Konkatenation mit der leeren Menge führt dazu, daß der gesamte
Teilausdruck leer ist.

\section*{Aufgabe 17}
$R \subseteq \Sigma^*$ ist eine reguläre Sprache. Es ist zu zeigen:
$MT(R) = \{ y | \exists x,z \in \Sigma^*: |x| = |y| = |z| \wedge xyz
\in R \}$ ist regulär, wobei $MT$ für \emph{Mittelteil} steht.

\textbf{Beweis:} $R$ ist regulär, d.h.~es gibt einen DFA $M = (Q,
\Sigma, \delta, q_0, F)$ mit $T(M) = R$. Definiert wird ein MNFA $M' =
(Q', \Sigma, \delta', Q_0, F')$ mit folgenden Eigenschaften:
\begin{eqnarray*}
  Q' &=& Q \times Q \times Q \times Q \times Q \\
  Q_0 &=& \{ [q_0, p, p, q, q]| p, q \in Q \} \\
  F' &=& \{ [p, p, q, q, f]| p, q \in Q, f \in F \} \\
  \delta'([ q_1, q_2, q_3, q_4, q_5 ], a) &=& \{ [ \delta(q_1,\sigma), q_2,
  \delta(q_3,\sigma), q_4, \delta(q_5, \tau) ] , \sigma, \tau, a \in
  \Sigma \}
\end{eqnarray*}
$\delta'$ wird wie üblich auf Wörter aus $\Sigma^*$ erweitert.

\textit{Behauptung:}
\begin{eqnarray*}
  [ p_1, p_2, p_3, p_4, p_5 ] \in \delta'([q_1, q_2, q_3, q_4, q_5],w)
  &\Leftrightarrow&
  \exists~x \in \Sigma^*: |x| = |w|\\
  && \wedge~ \delta(q_1,x)=p_1\\
  && \wedge~ q_2 = p_2\\
  && \wedge~ \delta(q_3, w) = p_3\\
  && \wedge~ q_4 = p_4 \\
  && \wedge~ \exists~ z \in \Sigma^*: |z| = |w|\\
  && \wedge~ \delta(q_5,z) = p_5
\end{eqnarray*}

\emph{Beweis} durch Induktion nach $|w|$:
\begin{eqnarray*}
  y \in T(M')
  &\Leftrightarrow& \delta'(Q_0, y) \cap F' \neq \emptyset \\
  &\Leftrightarrow& \exists~ p,q ,p',q' \in Q, f \in F \text{ mit }
  [p,p,q,q,f] \in \delta'([q_0,p',p',q'q'],y)\\
  &\Leftrightarrow& \exists~ x \in \Sigma^*: (|x| = |y|)\\
  && \wedge~ \delta(q_0,x) = p\\
  && \wedge~ (p'=p)\\
  && \wedge~ \delta(p',y)=q\\
  && \wedge~ (q'=q)\\
  && \wedge~ (\exists~ z \in \Sigma^*: |z| = |y|\\
  && \wedge~ \delta(q',z) = f)\\
  &\Leftrightarrow& \exists~ x,z \in \Sigma^*: p,q \in Q, f \in F:
  (\delta(q_0,xyz)\\
  && =\delta(\delta(q_0, x), yz)\\
  && = \delta(p, yz)\\
  && =\delta(\delta( p, y), z)\\
  && = \delta(q,z) = f)\\
  && \wedge~ (|x| = |y| = |z|) \\
  &\Leftrightarrow& \exists~ x,z \in \Sigma^*: (|x| = |y| = |z|) \wedge
  (xyz \in R)\\
  &\Leftrightarrow& y \in MT(R)
\end{eqnarray*}
\emph{Induktionsverankerung:} $|w| = 0 \Rightarrow w =
\varepsilon~~\checkmark$\hspace{1cm}$|w| = 1 \Rightarrow w = a \in
\Sigma~~\checkmark$

\emph{Induktionsannahme:} Behauptung gilt für $|w| = n$.

\emph{Induktionsschluß:} $|w| = n+1 \Rightarrow w = w_1w_2 \dots
w_nw_{n+1}$, das heißt
\begin{eqnarray*}
  [p_1, p_2, p_3, p_4, p_5] \in \delta'([q_1, q_2, q_3, q_4, q_5, ],
  w_1 \dots w_n) 
  &\Leftrightarrow& \exists~ x \in \Sigma^*: |x|=n \\
  && \wedge~ \delta(q_1, x) = p_1 \\
  && \wedge~ (q_2 = p_2) \\
  && \wedge~ \delta(q_3, w_1 \dots w_n)=p_3 \\
  && \wedge~ q_n = p_n \\
  && \wedge~ \exists~ z \in \Sigma^*: |z| = n \\
  && \wedge~ \delta(q_5,z) = p_5
\end{eqnarray*}
\begin{eqnarray*}
  &&\delta'([q_1, q_2, q_3, q_4, q_5], w_1 \dots w_nw_{n+1}) \\
  &&= \bigcup_{[s_1, s_2, s_3, s_4, s_5]} \delta'([s_1, s_2, s_3, s_4,
  s_5],w_{n+1}) \in \delta'([q_1, q_2, q_3, q_4, q_5], w_1 \dots
  w_n)\\
  && \stackrel{\text{IV}}{=} \bigcup_{[s_1, s_2, s_3, s_4, s_5] \text{
      mit }(*)} \{ [\delta(s_1,\sigma), s_2, \delta(s_3, w_{n+1}),
  s_4, \delta(s_5, \tau)]|\sigma, \tau \in \Sigma \}
\end{eqnarray*}
\begin{eqnarray*}
  (*)\hspace{1cm} \exists~ x \in \Sigma^*: && \delta(q_1, x) = s_1\\
  && \wedge~ s_2 = s_2\\
  && \wedge~ \delta(q_3, w_1 \dots w_n) = s_3\\
  && \wedge~ q_4 = s_4\\
  && \wedge~ \exists~ z \in \Sigma^*: \delta(q_5, z)=s_5\\
  && \wedge~ |x|=|z|=n
\end{eqnarray*}
Einsetzen:
\begin{eqnarray*}
  &=&  \{ [ \delta(\delta(q_1, x), \sigma), q_2,\\
  &&  ~\delta(\delta(q_3, w_1 \dots w_n),w_{n+1}), q_4,\\
  &&  ~\delta(\delta(q_5, z),\tau) ] | \sigma, \tau \in \Sigma 
      \text{ und } \exists~ x, z \in \Sigma: |x| = |z| = n \}\\
  &=& \{ [ \delta(q_1, x'), q_2, \delta(q_3, w), q_4, \delta(q_5,z')
  ]| \exists~ x', z' \in \Sigma^*: |x'| = |z'| = n+1 \}\\
  &\Rightarrow& [p_1, p_2, p_3, p_4, p_5 ] \in \delta'([ q_1, q_2,
  q_3, q_4, q_5], w_1 \dots w_{n+1}) \\
  &\Leftrightarrow& \exists~ x \in \Sigma^*: |x| = n+1\\
  && \wedge~ \delta(q_1, x) = p_1 \\
  && \wedge~ q_2 = p_2 \\
  && \wedge~ \delta(q_3, w_1 \dots w_{n+1}) = p_3 \\
  && \wedge~ (q_4 = p_4) \\
  && \wedge~ (\exists~ z \in \Sigma^*: |z| = n+1 \wedge \delta(q_5, z)
  = p_5)
\end{eqnarray*}
Der Induktionsschritt war richtig, die Behauptung ist also wahr.

\section*{Aufgabe 18}

Es läßt sich intuitiv feststellen, daß die Aussagen b) und c) falsch
sind, weil bei b) der Ausdruck auf der linken Seite mit einem $s$
beginnt und auf der rechten Seite mit einem $r$. Bei c) kann man mit
dem Ausdruck auf der linken Seite Zeichenketten $rsrsrs\dots$ bilden,
während rechts nur $rrrrr\dots$ oder $sssss\dots$ möglich sind.

Beweise durch Gegenbeispiele: Seien die regulären Ausdrücke $r,s$ wie
folgt belegt: $r = a, s = b$.

\textbf{b)} $ba \in s(rs+s)^*r = ab \in rr^*s(rr^*s)^*~~\blitz$

\textbf{c)} $abab \in (r + s)^* = aaaa \in r^* + s^*~~\blitz$

Die Beweise für die wahren Aussagen kann ich leider nur auf
Verständnisebene führen, aber nicht formal, und da das dann sowieso
nix wert ist, lasse ich es einfach. Wird schon nicht in der Klausur
kommen \texttt{:-/}

\section*{Aufgabe 19}
\textbf{a)} $L_1 \subseteq \Sigma^*$ ist regulär und $L_2 \subseteq
\Sigma^*$ beliebig.

\emph{Behauptung:} $L_1 / L_2 = \{ x | \exists~ y \in L_2: xy \in L_1$
ist regulär.

\emph{Beweis:} Da $L_1$ regulär ist, gibt es einen DFA $M' = (Q,
\Sigma, \delta, q_0, F)$ mit $T(M) = L_1$. Man definiere einen DFA $M'
= (Q, \Sigma, \delta, q_0, F')$ mit $F' := \{ q \in Q | \exists~ y \in
L_2: \delta(q,y) \in F \}$. Es gilt:
\begin{eqnarray*}
  x \in T(M') &\Leftrightarrow& \delta(q_0,x) \in F' \\
  &\Leftrightarrow& \delta(q_0,x)=q \wedge q \in F'\\
  &\Leftrightarrow& \delta(q_0,x) = q \wedge (\exists~ y \in L_2:
  \delta(q,y) \in F)\\
  &\Leftrightarrow& \exists~ y \in L_2: xy \in L_1\\
  &\Leftrightarrow& x \in L_1 / L_2
\end{eqnarray*}
Also ist $T(M') = L_1 / L_2$ und $L_1 / L_2$ somit
regulär.\hspace{1cm}$\Box$

\textbf{b)} \emph{Behauptung:} Die regulären Sprachen sind nicht
\textbf{nicht} abgeschlossen unter abzählbar unendlicher Vereinigung.

\emph{Beweis} [durch Gegenbeispiel]: Man definiere für jedes $n \in
\mathbb{N}$ die Sprache $L_n := \{ a^nb^n \}$. Jede einzelne $L_n$ ist
endlich und somit eine reguläre Sprache. Allerdings ist \[ L =
\bigcup_{n=0}^{\infty} \{ a^nb^n \} = \{ a^nb^n | n \geq 0 \}, \] was
ja bekanntlich keine reguläre Sprache ist.\hspace{1cm}\blitz
\end{document}