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

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

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

\section*{Aufgabe 24}
Es soll eine kontextfreie Grammatik konstruiert werden, die die Sprache
\[ L \stackrel{\rm def}{=} \{ wcx \in \{ a,b,c \}^* | w,x \in \{ a,b
\} \wedge w \neq x \} \] akzeptiert.

Für das Wort $v = w_1w_2 \dots w_n c x_1 x_2 \dots x_m \in L$ gilt:
\begin{enumerate}
\item $w$ und $x$ haben unterschiedliche Länge, also $|w| \neq |x|, n
  \neq m$ oder
\item $|w| = |x|$ und es existiert mindestens ein $i: 1 \leq i \leq n$
  und $x_i \neq w_i$
\end{enumerate}

Wir konstruieren eine Grammatik $G$, so daß für $v \in \{a,b,c\}^*$
mit $S~$\unitlength1mm
\begin{picture}(3,3)(0,0)
  \put(0,0.5){$\Rightarrow$}
  \put(0.5,1.5){*}
  \put(0,-2.2){\scriptsize $G$}
\end{picture}
$~v$ entweder (1) oder (2) gilt.

Zu (1): Sei zunächst $|w| > |x|$.

$S \rightarrow TS_L\\
S_L \rightarrow TS_LT|TS_L|c\\
T \rightarrow a|b$

Dann gilt: $S \Rightarrow TS_L \stackrel{*}{\Rightarrow} Tw'cx
\Rightarrow wcx$ mit $|w| > |x|$.

Analog: $|w| < |x|$.

$S \rightarrow S_RT\\
S_R \rightarrow TS_RT|S_RT|c\\
T \rightarrow a|b$

Dann gilt: $S \Rightarrow S_RT \stackrel{*}{\Rightarrow} wcx'T
\Rightarrow wcx$ mit $|w| < |x|$.

Zu (2): $w_i = a$, $x_i = b$

$S \rightarrow S_abT'\\
S_a \rightarrow TS_aT|aT'c\\
T' \rightarrow T'T'|T|\varepsilon\\
T \rightarrow a|b$

Dann gilt: $S_a \stackrel{*}{\Rightarrow} T^nS_aT^n \Rightarrow
T^naT'cT^n$, d.h.~vor einem $a$ stehen genauso viele Terminalsymbole
wie nach einem $c$.

Also:
\begin{eqnarray*}
  S &\Rightarrow& S_abT'\\
  &\stackrel{i-1}{\Rightarrow}& T^{i-1}S_aT^{i-1}bT'\\
  &\Rightarrow& T^{i-1}aT'cT^{i-1}bT'\\
  &\stackrel{*}{\Rightarrow}& w_1w_2 \dots w_{i-1} a w_{i+1} \dots w_ncx_1x_2
  \dots x_{i-1}bx_{i+1} \dots x_m \\
  &\leadsto& w_i = a, x_i = b
\end{eqnarray*}

Analog: $w_i = b, x_i = a$

$S \rightarrow S_b|aT'\\
S_b \rightarrow TS_bT|bT'c\\
T' \rightarrow T'T'|T|\varepsilon\\
T \rightarrow a|b$

Damit:
\begin{eqnarray*}
  S &\Rightarrow& S_baT'\\
  &\stackrel{i-1}{\Rightarrow}& T^{i-1}S_bT^{i-1}aT'\\
  &\Rightarrow& T^{i-1}bT'cT^{i-1}aT'\\
  &\stackrel{*}{\Rightarrow}& w_1w_2 \dots w_{i-1} b w_{i+1} \dots w_ncx_1x_2
  \dots x_{i-1}ax_{i+1} \dots x_m \\
  &\leadsto& w_i = b, x_i = a
\end{eqnarray*}

Zusammenfassung:

$G = (\{ S,S_L,S_R, S_a, S_b, T',T,a,b,c \}, \{ a,b,c\}, P,S)$

\(
P = \left\{
\begin{array}{l}
  S \rightarrow TS_L|S_RT|S_abT'|S_baT' \\
  S_L \rightarrow TS_LT|TS_L|c \\
  S_R \rightarrow TS_RT|S_RT|c \\
  S_a \rightarrow TS_aT|aT'c \\
  S_b \rightarrow TS_bT|bT'c \\
  T' \rightarrow T'T'|T|\varepsilon \\
  T \rightarrow a|b
\end{array}
\right\}
\)

\section*{Aufgabe 25}
Es soll ein PDA konstruiert werden, der $L_n \stackrel{\rm def}{=} \{
wcx \in \{a,b,c\}^* | w,x \in \{a,b\}^n \wedge w \neq x \}$ akzeptiert.

Jedes Wort besteht aus zwei gleich langen Teilen $w$ und $x$, die
durch ein $c$ getrennt sind. $w$ und $x$ unterscheiden sich an
mindestens einer Stelle.

\emph{Idee:}
\begin{itemize}
\item Zähle die Länge $|w|=|x|=n$ über die Zustände
\item Merke mit Hilfe des Kellers, wo sich $w$ und $x$ unterscheiden.
  \begin{itemize}
  \item Stack aufbauen
  \item "`Entscheidung"': $i$-te Stelle $w_i = a$ und $x_i = b$ oder
    $w_i = b$ und $x_i = a$
  \item Stack unberührt lassen bis $c$ kommt
  \item Stack abbauen bis zum Startsymbol
  \item Eingabesymbol $x_i = b$ (bzw $a$): Rest abzählen und
    Startsymbol beseitigen
  \item $X_i = a$ (bzw $b$): nicht akzeptieren
  \end{itemize}
\end{itemize}
\begin{center}
  \includegraphics{Blatt07-PDA-Aufg25.eps}
\end{center}
\emph{Definition:} $M = (Q, \{a,b,c\}, \{z, Z_0\}, \delta, q_0, Z_0,
\emptyset)$ mit\\
$Q = \{ q_0,q_1, \dots, q_{n-1},q_1^a,q_2^a, \dots, q_n^a, q_1^b,
q_2^b, \dots, q_{n+1}^b, p_0,p_1, \dots, p_n, p_0^a, \dots, p_{n-1}^a,
p_0^b, \dots, p_{n-1}^b \}$.\\
Offenbar: $|Q| = O(n)$.

Übergangsfunktion $\delta$ ist in der Bibliothek erhältlich.

\section*{Aufgabe 26}
\textbf{a)} Um zu zeigen, daß $G$ mehrdeutig ist, zeigen wir:
\texttt{if expr then if expr then stmt else stmt} hat zwei
verschiedene Linksableitungen.

1.
\begin{eqnarray*}
  S &\Rightarrow& {\tt if~expr~then}~S~{\tt else}~S \\
  &\Rightarrow& {\tt if~expr~then~if~expr~then}~S~{\tt else}~S \\
  &\Rightarrow& {\tt if~expr~then~if~expr~then~stmt~else}~S \\
  &\Rightarrow& {\tt if~expr~then~if~expr~then~stmt~else~stmt}
\end{eqnarray*}
2.
\begin{eqnarray*}
  S &\Rightarrow& {\tt if~expr~then}~S \\
  &\Rightarrow& {\tt if~expr~then~if~expr~then}~S~{\tt else}~S \\
  &\Rightarrow& {\tt if~expr~then~if~expr~then~stmt~else}~S \\
  &\Rightarrow& {\tt if~expr~then~if~expr~then~stmt~else~stmt}
\end{eqnarray*}

\textbf{b)} Betrachte Grammatik $G' = ( \{ S',S_M,S_N \}, \{ {\tt
  if,~then,~else,~expr,~stmt}\}, P', S')$ mit

\( P' = \left\{
  \begin{array}{l}
    S' \rightarrow S_N|S_M \\
    S_N \rightarrow {\tt if~exp~then}~S'|{\tt if~exp~then}~S_M~{\tt
      else~}S_N \\
    S_M \rightarrow {\tt if~exp~then~}S_M{\tt ~else~}S_M|{\tt stmt}
  \end{array}
\right \} \)

$G'$ ist eindeutig.

\textbf{c)} $G = (\{E\}, \{ (,),\cdot,+,{\rm op} \}, P, E$ mit $P = \{
E \rightarrow E+E|E \cdot E|(E)|{\rm op} \}$

$G$ ist mehrdeutig, denn ${\rm op} \cdot {\rm op} + {\rm op}$ besitzt
2 Linksableitungen.
\begin{enumerate}
\item $E \Rightarrow E \cdot E \Rightarrow {\rm op} \cdot E
  \Rightarrow {\rm op} \cdot E+E \Rightarrow {\rm op} \cdot {\rm op} +
  E \Rightarrow {\rm op} \cdot {\rm op} + {\rm op}$
\item $E \Rightarrow E + E \Rightarrow E \cdot E + E \Rightarrow {\rm
    op} \cdot E+E \Rightarrow {\rm op} \cdot {\rm op} + E \Rightarrow
  {\rm op} \cdot {\rm op} + {\rm op}$
\end{enumerate}

Betrachte $G' = (\{ E \}, \{ (,),\cdot,+,{\rm op} \}, P', E)$ mit $P'
= \{ E \rightarrow {\rm op}+E|{\rm op}\cdot E|(E)+E|(E)\cdot
E|(E)|{\rm op} \}$.

$G'$ ist eindeutig.
\end{document}