% 8. Uebungsblatt GTI SS 2005
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=15cm
\textheight=24,5cm
\hoffset = -19mm
\voffset = -25mm
\let\eps=\varepsilon
\selectlanguage{ngerman}

\setcounter{page}{10}
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2005 ---
 8.~\"Ubungsblatt\par
}
\medskip
Abgabe bis Montag, 20. Juni 2005, 10:15 Uhr
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{58}

\item
\begin{enumerate}
\item (10 Punkte)
Geben Sie eine kontextfreie Grammatik für arithmetische
Aus\-drü\-cke über dem Alphabet $\{+,*,(,),Z\}$
an. Dabei sollen nur Ausdrücke \emph{ohne über\-flüs\-sige 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
Die Grammatik
$$
\begin{array}{l}
S\to T \ \bigm|\ T + T\ \bigm|\ T - T \\
T\to F \ \bigm|\ F * F\ \bigm|\ F \div F \\
F\to V \ \bigm|\ (S) \\
V\to Z \ \bigm|\ ZV \\
Z\to 0\ \bigm|\ 1\ \bigm|\ 2\ \bigm|\ 3\ \bigm|\ 4\ \bigm|\ 5\ \bigm|\ 6\ \bigm|\ 7\ \bigm|\ 8\ \bigm|\ 9\
\end{array}
$$
für arithmetische Ausdrücke mit konstanten ganzzahlichen Operanden ist
mehrdeutig, weil zum Beispiel für den Ausdruck
$3-4+5$ aus der Grammatik nicht hervorgeht, ob $4+5$ oder $3-4$ zuerst
berechnet werden soll.
Die Mehrdeutigkeit wird durch die gängige Regel aufgelöst, dass
Operatoren gleicher Stufe von links nach rechts ausgewertet werden.

Schreiben Sie eine äquivalente eindeutige Grammatik, die diese Regel widerspiegelt.

\item Konstruieren Sie eine kontextfreie Grammatik für die
Sprache der Wörter über $\{0,1\}$, die \emph{kein} Palindrom sind:
$$L = \{\,w\mid w\ne w^R\,\}$$

\item
  \begin{enumerate}
  \item 
 Beweisen Sie, dass die Grammatik $G$ mit den Regeln
\ $S \to aS \ \bigm| \ SS \ \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 Schreiben Sie ein entsprechendes Gleichungssystem für die
vom der Grammatik akzeptierte Sprache $L_S$ auf.

\item $L_S = \{a,b\}^*$ ist eine Lösung dieses Gleichungssystems.
Finden Sie eine Lösung, die von $L(G)$ und $\{a,b\}^*$ verschieden ist.

\item Schreiben Sie eine Grammatik ohne $\eps$-Regeln für die Sprache
  $L(G)-\{\eps\}$.

  \end{enumerate}

\item 
Wandeln Sie die folgende Grammatik in Chomsky-Normalform um.
Prüfen Sie dann mit dem CYK-Algorithmus nach, dass das Wort
$a+a*a*a$  von dieser Grammatik
erzeugt wird, und geben Sie einen Syntaxbaum \emph{und} eine
Linksableitung (für die umgewandelte Grammatik) an.
$$
\begin{array}{l}
S\to S*A \ \bigm| \ A-A
\\
A\to A*A \ \bigm|\ a
\end{array}
$$


\end{enumerate}
\end{document}

