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

\begin{document}

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

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

\section*{Aufgabe 5}

Automat für $L$:
\begin{center}
  \includegraphics{Blatt02-Automat-5.eps}
\end{center}
Wir zeigen durch Induktion nach $|w|$:
\begin{eqnarray*}
  &&\delta(q_0,w)=q_0 \Leftrightarrow w=1^i~\text{ für ein }i \geq 0\\
  &&\delta(q_0,w)=q_1 \Leftrightarrow w=1^i0^j\text{ für } i \geq 0, j
  \geq 1\\
  &&\delta(q_0,w)=q_2 \Leftrightarrow w=x01y:x,y \in \Sigma^*
\end{eqnarray*}
{\bfseries Induktionsverankerung:} $|w|=0~~\surd~~~~(|w|=1~~\surd~~)$

{\bfseries Induktionsschluß:} Sei die Behauptung für alle $w \in
\Sigma^*$ mit $|w|=n$ bewiesen und $x=w\sigma$ mit $|w|=n$ und $\sigma
\in \Sigma$.
\begin{eqnarray*}
  \delta(q_0, w \sigma) = q_0
  & \Leftrightarrow & \delta (q_0, w) = q_0 \wedge \sigma = 1 \\
  & \Leftrightarrow & w = 1^i, i \geq 0 \wedge \sigma = 1 \\
  & \Leftrightarrow & w \sigma = 1^i, i \geq 0 \\
    \delta (q_0, w \sigma) = q_1
  & \Leftrightarrow & (\delta (q_0, w) = q_0 \wedge
    \sigma=0) \vee (\delta (q_0, w) = q_1 \wedge \sigma = 0) \\
  & \Leftrightarrow & (w = 1^i, i \geq 0 \wedge \sigma = 0)\vee (w =
    1^i0^j, i \geq 0, j \geq 1 \wedge \sigma = 0) \\
  & \Leftrightarrow & (w \sigma = 1^i0, i \geq 0) \vee (w \sigma =
    1^i0^j, i \geq 0, j \geq 1) \\
    \delta(q_0,w \sigma) = q_2
  & \Leftrightarrow & (\delta(q_0, w) = q_1 \wedge \sigma=1) \vee 
    (\delta (q_0, w) = q_2 \wedge \sigma \in \{0,1\}) \\
  & \Leftrightarrow & (w=1^i0^j, i \geq 0, j \geq 1, \sigma = 1) \vee
    (w = u01v, u,v \in \{0,1\}^*, \sigma \in \{0,1\}) \\
  & \Leftrightarrow & w \sigma = u01v, u,v \in \{0,1\}^* \\ \\
    \forall w \in \Sigma^*: \\
    w \in T(M)
  & \Leftrightarrow & \delta(q_0, w) \in F \\
  & \Leftrightarrow & \delta(q_0, w) = q_2 \\
  & \Leftrightarrow & w = u01v, u,v \in \{0,1\}^*~~\Box
\end{eqnarray*}

\section*{Aufgabe 6}
Gegeben: $m \in \mathbb{N}, L_m \subseteq \{0,1\}^*, w=a_n \dots
a_1a_0 \in L_m \Leftrightarrow q(w) = \sum_{0 \leq i \leq n}a_i \cdot
2^i$ ist durch $m$ teilbar.

\subsection*{a)}
Es soll ein DFA für $L_m$ mit höchstens $m$ Zuständen konstruiert
werden.

{\bfseries Idee:} Speichere in den Zuständen die Restklasse modulo $m$
der durch das gelesene Wort repräsentierten Zahl, denn falls $\varphi
(x)$ mod $m=r$, dann ist $\varphi(x0)$ mod $m=2r$ mod $m$ und
$\varphi(x1)$ mod $m=2r+1$ mod $m$. $\varphi$ ist die mit dem Wert
assoziierte Zahl.

Man definiere den DFA $M=(Q, \Sigma, \delta, q_0, F)$ mit
\begin{eqnarray*}
  Q
  & = & \{q_i|0 \leq i \leq m-1 \} \\
    \delta(q_i,0)
  & = & q_{(2i) \text{ mod }m} \forall q_i \in Q \\
    \delta(q_i,1)
  & = & q_{(2i+1) \text{ mod }m} \forall q_i \in Q
\end{eqnarray*}

Durch Induktion läßt sich zeigen: $\forall w \in \Sigma^* : \delta
(q_0, w) = q_{\varphi (w)} $ mod $r$.
\begin{eqnarray*}
    \forall w \in \Sigma^*: w \in T(M)
  & \Leftrightarrow & \delta(q_0, w) \in F \\
  & \Leftrightarrow & \delta(q_0, w) = q_0 \\
  & \Leftrightarrow & \delta(w) \text{ mod } r=0~~\Box
\end{eqnarray*}

\subsection*{b)}

Es soll ein DFA mit $k+1$ Zuständen konstruiert werden, der $L_m$ mit
$m=2^k$ versteht. Wie man zeigen kann, ist für alle $w \in \Sigma^*~
\varphi (w)$ genau dann durch $m=2^k$ teilbar, wenn die letzten $k$
Stellen von $w~0$ sind, $w=x0^k$ oder $w_0 = 0^l,l \geq 0 \rightarrow$
Konstruktion eines DFA für $L_m=\{x0^k|x \in \Sigma \} \cup \{0^l | l
\geq 0\}$.

\begin{center}
  \includegraphics{Blatt02-Automat-6b.eps}
\end{center}

\section*{Aufgabe 7}

$h(0) = a, h(1) = c$. Der Monoid $\langle M,\circ \rangle$ läßt sich
durch folgendes Diagramm darstellen:

\begin{center}
  \includegraphics{Blatt02-Diagramm-7.eps}
\end{center}

{\bfseries Idee:} $h^{-1}(a) = \{ u0v | uv \in \{0,1\}^*\}, h^{-1}(c)
= \{ 1^i | i \geq 1 \}$.

Wir zeigen: $\forall w \in \Sigma^+: h(w) = c \Leftrightarrow w = 1^k$
für ein $k \geq 1$.

"`$\Rightarrow$"': Induktion über $k$

Verankerung: $k=1: h(1) = c~~\surd$

Schluß: $n \rightarrow n+1: h(1^{n+1}) = h(1^n) \circ h(1) = c \circ c
= c ~~\surd$

"`$\Leftarrow$"': Induktion über $|w|$

Verankerung: $|w| = 1 \Rightarrow h(0) = a, h(1) = c~~\surd$

Schluß: $|w| = n+1 \Rightarrow w = x\sigma, |w|=n, \sigma \in \Sigma.~
h(x\sigma) = h(x) \circ h(\sigma)$

{\bfseries Fallunterscheidung:}
\begin{itemize}
\item $\sigma=0: h(x) \circ h(0) = h(x) \circ a = a \forall h(x) \in
  M$, also $h(x\sigma) \neq c$
\item $\sigma=1$:

  \begin{math}
    h(x) \circ h(1) = h(x) \circ c\\
    h(x) = a \Rightarrow h(x) \circ c = a \circ c = a\\
    h(x) = b \Rightarrow h(x) \circ c = b \circ c = c\\
    h(x) = c \Rightarrow h(x) \circ c = c \circ c = c\\
    h(x) = b \text{ kommt nicht vor für } x \neq \varepsilon
  \end{math}
\end{itemize}

Für $h(x)=c$ gilt nach Induktionsvoraussetzung $x=1^n$, also
$x\sigma = 1^{n+1}~~\Box$

Für alle $w \in \Sigma^+$ gilt $h(w)=a \vee h(w) = c$. Also ist
$h^{-1} (a) = \Sigma^+ - h^{-1}(c) = \{u0v | u,v \in \Sigma^*\}
~~\Box$

\section*{Aufgabe 8}
Gegeben: Zwei DFA $M_i = (Q_i,\Sigma_i,\delta_i,q_0^i,F_i), i=1,2$.
\subsection*{a)}
Es soll ein DFA $M'$ mit $T(M')=T(M_1)\cup T(M_2)$ ohne Verwendung der
Potenzmengenkonstruktion konstruiert werden.

{\bfseries Idee:} Verwendung des Kreuzproduktes.
\begin{center}
  \includegraphics{Blatt02-Modell-8a.eps}
  \begin{tabular}{cc}
    $M_1$        & $M_2$ \\
    $\downarrow$ & $\downarrow$\\
    $[q_0^1$    & $q_0^2]$\\
    $\downarrow$ & $\downarrow$\\
    $[q_1$       & $p_1]$\\ \\
    \multicolumn{2}{c}{Kreuzprodukt}
  \end{tabular}
\end{center}
Man definiert also den DFA $M'=(Q,\Sigma,\delta,[q_0^1,q_0^2],F)$ mit
$Q_1 \times Q_2 = Q = \{[p,q]|p \in Q_1, q \in Q_2 \}$. $\delta
([p,q], \sigma)= [\delta_1(p,\sigma),\delta_2(q,\sigma)]$ für alle
$[p,q] \in Q,\sigma \in \Sigma$. $F=\{[p,q]|p \in F_1 \vee q \in F_2
\} \rightarrow $ "`$F_1 \times Q_2 \times Q_1 \times F_2$"'

Zu zeigen: $T(M') = T(M_1) \cup T(M_2)$.

Durch Induktion nach der Länge von $w$ zeigt man: $\forall [p,q] \in
Q, w \in \Sigma^*: \delta ([p,q],w)=[\delta_1(p,w),\delta_2(q,w)]$.

{\bfseries Induktionsverankerung:} $|w|=0 \Rightarrow
w=\varepsilon$. $\delta ([p,q],\varepsilon)=[p,q]=[\delta_1(p,\varepsilon),
\delta_2(p,\varepsilon)]~~\surd$

{\bfseries Induktionsschluß:} Sei die Behauptung für $n$ bewiesen und
$|w|=n+1$. Dann gilt $w=x\sigma, \sigma \in \Sigma$. Es ist
\begin{eqnarray*}
  \delta([p,q],w) &=& \delta([p,q],x\sigma) \\
  &=& \delta(\delta([p,q],x),\sigma)\\
  &=& \delta([\delta_1(p,x),\delta_2(q,x)],\sigma)\\
  &=&
  [\delta_1(\delta_1(p,x),\sigma),\delta_2(\delta_2(q,x),\sigma)]\\
  &=& [\delta_1(p,x\sigma),\delta_2(q,x\sigma)]~~\Box
\end{eqnarray*}

Wie folgt daraus $T(M')=T(M_1)\cup T(M_2)$?
\begin{eqnarray*}
  w \in T(M') &\stackrel{\text{def }T(M)}{\Leftrightarrow}& \delta
  ([q_0^1,q_0^2],w) \in F \\
  &\Leftrightarrow& [\delta_1(q_0^1,w),\delta_2(q_0^2,w)] \in F \\
  &\Leftrightarrow& \delta_1(q_0^1,w)\in F_1 \vee \delta_2(q_0^2,w)
  \in F_2\\
  &\Leftrightarrow& \\
  &\Leftrightarrow& \\
\end{eqnarray*}

\subsection*{b)}
Konstruktion aus 8a) hat $|Q_1|\cdot|Q_2|$ Zustände --- zu groß!
{\bfseries Idee:} Zu Beginn "`erraten"', ob $w \in T(M_1)$ oder $w \in
T(M_2)$:
\begin{center}
  \includegraphics{Blatt02-Modell-8b.eps}
\end{center}
Formal: $M'' = (Q'',\Sigma,\delta'',q_0^{''},F'')$ mit $Q'' =
\{q_0^{''}\} \cup Q_1 \cup Q_2$; o.B.d.A. $q_0^{''} \notin Q_1 \cup
Q_2$, $Q_1 \cap Q_2 = \emptyset$.
\begin{eqnarray*}
  \delta''(q_0^{''},\sigma) &=& \{ \delta_1(q_0^1,\sigma),
  \delta_2(q_0^2, \sigma) \} \forall \sigma \in \Sigma \\
  \delta''(q,\sigma) &=& \{\delta_1(q,\sigma) \} \forall q \in Q_1,
  \sigma \in \Sigma \\
  \delta''(q,\sigma) &=& \{ \delta_2(q,\sigma) \} \forall q \in Q_2,
  \sigma \in \Sigma \\
  F'' &=& \{ q \in Q''| q \in F_1 \cup F_2 \} \cup \{ q_0^{''}| q_0^1
  \in F_1 \vee q_0^2 \in F_2 \}
\end{eqnarray*}
Durch Induktion nach der Länge von $w: \forall w \in \Sigma^*:
\delta''(q_0^{''},w) = \{ \delta_1(q_0^1,w),\delta_2(q_0^2,w) \}$
\begin{eqnarray*}
  \forall w \in \Sigma^*: w\in T(M'')
  &\Leftrightarrow& \delta^{''}(q_0^{''},w) \cap F \neq \emptyset \\
  &\Leftrightarrow& \{\delta_1(q_0^1,w),\delta_2(q_0^2,w)\} \cap \{
  F_1 \cup F_2 \} \neq \emptyset \\
  &\Leftrightarrow& \{\delta_1(q_0^1,w)\}\cap F_1 \neq \emptyset \vee
  \{ \delta_2(q_0^2,w) \} \cap F_2 \neq \emptyset \\
  &\Leftrightarrow& w \in T(M_1) \vee w \in T(M_2) \\
  &\Leftrightarrow& w \in T(M_1) \cup T(M_2)\\
  &\Leftrightarrow& T(M'') = T(M_1) \cup T(M_2)~~\Box
\end{eqnarray*}
Außerdem: $\varepsilon \in T(M'') \Leftrightarrow \varepsilon \in
T(M_1) \cup T(M_2)$
\end{document}