%  1b. Klausur GTI SS 2001
\documentclass [12pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=16cm
\textheight=23cm
\hoffset = -17mm
\voffset = -20mm

\newif\iferstes
%\erstestrue
\let\seite\relax

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

\begin{document}
\setcounter{page}{0}
\thispagestyle{empty}
\nam

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

erste Nachklausur zur 1.~Klausur,
Mittwoch, 25. Juli 2001}
\par \smallskip
\end{centering}$$
\begin{tabular}{|l| r r r r   |}
\hline
 
Aufgabe
\vrule height 12pt depth 6pt width 0pt
&\ 1 &\ 2 &\ 3 & (4) \ \\
\hline
Punkte
\vrule height 14pt depth 6pt width 0pt
& 10 & 10& 10 & (5) \ \\
\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 dem dafür vorgesehenen \emph{Blatt}.
Verwenden Sie gegebenfalls Ergänzungsblätter.
Schreiben Sie auf \emph{alle} Blätter Ihren Namen und Ihre
Matrikelnummer.

\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 % \iferstes\else (10 Punkte)\fi
  \begin{enumerate}
  \item (3 Punkte)
Konstruieren Sie einen endlichen Automaten, der die durch 5
teilbaren
Binärzahlen akzeptiert.

  \item (7 Punkte)
Konstruieren Sie einen endlichen Automaten (\emph{ohne}
$\varepsilon$-Übergänge) für die
 Sprache
$$ L = \{\, w0\mid w\hbox{ ist durch 5 teilbar}\,\}
\cup \{\, w1\mid w\hbox{ ist durch 7 teilbar}\,\}.$$
"`$w$ ist durch 5 teilbar"' bedeutet, dass $w\in\{0,1\}^*$ ein Vielfaches von 5
ist, wenn man es als Binärzahl interpretiert.
  \end{enumerate}
Erläutern Sie Ihre Konstruktionen durch wenige Sätze.
\seite


\item (10 Punkte)
Beweisen Sie,  dass die regulären Sprachen unter
{Teilfolgenbildung} abgeschlossen sind:
Wenn $L$ regulär ist, dann ist auch
$$L' = \{\, x \mid \hbox{es gibt ein $y\in L$,
sodass $x$ Teilfolge von $y$ ist}\,\}$$
regulär.
Ein Wort $x\in\Sigma^*$
 ist \emph{Teilfolge} von $y=y_1y_2\ldots y_n$, ($y_i\in
\Sigma$)
wenn
$x=y_{i_1}y_{i_2}\ldots y_{i_k}$ für $1\le i_1<i_2<\cdots <i_k\le n$,
$k\ge0$, ist.



\seite
\item (10 Punkte)
Zeichnen Sie das Zustandsdiagramm des
\iffalse/erstes 
NEA
 $(\{a,b,c,d\},\{0,1\},\delta,\{a\},\{d\})$
mit $\delta=\{(a,0,b),(a,1,a),(a,1,c),(b,0,a),(b,1,b),
(b,1,c),(c,0,d),(d,0,d)\}$,
\else
nichtdeterministischen endlichen Automaten
 $M=(\{a,b\},\{0,1\},\delta,\{a\},\{b\})$
mit $$\delta=\{(a,0,a),(a,0,b),(a,1,b),(b,1,b),(b,0,a)
\}.$$
\fi
Bestimmen Sie einen dazu äquivalenden \emph{deterministischen}
endlichen Automaten.
%
Bestimmen Sie einen Automaten, der die komplementäre Sprache 
$\{0,1\}^*-L(M)$ akzeptiert.
%
Geben Sie einen regulären Ausdruck für $L(M)$ an.
\seite

\item (Zusatzfrage, 5 Punkte)
Ist für jede reguläre Sprache $L_1$ über dem Alphabet
$\Sigma=\{0,1\}$ auch die Sprache
$$L_2 = \{\,w\in \Sigma^* \mid 01001w \in L_1\,\}$$
regulär?
Beweisen Sie Ihre Antwort.
\end{enumerate}

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

%\hrule
%\medskip

%\noindent
%\emph{Hinweis:}


\end{document}

