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

\begin{document}

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

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

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

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

\section*{Aufgabe 27}

Gesucht ist ein PDA, der $L_k = \{ a^nb_i^n | n \in \mathbb{N} , 1
\leq i \leq k \}$. Sei der PDA 
\[ M = ( \{ q_0, q_1, \dots, q_k, \overline{q}
\}, \{ a, b_1, \dots, b_k \}, \{ Z, Z_0 \}, \delta, q_0, Z_0, \{
\overline{q} \})\]
mit $\delta$:

\begin{math}
\left.
  \begin{array}{l}
    \delta(q_0,a,Z_0) := (q_0, ZZ_0) \\
    \delta(q_0,a,Z) := (q_0, ZZ)
  \end{array}
\right\} \text{ Schreibe für jedes }a\text{ ein }Z\text{ auf den
  Keller.}
\\[2ex]
\left.
  \begin{array}{c}
    \delta(q_0,b_1,Z) := (q_1, \varepsilon) \\
    \delta(q_0,b_2,Z) := (q_2, \varepsilon) \\
    \vdots \\
    \delta(q_0,b_k,Z) := (q_k, \varepsilon) \\
  \end{array}
\right\}\parbox{12cm}{Gehe abhängig vom zuerst konsumierten $b_i$ in
  den Zustand $q_i$ und entferne ein $Z$ vom Keller.}
\\[2ex]
\left.
  \begin{array}{c}
    \delta(q_1,b_1,Z) := (q_1, \varepsilon) \\
    \delta(q_2,b_2,Z) := (q_2, \varepsilon) \\
    \vdots \\
    \delta(q_k,b_k,Z) := (q_k, \varepsilon) \\
  \end{array}
\right\}\parbox{12cm}{Konsumiere $n-1$ $b_i$ im jeweiligen Zustand
  $q_i$ und entferne jeweils ein $Z$ vom Keller. Ist man in $q_i$
  gelandet, kann man diesen nicht mehr verlassen.}
\\[2ex]
\left.
  \begin{array}{c}
    \delta(q_1,\varepsilon,Z_0) := (\overline{q}, \varepsilon) \\
    \vdots \\
    \delta(q_k,\varepsilon,Z_0) := (\overline{q}, \varepsilon) \\    
  \end{array}
\right\}\parbox{12cm}{Gehe nach Konsumation von $a^nb_i^n$ in den
  akzeptierenden Zustand über.}
\end{math}

$M$ ist deterministisch, denn es gilt:
\begin{enumerate}
\item $\forall~q \in \{ q_0,a_1,\dots,q_n,\overline{q} \},~\forall~ a
  \in \Sigma \cup \{\epsilon\},~\forall~ A \in \{ Z,Z_0 \}$ gilt:
  $|\delta(q,a,A)| \leq 1$
\item $\delta(q,\varepsilon,A) \neq \emptyset \Rightarrow
  \delta(q,a,A) = \emptyset$
\end{enumerate}

\section*{Aufgabe 28}

Die Grammatik $G = (\{ A,S \}, \{a,b\}, P,S), P= \{ S \rightarrow
AA|a, A \rightarrow SS|b \}$ soll in Greibach-Normal-Form umgewandelt
werden.

\ovalbox{1} Umwandlung in Chomsky-Normalform durch Einführen eines
neuen Startsymbols $S'$. Wir erhalten $G' = (\{A,S,S'\}, \{a,b\}, P',
S')$ mit $P' = \{ S' \rightarrow AA|a, S \rightarrow AA|a, A
\rightarrow SS|b \}$.

\ovalbox{2} Umwandlung der Chomsky-Normalform in Greibach-Normal-Form.
Umbenennen der Nichtterminale $S' := A_1, S := A_2, A := A_3 \leadsto
P' = \{ A_1 \rightarrow A_3A_3|a, A_2 \rightarrow A_3A_3|a, A_3
\rightarrow A_2A_2|b \}$

\emph{1. Schritt:} Es gilt bereits $A_i \rightarrow A_j\gamma, j > i$
für $i=1,2$. Ersetze $A_3 \rightarrow A_2A_2$ durch\linebreak $A_3
\rightarrow A_3A_3A_2|aA_2 \leadsto P' = \{ A_1 \rightarrow A_3A_3|a,
A_2 \rightarrow A_3A_3|a, A_3 \rightarrow A_3A_3A_2|aA_2|b \}$.
Ersetze $A_3 \rightarrow A_3A_3A_2$ durch $A_3 \rightarrow aA_2B_3$
und füge $B_3 \rightarrow A_3A_2|A_3A_2B_3$ ein:
\[ P' = \{ A_1 \rightarrow A_3A_3|a, A_2 \rightarrow A_3A_3|a, A_3
\rightarrow aA_2B_3|bB_3|aA_2|b, B_3 \rightarrow A_3A_2|A_3A_2B_3 \}
\]

\emph{2. Schritt:} Ersetze $A_2 \rightarrow A_3A_3$ durch $A_2
\rightarrow aA_2B_3A_3|bB_3A_3|aA_2A_3|bA_3$ und ersetze\linebreak
$A_1 \rightarrow A_3A_3$ durch $A_1 \rightarrow
aA_2B_3A_3|bB_3A_3|aA_2A_3|bA_3$

\emph{3. Schritt:} Ersetze $B_3 \rightarrow A_3A_2$ durch $B_3
\rightarrow aA_2B_3A_2|bB_3A_2|aA_2A_2|bA_2$ und ersetze\linebreak
$B_3 \rightarrow A_3A_2B_3$ durch $B_3 \rightarrow
aA_2B_3A_2B_3|bB_3A_2B_3|aA_2A_2B_3|bA_2B_3$

Wir erhalten also unter Rückumbenennung $\overline{G} =
(\{S',S,A,B_3\}, \{a,b\}, \overline{P}, S')$ mit
\begin{eqnarray*}
  \overline{P} &= \{& S' \rightarrow aSB_3A|bB_3A|aSA|bA|a,\\
  && S \rightarrow aSB_§A|bB_3A|aSA|bA|a,\\
  && A \rightarrow aSB_3|bB_3|aS|b,\\
  && B_3 \rightarrow aSB_3S|bB_3S|aSS|bS|aSB_3SB_3|bB_3SB_3|aSSB_3|bSB_3 ~~ \}
\end{eqnarray*}

\section*{Aufgabe 29}

\textbf{a)} $L_1 := \{ a^{n^2} | n \in \mathbb{N} \}$ ist nicht
kontextfrei.

\emph{Beweis:} Angenommen, $L_1$ wäre kontextfrei. Dann existiert nach
dem Pumping-Lemma für kontextfreie Sprachen eine Konstante $k \in
\mathbb{N}$, so daß für $a^{k^2} \in L_1$ eine Zerlegung $uvwxy$
existiert mit $|vx| > 1, |vwx| \leq k$, und $uv^iwx^iy \in L_1$ für
alle $i \geq 0$. Insbesondere gilt $uv^2wx^2y \in L_1$,
d.h.~$|uv^2wx^2y|$ ist eine Quadratzahl, aber \[ k^2 < k^2 + |vx| =
|uv^2wx^2y| = k^2 + |vx| \leq k^2 < k^2 + 2k + 1 = (k+1)^2, \] also
ist $|uv^2wx^2y|$ keine Quadratzahl $~\blitz$

\textbf{b)} $L_2 := \{ a^{n_1}ba^{n_2}ca^{m_1}ba^{m_2} | n_1 + n_2 =
m_1 + m_2 \wedge n_1 \neq m_1 \}$ ist keine kontextfreie Sprache.

\emph{Beweis:} Angenommen, $L_2$ wäre kontextfrei. Sei $k$ die
Konstante des Pumping-Lemmas. Betrachte $z = a^{k!+k}ba^kca^kba^{k!+k}
\in L_2$. Dann existiert eine Zerlegung $z = uvwxy, |vx| \geq 1, |vwx|
\leq k$ und $uv^iwx^iy \in L_2$ für alle $i \geq 0$.
\begin{enumerate}
\item $v$ und $x$ enthalten kein $b$ und kein $c$, sonst entsteht ein
  Widerspruch beim Pumpen.
\item $v$ ist links von $c$ und $x$ ist rechts von $c$ positioniert,
  sonst Widerspruch durch Verletzen der Bedingung $n_1 + n_2 = m_1 +
  m_2$
\item Also ist $vwx$ ein Teil von $a^kca^k$ mit $c$ Teil von $w$.
\item $|v| = |x| \geq 1$, sonst Verletzung der Bedingung $n_1 + n_2 =
  m_1 + m_2$. Es gilt: \[ uv^iwx^iy =
  a^{k!+k}ba^{k-|v|}(a^{|v|})^ic(a^{|v|})^ia^{k-|v|}ba^{k!+k} \in
  L_2~\forall~i \]
  Setze: $i = \frac{k!}{|v|}+1$. Dann ist
  \begin{eqnarray*}
    uv^ix^iy &=& a^{k!+k}ba^{k-|v|}(a^{|v|})^{\frac{k!}{|v|}+1}c(a^{|v|})^{\frac{k!}{|v|}+1}a^{k-|v|}ba^{k!+k}\\
    &=& a^{k!+k}ba^{k-|v|}a^{k!+|v|}ca^{k!+|v|}a^{k-|v|}ba^{k!+k}\\
    &=& a^{k!+k}ba^{k-|v|}a^{k!+|v|}ca^{k!+|v|}a^{k-|v|}ba^{k!+k}\\
    &=& a^{k!rk}ba^{k-|v|}a^{k!r|v|}ca^{k!r|v|}a^{k!|v|}ba^{k!+k}\\
    &=& a^{k!rk}ba^{k!+k}ca^{k!+k}ba^{k!+k} \in L_2~~\blitz
  \end{eqnarray*}
\end{enumerate}

\textbf{c)} Die Sprache $L_3 := \{ wcx | w,x \in \{a,b\}^* \wedge w
\neq x \wedge |w| = |x| \}$ ist nicht kontextfrei.

\emph{Beweis:} Angenommen, $L_3$ wäre kontextfrei. Dann ist auch $L_3'
:= L_3 \cap \{ a^nba^mca^rba^s | n,m,r,s \geq 0 \}$ kontextfrei, da
kontextfreie Sprachen abgeschlossen sind im Schnitt mit regulären
Mengen. Aber
\begin{eqnarray*}
  L_3' &=& \{ a^{n_1}ba^{n_2}ca^{m_1}ba^{m_2}|n_1 + n_2 =
  m_1 + m_2 \wedge (n_1 \neq m_1 \vee n_2 \neq m_2)\}\\
  &=& \{ a^{n_1}ba^{n_2}ca^{m_1}ba^{m_2}|n_1 + n_2 = m_1 + m_2 \wedge
  n_1 \neq m_1 \}\\
  &=& L_2,
\end{eqnarray*}
denn $n_2 \neq m_2 \Rightarrow n_1 \neq m_1$: Angenommen, $n_1 = m_1
\Rightarrow n_2 \neq m_2 \Leftrightarrow n_1+n_2 \neq n_1 + m_2
\Leftrightarrow n_1 + n_2 \neq m_1 + m_2~~\blitz$.

Also wäre $L_2$ kontextfrei $\Rightarrow~\blitz$ zu b)

\section*{Aufgabe 30}
Die Sprache $FH(L) := \{x | \exists y \in \Sigma^*: (|x| = |y| \wedge
xy \in L) \}$ ist nicht kontextfrei.

\emph{Beweis:} Angenommen, die Behauptung sei wahr. Betrachte die
Sprache $L = \{ a^nb^nc^m\#d^{3m}\# | n,\linebreak m \in \mathbb{N}
\}$. $L$ ist kontextfrei.

Nach Annahme ist $FH(L)$ kontextfrei. Aber dann ist
\begin{eqnarray*}
  && FH(L) \cap \{ a^nb^mc^r\# | n,m,r \geq 0 \} \\
  &=& \{ a^nb^nc^m\#|n,m \geq 0 \wedge (2n+m) = 3m \}\\
  &=& \{ a^nb^nc^m\#|n,m \geq 0 \wedge (n-m) = 0 \}\\
  &=& \{ a^nb^nc^n\# | n \geq 0 \}
\end{eqnarray*}
kontextfrei.

Betrachte Homomorphismus $h$ mit $h(a) = a, h(b) = b, h(\#) =
\varepsilon$. Dann ist $h(\{a^nb^nc^n\# | n \geq 0 \}) = \{ a^nb^nc^n
| n \geq 0 \}$ kontextfrei$~~\blitz$

Also sind die kontextfreien Sprachen nicht unter $FH$ abgeschlossen.

\section*{Anmerkung}

Die kontextfreien Sprachen sind abgeschlossen unter
\emph{Vereinigung}, \emph{Konkatenation}, \emph{Kleenescher
  Hüllenbildung}, \emph{Schnitt} mit \textbf{regulären} Mengen,
\emph{Homomorphismen} und \emph{inversen Homomorphismen}. Sie sind
\textbf{nicht} abgeschlossen unter \emph{Schnitt} und
\emph{Komplementbildung}.
\end{document}