\documentclass[12pt,a4paper]{article}
\usepackage{german}
\usepackage[latin1]{inputenc}
\usepackage{fancyhdr}
\usepackage{amstext,amssymb}
\usepackage{graphicx}
\usepackage{fancybox}
\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 6}
\rhead{Seite \thepage}

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

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

\section*{Aufgabe 20}
\textbf{a)} \emph{Behauptung:} $L_1 \stackrel{\text{Def}}{=} \{ wcw |
w \in \{ 0, 1 \}^n \}$ für ein festes $n \in \mathbb{N}$ ist eine
reguläre Sprache.

\emph{Beweis:} Man betrachte DFAs $M_i$, die genau 1 Wort aus $L_1$
erkennen. Z.B.~$n=2$: $M_1$ akzeptiert $\{ 00c00 \},~M_2~\{ 01c01 \},~
M_3~\{ 10c10 \},~M_4~\{ 11c11 \}$. Zu einem gegebenen $n \in
\mathbb{N}$ gibt es also genau $2^n$ solcher $M_i$'s, also endlich
viele. $L_1$ ist dann die endliche Vereinigung regulärer Mengen und
damit ebenfalls regulär.

\textbf{b)} \emph{Behauptung:} $L_2 \stackrel{\text{Def}}{=} \{ wcw |
w \in \{ 0, 1 \}^* \}$ ist \emph{nicht} regulär.

\emph{Beweis:} Angenommen, $L_2$ sei regulär. Dann gibt es nach dem
Pumping-Lemma eine Konstante $n \in \mathbb{N}$ und für das Wort $\{
0^nc0^n \} \in L_2$ gibt es eine Zerlegung $0^nc0^n = xyz$ mit $0 \leq
|y| \leq n$ und $xy^iz \in L_2$ für alle $i \geq 0$. Drei mögliche
Fälle können eintreten:
\begin{enumerate}
\item $y$ enthält ein $c$, dann enthält $xy^2z \in L_2~2c~~\blitz$
\item $y$ enthält kein $c$, $z$ enthält ein $c$. Dann befinden sich
  durch Pumpen links vom $c$ mehr Nullen als rechts $\Rightarrow$ Wort
  nicht in $L_2~~\blitz$
\item Analog zu 2: $y$ enthält kein $c$, $x$ enthält ein $c$. Durch
  Pumpen befinden sich rechts vom $c$ mehr Nullen als links
  $\Rightarrow$ Wort nicht in $L_2~~\blitz$
\end{enumerate}
Damit ist $L_2$ keine reguläre Sprache.

\textbf{c)} \emph{Behauptung:} $L_3 \stackrel{\text{Def}}{=} \{ w \in
\{0\}^*|~|w| \neq 2^n~\forall~n \in \mathbb{N}\}$ ist keine reguläre
Sprache.

\emph{Beweis:} Angenommen, $L_3$ sei regulär. Dann ist auch das
Komplement $\overline{L_3} = \{ w \in \{0\}^* |~|w| = 2^n~\forall~n
\in \mathbb{N}\}$ eine reguläre Sprache. Sei $n$ die Konstante des
Pumping-Lemmas und $2^m > n$. Dann besitzt $w = 0^{2^m}$ eine
Zerlegung $w = xyz$ mit $0 \leq |y| \leq n$ und $xy^2z \in
\overline{L_3}$, d.h.~$|xy^2z|$ ist die Zerlegung.

Es gilt: $2^m < 2^m+1 \leq |xy^2z| < 2^m+n < 2^m + 2^m = 2^m \cdot 2 =
2^{m+1} \Rightarrow |xy^2z|$ ist keine Zweier-Potenz$~~\blitz$

\textbf{d)} \emph{Behauptung}: $L_4 \stackrel{\text{Def}}{=} \{ ww^R |
w \in \{0,1\}^* \}$ ist keine reguläre Sprache.

\emph{Beweis:} Über Abschlußeigenschaften. Angenommen, $L_4$ ist
regulär. Dann ist auch $L_4' = L_4 \cap \{ 0^r1^s0^n | r,s,n \geq 0 \}
= \{ 0^n1^{2r}0^n | n,r \geq 0 \}$ regulär. Man betrachte einen
Homomorphismus $h_1$ mit $h_1(a)=0, h_1(b)=0,h_1(1)=1$. Dann ist
$L_4'' = h^{-1}_1(L_4') \cap \{ a^r1^sb^n | r,s,n \geq 0 \} = \{
a^n1^{2r}b^n \}$ ebenfalls regulär. Man betrachte einen weiteren
Homomorphismus $h_2$ mit $h_2(a)=a, h_2(1)=\varepsilon, h_2(b) = b$.
Dann ist $h_2(L_4'') = \{ a^nb^n | n \geq 0 \}$ ebenfalls
regulär$~~\blitz$

\section*{Aufgabe 21}
\emph{Behauptung:} $L \stackrel{\text{Def}}{=} \{ 0^i1^j | i,j \geq 1
\wedge \text{ggT} (i,j)=1 \}$ ist nicht regulär.

\emph{Beweis:} Angenommen, $L$ sei regulär. Dann gibt es nach dem
Pumping-Lemma ein $n \in \mathbb{N}$, so daß für $w \in L$ mit $|w|
\geq n$ gilt: $w=xyz, 0 < |y| < n, xy^iz \in L~\forall~i \geq 0$. Sei
$w = 0^n1^{n'}$ mit $n'$ ist die kleinste Primzahl größer als $n$.
Dann ist ggT$(n,n') = 1 \Rightarrow w \in L$. Es ist $|w| \geq n$,
also gibt es die Zerlegung $w = xyz$.

Angenommen, $y$ enthalte Nullen und Einsen. Dies würde einen
Widerspruch beim Pumpen ergeben, da das resultierende Wort nicht mehr
in $L$ wäre. $y$ enthält also entweder nur Nullen oder nur Einsen.

o.B.d.A. enthalte $y$ nur Nullen. Dann ist $w=xyz_1z_2$ mit $z_1 \in
\{0\}^*, z_2 \in \{1\}^*$. $|xyz_1| = n$ und $z_2 = n' \Rightarrow n =
|y|+|xz_1| = s+r$ mit $0<s<n,r>0$. $n'$ ist eine Primzahl $\Rightarrow
\text{ggT}(s,n')=1$. Nach Folgerung aus dem gegebenen Satz gibt es
$u,v \in \mathbb{Z}$ mit $n < 0, r > 0$ und $us + vn' = 1$.

$u < 0 \Rightarrow u = -|n|$.
\begin{eqnarray*}
  us + rn' = 1 &\Leftrightarrow& urs + vrn' = r \\
  &\Leftrightarrow& -|n|rs + vrn' = r \\
  &\Leftrightarrow& r|n|s + r = vrn'
\end{eqnarray*}
mit $r,|n|, s, v > 0$.

Nach dem Pumping-Lemma gilt $xy^{r|u|}z \in L$,
d.h.~ggT$(|xy^{r|u|}z_1|, |z_1|) = 1$. Aber: $|xy^{r|u|}z_1| =
|y|r|u|+|xz_1| = sr|u|+r$ und ggT$(|xy^{r|u|}z_1|,|z_2|) =
\text{ggT}(sr|u|+r, n') = \text{ggT}(vrn', n') = n' > 1~~\blitz$

\section*{Aufgabe 22}
\textbf{a)} $G = (V,\Sigma, P, S)$ mit $V = \{S\}$, $\Sigma=\{
\text{op}, (, ), \cdot, + \}$,\\ $P = \{ S \rightarrow \text{op}, S
\rightarrow S+S, S \rightarrow S \cdot S, S \rightarrow (S) \}$

\textbf{b)} \emph{Behauptung:} $L(G) = L$.

\emph{Beweis:} Sei $w \in \Sigma^*$. Zu zeigen: $S
\stackrel{*}{\Rightarrow} w \Leftrightarrow w$ ist ein korrekt
geformter arithmetischer Ausdruck~$(*)$

Beweis durch Induktion nach $|w|$:

Verankerung: $|w| = 1$. "`$\Rightarrow$"': $S
\stackrel{*}{\Rightarrow} w$ mit $|w|=1 \Rightarrow w= \text{op}
\Rightarrow w$ ist ein korrekt geformter Ausdruck.$~~\checkmark$

"`$\Leftarrow$"': $w = op$ ist der einzige korrekt geformte Ausdruck
mit der Länge 1.$~~\checkmark$

$|w| = n+1$: $(*)$ gilt für $|w'| \leq n$.

"`$\Rightarrow$"': $S \stackrel{*}{\Rightarrow}w, |w| > 1 \Rightarrow
w \neq \text{op}$, also gibt es 3 Fälle:
\begin{enumerate}
\item $S \rightarrow S+S \stackrel{*}{\Rightarrow} w_1 + w_2 = w$ mit
  $S \stackrel{*}{\Rightarrow} w_1, S \stackrel{*}{\Rightarrow} w_2$
\item $S \rightarrow S\cdot S \stackrel{*}{\Rightarrow} w_1 \cdot w_1
  = w$
\item $S \rightarrow (S) \stackrel{*}{\Rightarrow} (w_1) = w$
\end{enumerate}
In jedem Fall ist $|w_1| \leq n, |w_2| \leq n$, damit sind $w_1$ und
$w_2$ nach Induktionsvorraussetzung korrekt geformt und damit auch
$w_1 + w_2, w_1 \cdot w_2, (w_1)~~\checkmark$

"`$\Leftarrow$"': $w$ ist ein korrekt geformter Ausdruck der Länge
$n+1$. Damit enthält $w$ nicht nur op, sondern mindestens ein
$+,\cdot$ oder Klammern.

\vspace{1ex}\hspace*{0.4em}
\begin{math}
\left.
  \begin{array}{ll}
    1. & w = w_1 + w_2\\[1ex]
    2. & w = w_1 \cdot w_2\\[1ex]
    3. & w = (w_1)\\[1ex]
  \end{array}
\right\} w_1 \text{ und } w_2 \text{ sind korrekt geformte Ausdrücke }
\leq n
\end{math}

Nach Induktionsvorraussetzung gilt: $S \stackrel{*}{\Rightarrow} w_1,
S \stackrel{*}{\Rightarrow} w_2$. Damit gilt
\begin{enumerate}
\item $S \rightarrow S + S \stackrel{*}{\Rightarrow} w_1 + S
  \stackrel{*}{\Rightarrow} w_1 + w_2 = w$
\item $S \rightarrow S \cdot S \stackrel{*}{\Rightarrow} w_1 \cdot S
  \stackrel{*}{\Rightarrow} w_1 \cdot w_2 = w$
\item $S \rightarrow (S) \stackrel{*}{\Rightarrow} (w_1) = w$
\end{enumerate}
Es gilt also immer: $S \stackrel{*}{\Rightarrow} w$ mit $|w| =
n+1~~\Box$

\section*{Aufgabe 23}
Die Grammatik $G = ( \{ S,A,B,C,D,E \}, \{a,b\}, P,S )$ mit
\[ P \stackrel{\text{Def}}{=} \left\{
\begin{array}{ll}
  S \rightarrow AE | BE | C & A \rightarrow aAa|B \\
  B \rightarrow bB | bb     & C \rightarrow aCaa|D\\
  D \rightarrow baD|abD|aa  & E \rightarrow EE|\varepsilon
\end{array}
\right\}\] ist in eine reduzierte kontextfreie Grammatik zu überführen.

Nach Satz S.~53 im Skript ist eine kontextfreie Grammatik reduziert,
wenn
\begin{enumerate}
\item $\forall~ A \in \{ V-\Sigma \}: (A \rightarrow \varepsilon)
  \notin P$
\item $S \rightarrow \varepsilon \Leftrightarrow \varepsilon \in L$
\item $S$ erscheint auf \emph{keiner} rechten Seite.
\end{enumerate}
\textbf{1. Schritt:} Anwendung Algorithmus S.~53

$V_1 =\{ E \}\hspace{1cm}V_2 = \{ E \} \cup \{ E \} \Rightarrow V_n =
\{ E \}$

$P_1 = P \cup \{ S \rightarrow A, S \rightarrow B, E \rightarrow E\\
P_2 = P_1 \setminus \{ E \rightarrow E \}\\
P' = P_2 \cup \{ S' \rightarrow S \}$

Man erhält $G' = ( \{ S, S', A, B, C, D, E \}, \{a, b\}, P', S')$
\[ P' = \left\{
  \begin{array}{ll}
    S \rightarrow AE | BE | C | A | B & A \rightarrow aAa|B \\
    B \rightarrow bB | bb             & C \rightarrow aaCaa|D \\
    D \rightarrow baD|abD|aa          & E \rightarrow EE|E\\
    S' \rightarrow S
  \end{array}
\right\}
\]
$G'$ erfüllt die gewünschten Eigenschaften.

\textbf{2. Schritt:} Anwendung Algorithmus S.~59; Beseitigung
zyklischer Produktionen

$V_{S'}^{(1)} = \{ S \} \\
V_{S'}^{(2)} = \{ S \} \cup \{ A,B,C \} = \{ S,A,B,C \} \\
V_{S'}^{(3)} = \{ S,A,B,C \} \cup \{ A,B,C,D \} = \{S,A,B,C,D\}\\
V_{S'}^{(4)} = \{ S,A,B,C,D \} \cup \{ A,B,C,D \} = \{S,A,B,C,D \} =
V_{S'}^{(N)}\\[3ex]
V_S^{(1)} = \{ A,B,C \}\\
V_S^{(2)} = \{ A,B,C,D \}\\
V_S^{(3)} = \{ A,B,C,D \} = V_S^{(N)}\\[3ex]
V_A^{(1)} = \{ B \}\\
V_A^{(2)} = \{ B \} = V_A^{(N)}\\[3ex]
V_B^{(1)} = \emptyset = V_B^{(N)}\\[3ex]
V_C^{(1)} = \{ D \}\\
V_C^{(2)} = \{ D \} = V_C^{(N)}\\[3ex]
V_D^{(1)} = \emptyset = V_D{(N)}\\[3ex]
V_E^{(1)} = \{ E \}\\
V_E^{(2)} = \{ E \} = V_E^{(N)}
$

$G'' = ( \{S', S, A, B, C, D, E \}, \{ a,b \}, P'', S' )$

$P'' = ( P' \setminus \{ S \rightarrow A|B|C, A \rightarrow B, C
\rightarrow D, E \rightarrow E, S' \rightarrow S \})\\
\cup \{ S' \rightarrow AE|BE|aAa|bB|bb|aCaa|baD|abD|aa,\\
\hspace*{7mm}S \rightarrow aAa|bB|bb|aCaa|baD|abD|aa,\\
\hspace*{6.5mm}A \rightarrow bB, C \rightarrow baD|abD|aa, E
\rightarrow EE \}$

Nach Skript S.~56 erhalten wir:
\[ P'' = \left\{
  \begin{array}{l}
    S' \rightarrow AE|BE|aAa|bB|bb|aCaa|baD|abD|aa \\
    S \rightarrow AE|BE|aAa|bB|bb|aCaa|baD|abD|aa \\
    A \rightarrow aAa|bB|bb\\
    B \rightarrow bB|bb\\
    C \rightarrow baD|abD|aCaa|aa\\
    D \rightarrow baD|abD|aa\\
    E \rightarrow EE
  \end{array}
\right\}
\]

\textbf{Schritt 3:} Skript S.~55; Beseitigen überflüssiger Symbole

\Ovalbox{1}

$V_1 = \{ S',S,A,B,C,D \}\\
V_2 = \{ S', S,A,B,C,D \} = V_N\\
\overline{G} = ( \overline{V}, \{a,b\}, \overline{P}, S')\\
\overline{V} = \{ S',S,A,B,C,D \} \cup \{a,b\}\\
\overline{P} = P'' \cap (\overline{V} \times \overline{V}^*)\\[3ex]
\leadsto \overline{P} = P'' \setminus \{ S' \rightarrow AE|BE, S
\rightarrow AE|BE, E \rightarrow EE\}$

\Ovalbox{2}

$H_0 = \{ S' \}\\
H_1 = \{ S' \} \cup \{ A,B,C,D \} = \{ S',A,B,C,D \}\\
H_2 = \{ S',A,B,C,D \} = H_N\\
G''' = (V''',\{a,b\}, P''', S') \text{ mit}\\
V''' = \{S',A,B,C,D\} \cup \{a,b'\}, P''' = \overline{P} \cap (V'''
\times (V''')^*)\\[3ex]
\leadsto P''' = \left\{
\begin{array}{l}
  S' \rightarrow aAa|bB|bb|aCaa|baD|abD|aa\\
  A \rightarrow aAa|bB|bb\\
  B \rightarrow bB|bb\\
  C \rightarrow aCaa|baD|abD|aa\\
  D \rightarrow baD|abD|aa
\end{array}
\right\}$

\section*{zu Aufgabe 21}
In der Aufgabenstellung war folgender Satz gegeben:
\[ \text{Zu } i,j \in \mathbb{Z} \text{ existieren } 
u,v \in \mathbb{Z} \text{ mit } ui+vj = 1\]
Daraus läßt sich folgende Folgerung ableiten:
\[ \text{Zu } i,j \in \mathbb{N}~(i,j \geq 1) \text{ mit ggT}(i,j)=1
\text{ gibt es }u,v \in \mathbb{Z} \text{ mit } uv+vj=1 \text{ und }
u<0, v>0 \]
\textbf{Beweis:} Nach dem Satz existieren $u,v \in \mathbb{Z}$ mit
$ui+vj = 1$. Da $i > 0, j > 0$ ist $u \leq 0$ und $v \geq 0$ oder $u
\geq 0$ und $v \leq 0$. Für den ersten Fall ist die Folgerung bereits
bewiesen.

Sei also $u \geq v$ und $r \leq 0$, dann gilt 
\begin{eqnarray*}
  ui+vj = 1 &\Leftrightarrow& ui-uij+uij+vj = 1\\
  &\Leftrightarrow& i(u-uj)+j(v+ui) = 1 \text{ mit } (u-uj) =: u' \leq
  0 \text{ und }(v+ui) =: v' \geq 0
\end{eqnarray*}
Also ist $u'i+v'j = 1~~\Box$

Es soll gelten $u < 0, v > 0$ bzw.~$u' < 0, v' > 0$.
\begin{eqnarray*}
  &&u = 0 \Rightarrow vj=1 \Rightarrow j=1~~\blitz\\
  &&v = 0 \Rightarrow ui=1 \Rightarrow i=1~~\blitz\\
  &&u' = 0 \Rightarrow n-nj = 0 \Rightarrow j=1~~\blitz\\
  &&v' = 0 \Rightarrow v' = -ui \Rightarrow -v+vj=1 \Rightarrow
  v(j-1)=1 \Rightarrow j = \frac{1}{r}+1 \Rightarrow i=0, \text{ da }
  r < 0~~\blitz
\end{eqnarray*}
\end{document}
