% 2. Klausur GTI SS 2005
\documentclass [12pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {ngerman}
\usepackage[latin1]{inputenc}
\textwidth=16cm
\textheight=22cm
\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}{3}
%\thispagestyle{empty}
%\nam

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

%Nachklausur zur 
Abschlussklausur
%Montag, 6. Juni 2005

}

\medskip
Abgabe bis Montag, 11. Juli 2005, 11:45 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)
Geben Sie für die folgende kontextfreie Grammatik über dem
Terminalalphabet
$\Sigma=\{1,2,3\}$ einen äquivalenten
Kellerautomaten an. Entscheiden Sie selbst,
ob der Automat deterministisch oder nichtdeterministisch ist, und wie der
Automat akzeptieren soll.
$$
\begin{array}{l}
S\to SSS \ \bigm| \ A
\\
A\to A1A \ \bigm|\ AS2 \ \bigm|\ 3
\end{array}
$$

\seite

\item %(10 Punkte)
\begin{enumerate}
\item (5 Punkte)
Formulieren Sie 
wahlweise
das Pumping-Lemma für kontextfreie Sprachen
oder
das Pumping-Lemma für reguläre Sprachen.

\item (5 Punkte)
Beweisen Sie, dass die Sprache aller Doppelwörter
$$\left\{\,ww\mid w \in \{0,1\}^*\,\strut\right\}$$
nicht kontextfrei ist.
\end{enumerate}
\seite
\item (10 Punkte)
Wandeln Sie die Grammatik
$$
\begin{array}{l}
S\to aS \ \bigm| \ aAAS \ \bigm| \ B
\\
A\to Sb \ \bigm|\ aSb \ \bigm|\ \varepsilon
\\
B\to bA \ \bigm|\ AS
\end{array}
$$
in Chomsky-Normal\-form um.


\seite


\end{enumerate}

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

%\hrule
%\medskip

%\noindent
%\emph{Hinweis:}


\end{document}

