%  1. Klausur GTI WS 1999/2000
\documentclass [12pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {ngerman}
\usepackage[latin1]{inputenc}
\textwidth=15cm
\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{\hfil NAME: 
\vrule height -1,6pt depth 2pt width 5cm
MATRIKELNUMMER:
\vrule height -1,6pt depth 2pt width 3cm
\hskip -1cm
}\vss}}

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

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

 Zwischenklausur,
 Montag, 6. Juni 2005

}

\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 \ \rlap{ \quad gesamt: 30}\\
\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)
Welche dieser Aussagen sind wahr? Geben Sie einen Beweis oder ein
Gegenbeispiel an.
\begin{enumerate}
\item (3 Punkte)
Wenn $L$ entscheidbar ist, dann ist auch $L^*$ entscheidbar.
\item (3 Punkte)
Wenn $L$ unentscheidbar ist, dann ist auch $L^*$ unentscheidbar.
\item (4 Punkte)
Wenn $L$ rekursiv aufzählbar ist, dann ist auch $L^*$ rekursiv aufzählbar.
\end{enumerate}
\seite

\item[2a.] (5 Punkte)
Definieren Sie, was ein regulärer Ausdruck über einem Alphabet
$\Sigma$ ist.
\seite

\item[2b.] (5 Punkte)
Was ist die kleinste Sprache $L$, für die
$$ L = \{0,01\} \ \cup\ L \cdot \{000,111\} $$
ist? Geben Sie einen regulären Ausdruck für $L$ an.

\seite
\item[3.] (10 Punkte)
Konstruieren Sie den Minimalautomaten für die folgende Sprache
$L\subset \{0,1\}^*$:

$$ L = \{\,w\mid \parbox[t]{9cm}{$w$ enthält eine ungerade Anzahl von
  Einsen,\\ und direkt vor jeder Eins steht eine Null$\,\}$}
$$
Begründen Sie in 1--2 Sätzen, warum Ihr Automat diese Sprache
akzeptiert.
Wenn Sie den Automaten nicht durch den Minimierungsalgorithmus
konstruiert haben, dann beweisen Sie auf andere Art, dass es der
Minimalautomat ist.
\end{enumerate}

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

%\hrule
%\medskip

%\noindent
%\emph{Hinweis:}


\end{document}

