% 9. Uebungsblatt GTI SS 2001
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=16cm
\textheight=24cm
\hoffset = -19mm
\voffset = -25mm

\setcounter{page}{9}
\let\eps=\varepsilon
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2001 ---
 9.~\"Ubungsblatt\par
}
\medskip
Abgabe bis Montag, 2. Juli 2001
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{51}


\item
\begin{enumerate}
\item (0 Punkte)
Geben Sie eine kontextfreie Grammatik für arithmetische
Ausdrücke über dem Alphabet $\{+,*,(,),Z\}$
an. Dabei sollen nur Ausdrücke \emph{ohne überflüssige Klammern}
erzeugt werden, d.~h., solche Audrücke, die 
nach den üblichen mathematischen Vorrangregeln einen anderen Wert
bekommen,
wenn man Klammern weglässt.
Zum Beispiel sind die Klammern in $Z*( Z+ Z)$ notwendig,
weil man den Ausdruck ohne Klammern $Z*Z+Z$ als $(Z*Z)+Z$ lesen
würden. Aus diesem Grund sind auch die Klammern im Ausdruck
$(Z*Z)+Z$  überflüssig (redundant).
\item  (0 Punkte)
Lösen Sie die Aufgabe mit dem erweiterten Alphabet $\{+,-,*,\div,(,),Z\}$.
\end{enumerate}

\item (0 Punkte)
Beweisen Sie, dass man zu jeder kontextsensitiven Grammatik eine
äquivalente Grammatik finden kann, deren Regeln von der
Gestalt $S\to \eps$ oder von folgender Gestalt sind.
$$ \alpha_1A\alpha_2 \to \alpha_1\beta\alpha_2,
\hbox{ mit $A\in V$, $\alpha_1,\alpha_2,\beta\in (T\cup V-\{S\})^*$,
$\beta\ne\eps$}$$


\item (6 Punkte)
Welche der folgenden Sprachen sind kontextfrei?
  \begin{enumerate}
  \item (4 Punkte) $L_1 = \{\,0^i1^{i^2} \mid i\ge 1\,\}$
  \item (2 Punkte) $L_2 = \{\,0^i1^j \mid i\ge j\,\}$
  \item Die Sprache der Doppelwörter
    $L_3 = \{\,ww \mid w\in \{0,1\}^* \,\}$
  \item $L_4 = \{\,0^i1^j0^k1^l \mid i+j=k+l \,\}$,
%%  \item $L_5 = \{\,0^i1^j0^k1^l \mid i+l=j+k \,\}$
\qquad  %\item
 $L_5 = \{\,0^i1^j0^k1^l \mid i+k=j+l \,\}$
  \item 
    $L_6 = \{\, w\in \{0,1\}^* \mid w$ enthält doppelt so
    viele Nullen wie Einsen$\,\}$
  \end{enumerate}

\item (5 Punkte)
 Beweisen Sie, dass die Grammatik mit den Regeln
\ $S \to aS \ \bigm| \ aSbS \ \bigm|\ \eps$\quad
genau die Wörter über $\{a,b\}$ erzeugt, in denen jeder Präfix
mindestens so viele $a$'s wie $b$'s enthält.

\item (0 Punkte)
Die Grammatik
$$
\begin{array}{l}
S\to \textbf{if } (B)\ S \ \bigm|\ \textbf{if } (B)\ S \textbf{ else } S
\ \bigm| \  \textrm{print}(0); 
\ \bigm| \  \textrm{print}(1);
\ \bigm| \  \textrm{print}(2); \\
B \to \textrm{true}\ \bigm| \  \textrm{false}
\end{array}
$$
ist mehrdeutig, wie das Beispiel
$$\textrm{\textbf{if} (true) \textbf{if} (false) \textbf{if} (false) print(0); \textbf{else}
\textbf{if} (true) print(0); \textbf{else} print(1); \textbf{else}
  print(2);}$$
zeigt.
Die Mehrdeutigkeit kann durch die gängige Regel aufgelöst werden, dass eine
\textbf{else}-Klausel immer dem \emph{letzten} \textbf{if} zugeordnet wird, dem
noch keine \textbf{else}-Klausel zugeordnet wurde.
Nach dieser Regel würde der obige Ausdruck 2 drucken,
wenn man ihn als Programm auf"|fasst. (Welche Werte könnte das
Programm sonst noch
drucken, wenn man alle Mehrdeutigkeiten berücksichtigt?)
Geben Sie eine eindeutige Grammatik an, die dieser Regel entspricht.

\item (5 Punkte)
Bleibt eine eindeutige Grammatik bei der
Transformation in Chomsky-Normal\-form eindeutig?
Beweisen Sie Ihre Antwort.

\item (0 Punkte)
$G$ sei eine
Grammatik
in Chomsky-Normalform, die eine endliche Sprache erzeugt.
Finden Sie eine Schranke für das längste Wort in $L(G)$.

\item (0 Punkte)
Wie lang kann die Ableitung eines Wortes $w$ bei einer
Grammatik in Chomsky-Normalform höchstens sein?


\end{enumerate}
\end{document}