%  1c. Klausur GTI SS 2001
\documentclass [12pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=16cm
\textheight=22cm
\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

zweite Nachklausur zum 1.~Teil,
Dienstag, 9. Oktober 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 (10 Punkte)
$L_1$ sei eine reguläre Sprache über dem Alphabet $\{0,1\}$, und
$$ L_2= \{\, w_10w_20\ldots 0w_n\mid w=w_1w_2\ldots w_n\in L_1,\ n\ge1
,\ w_i\in\{0,1\}
\,\}$$
sei die
Sprache, wo zwischen je zwei Buchstaben eine Null eingefügt
ist. (Am Ende wird \emph{keine} Null angehängt!)
Beweisen Sie, dass $L_2$ ebenfalls regulär ist.

\seite


\item (10 Punkte)
Betrachten Sie den nichtdeterministischen endlichen Automaten
 $M=(\{a,b,c\},\{0,1\},\delta,\{a\},\{a\})$
mit $$\delta=\{(a,0,a),(a,0,b),(b,1,b),(b,1,c),(c,0,c),(c,0,a)
\}.$$
Konstruieren Sie einen dazu äquivalenten deterministischen
Automaten, und den Minimalautomaten.
(Der Minimalautomat ist immer ein deterministischer Automat.)

\seite
\item (10 Punkte)
Konstruieren Sie einen endlichen Automaten
\emph{ohne} $\varepsilon$-Übergänge, der die Sprache
$$(a+ba)^+(b+ab)^*+
(bb)^*a^+(bb)^*$$
akzeptiert.
\seite

\item (Zusatzfrage, 5 Punkte)
Ist das folgende Problem entscheidbar?
\begin{quote}
  Gegeben sind zwei reguläre Ausdrücke $R$ und $S$.
  Stellen diese beiden Ausdrücke dieselbe Sprache dar?
\end{quote}
Begründen Sie Ihre Antwort, indem Sie entweder einen
Lösungsalgorithmus oder einen
Nichtentscheidbarkeitsbeweis in groben Zügen skizzieren.
\end{enumerate}

\erstesfalse %%%% 

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

%\hrule
%\medskip

%\noindent
%\emph{Hinweis:}


\end{document}

