% Nachklausur zur 2. Klausur GTI SS 2005
\documentclass [12pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {ngerman}
\usepackage[latin1]{inputenc}
\textwidth=16cm
\textheight=23,5cm
\hoffset = -17mm
\voffset = -20mm

\newif\iferstes
%\erstestrue %% if all pages separately
\let\seite\relax

\def\nam {\vbox to 0cm{\vskip - 1,5cm \hbox to \hsize{
Matrikelnummer:
\vrule height -1,6pt depth 2pt width 2cm
\hfil Vorname: 
\vrule height -1,6pt depth 2pt width 2cm
\hfil FAMILIENNAME: 
\vrule height -1,6pt depth 2pt width 3,2cm
\hskip -1,5cm
}\vss}}

\begin{document}
\setcounter{page}{4}
%\thispagestyle{empty}
%\nam

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2005

%Nachklausur zur 
Nachklausur zur Abschlussklausur
%Montag, 6. Juni 2005

}

\medskip
Abgabe bis Dienstag, 18. Oktober 2005, 19:30 Uhr

\par \smallskip
\end{centering}$$
\begin{tabular}{|l| r r r r   |}
\hline
 
Aufgabe
\vrule height 12pt depth 6pt width 0pt
&\ 1 &\ 2a &\ 2b & 3 \ \\
\hline
Punkte
\vrule height 14pt depth 6pt width 0pt
& 10 & 5 & 5 & 10 \ \\
\hline
Punkte
\vrule height 16pt depth 8pt width 0pt&&&&
\rlap{ \quad gesamt: }\\
\hline
\end{tabular}
$$       
\medskip
\hrule
\medskip

\noindent \emph{Anleitung}:
Bearbeiten Sie {jede} Aufgabe auf einem getrennten \emph{Blatt}.
Verwenden Sie gegebenenfalls Ergänzungsblätter.
Schreiben Sie auf \emph{alle} Blätter Ihren Namen und Ihre
Matrikelnummer. Sie haben 90 Minuten Zeit.

\medskip
\noindent
Sie können alle Aussagen, die in der Vorlesung oder auf den
Übungsblättern vorgekommen sind, verwenden, ohne die Beweise
abzuschreiben.

\medskip
\noindent
Kriterium für positive Bewertung: mindestens 50\,\%, das sind 15 Punkte.
\medskip
\hrule
\medskip


\loop

\seite
\begin{enumerate}

\item (10 Punkte)
Wandeln Sie die Grammatik
$$
\begin{array}{l}
S \to a{+}S \ \bigm| \ Ba
\\
B\to aBa \ \bigm|\ {+}a
\end{array}
$$
in Chomsky-Normal\-form um.
Prüfen Sie dann mit dem CYK-Algorithmus nach, ob das Wort
$a{+}aa{+}aaa$  von dieser Grammatik
erzeugt wird. Geben Sie gegebenenfalls einen Syntaxbaum 
%\emph{und} eine Linksableitung
 (für die \emph{ursprüngliche} Grammatik) an.

\seite

\item %(10 Punkte)
\begin{enumerate}
\item (5 Punkte)
Skizzieren Sie einen Algorithmus für das Wortproblem für
%kontextsensitive 
Typ-1-Sprachen. (etwa 5 Sätze)
\item (5 Punkte)
 Beweisen Sie: Die Vereinigung einer kontextfreien Sprache und einer regulären
  Sprache ist kontextfrei.

\end{enumerate}
\seite

\item %(10 Punkte)
Die Grammatik
$$
\begin{array}{l}
S\to S + S \ \bigm|\ S * S \ \bigm|\ (S) \ \bigm|\ Z\\
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 einfache arithmetische Ausdrücke mit einzelnen Ziffern als Operanden ist
mehrdeutig, weil zum Beispiel für den Ausdruck
$3+4*5$ aus der Grammatik nicht hervorgeht, ob $3+4$ oder $4*5$ zuerst
berechnet werden soll.
\begin{enumerate}
\item Geben Sie \emph{alle} möglichen Syntaxbäume 
und \emph{alle} möglichen Linksableitungen für das Wort
$3+4*5$ an.
\item
Die Mehrdeutigkeit kann durch die gängige Regel aufgelöst werden, dass
die Multiplikation ($*$) stärker bindet als die Addition ($+$).
Das Beispiel wird also so interpretiert,
dass $3+4*5=3+20=23$ herauskommt, wenn man es ausrechnet.
% als ob $3+(4*5)$ stünde.
Schreiben Sie eine äquivalente \emph{eindeutige} Grammatik, die diese Regel widerspiegelt.
\end{enumerate}
\seite

\end{enumerate}

\iferstes
 \erstesfalse
 \def\seite{\eject\nam}
 \setcounter{page}{0}
\repeat

%\hrule
%\medskip

%\noindent
%\emph{Hinweis:}


\end{document}

