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

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

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


\begin{enumerate}
\setcounter{enumi}{43}

\item (5 Punkte) Beweisen Sie:
  \begin{enumerate}
  \item (0 Punkte)
    Wenn es eine Turingmaschine gibt, die die Wörter einer Sprache
    in beliebiger Reihenfolge, möglicherweise mit Wiederholungen,
    auf ein Ausgabeband schreibt, dann ist diese Sprache rekursiv
    aufzählbar.
  \item (5 Punkte)
    Eine Sprache ist genau dann rekursiv,
    wenn es eine Turingmaschine gibt, die die Wörter der Sprache
    der Länge nach sortiert
    auf ein Ausgabeband schreibt (Wörter gleicher Länge
    können in beliebiger Reihenfolge, möglicherweise mit Wiederholungen,
    ausgegeben werden.)
  \end{enumerate}

\item (0 Punkte)
Zeigen Sie:
\begin{enumerate}
\item
Die rekursiven Sprachen sind unter Differenz
 abgeschlossen.
(Das heißt: Mit $L_1$ und $L_2$ ist auch $L_1-L_2$ immer rekursiv.)
\item Die rekursiv aufzählbaren Sprachen sind unter
Differenz nicht abgeschlossen.
\end{enumerate}

\item (5 Punkte)
Bestimmen Sie die Sprache, die von der Grammatik mit dem Startsymbol
$S$,
dem Terminalalphabet $\{a\}$ und den folgenden Regeln erzeugt wird.
Begründen Sie Ihre Antwort, indem Sie den Ableitungsprozess
in Worten beschreiben.
$$
\begin{array}{ll}
S\to ACaB \qquad & aD\to Da \\
Ca\to aaC & AD\to AC \\
CB\to DB & aE\to Ea \\
CB\to E & AE\to \eps 
\end{array}
$$
\item (0 Punkte)
Bestimmen Sie kontextsensitive Grammatiken für folgende Sprachen.

\begin{minipage}[t]{0,4\hsize}
\begin{enumerate}
\itemsep=0pt
\item[(a)] $L_1 = \{\, ww \mid w \in \{0,1\}^+\,\}$
\item[(b)] $L_2 = \{\, 0^ {i^2} \mid i\ge 1 \,\}$
\end{enumerate}
\end{minipage}
\begin{minipage}[t]{0,5\hsize}
\begin{enumerate}
\itemsep=0pt
\item[(c)] $L_3 = \{\, 0^ {i} \mid i\ge 2 \hbox{, $i$ ist keine Primzahl} \,\}$
\item[(d)]  $L_4 = \{\, 0^ {i}1^i2^i \mid i\ge 1 \,\}$
\end{enumerate}
\end{minipage}
\item (6 Punkte)
Geben Sie eine \emph{eindeutige} kontextfreie Grammatik für arithmetische
Ausdrücke über dem Alphabet $\{+,-,*,\div,\uparrow,(,),Z\}$
an. Die Grammatik soll die Ausdrücke gemäß den üblichen
mathematischen Regeln analysieren, wobei der
Operator $\uparrow$ für die Exponentiation höchste
Priorität hat und rechtsassoziativ ist. Es soll also
zum Beispiel
$Z\uparrow Z\uparrow Z$
wie
$Z\uparrow (Z\uparrow Z)$ interpretiert werden, und
$Z-Z\div Z* Z - Z*Z$ wie
$(Z-((Z\div Z)* Z)) - (Z*Z)$.

\item (0 Punkte)
\xdef\G{\arabic{enumi}}%
Betrachten Sie die kontextfreie Grammatik $G$ mit den Regeln
$$
\begin{array}[t]{ll}
S \to ScS \ |\  A \\
A \to aAb \ |\  \eps
\end{array}
$$
\begin{enumerate}
\item Beschreiben Sie die erzeugte Sprache, und
%\item
 zeigen Sie, dass $G$ mehrdeutig ist.
\item Geben Sie eine eindeutige kontextfreie Grammatik an, die dieselbe Sprache
erzeugt.
\end{enumerate}

\item(0 Punkte)
Zeigen Sie, dass die Grammatiken
\begin{enumerate}
\item $S \to SS \ |\  (S) \ |\  \eps$
\item $S \to (S)S \ |\  \eps$
\end{enumerate}
die gleiche Sprache erzeugen und dass (a) mehrdeutig und (b) eindeutig ist.

\item (0 Punkte)
Bringen Sie die Grammatik aus Aufgabe \G\ und Ihre Antwort aus
Aufgabe \G b in Chomsky-Normalform.

\end{enumerate}
\end{document}






