% 3. Uebungsblatt GTI SS 2001
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=16,1cm
\textheight=24cm
\hoffset = -19mm
\voffset = -25mm

\setcounter{page}{3}
\let\eps=\varepsilon
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2001 ---
 3.~\"Ubungsblatt\par
%ENTWURF
}
\medskip
Abgabe bis Montag, 14. Mai 2001
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{11}

\item (6 Punkte)
Zeichnen Sie das Zustandsdiagramm des NEA 
 $(\{a,b,c,d,e\},\{0,1\},\delta,\{a\},\{e\})$
mit $\delta=\{(a,0,a),(a,1,a),(a,0,b),(a,1,c),(b,0,b),
(b,1,d),(c,0,d),(d,1,e),(e,0,e)\}$,
und bestimmen Sie
einen dazu äquivalenten DEA.
Versuchen Sie, dabei mit möglichst wenigen Zuständen auszukommen.

\item
\noindent\hbox to \linewidth{\vtop{\hsize=\linewidth \noindent
\hangindent=-25mm \hangafter=-6
 (0 Punkte)
Konstruieren Sie für den DEA $M=(\{a,b,c\},\{0,1\},\delta,a,\{b\})$ einen
regulären Ausdruck, der die von $M$ akzeptierte Sprache beschreibt.
Die Übergangsfunktion $\delta$ ist in der nebenstehenden Tabelle angegeben.

\hangafter=-2
 Wenden Sie den in der Vorlesung
vorgestellten Algorithmus von Kleene auf die Zustände einmal in der
Reihenfolge $a,b,c$ und dann in der Reihenfolge $c,a,b$ an.
Vereinfachen Sie dabei die Zwischenergebnisse, so gut es geht.
Versuchen Sie auch, "`direkt"' durch Betrachten des
Zustandsdiagramms und Nachdenken
einen möglichst einfachen regulären Ausdruck zu finden.


}\llap {\vtop{ \hrule height 0pt \vskip -0,5\baselineskip
\hbox{\begin{tabular}[t]{|c|cc|}
\hline
$\delta$ & 0& 1\\\hline
$a$&$a$&$b$\\
$b$&$c$&$b$\\
$c$&$b$&$a$\\\hline
\end{tabular}%
}}}}

\item (5 Punkte)
Im Beweis für die Äquivalenz zwischen endlichen Automaten und
regulären Ausdrücken wird für
die von einem gegebenen deterministischen
endlichen Automaten akzeptierte Sprache
ein regulärer Ausdruck konstruiert.
Funktioniert diese Konstruktion auch für \emph{nichtdeterministische}
endliche Automaten?
Wie muss man die Konstruktion in diesem Falle anpassen,
oder an welcher Stelle ist es wesentlich, dass der Automat
deterministisch ist?

\item (0 Punkte)
Betrachten Sie deterministische sowie nichtdeterministische endliche Automaten
(mit oder ohne $\eps$-Übergänge),
die nur einen einzigen akzeptierenden Zustand haben dürfen.
Sind diese Automaten gegenüber allgemeinen endlichen Automaten
in ihrer Mächtigkeit eingeschränkt? Gibt es reguläre
Sprachen, die von solchen Automaten nicht erkannt werden können?

\item (3 Punkte)
Manchmal werden nichtdeterministische endliche Automaten so definiert,
dass Sie nur einen einzigen Anfangszustand haben.
Zeigen Sie, dass
diese Automaten gegenüber NEA's mit beliebig vielen Anfangszuständen
in ihrer Mächtigkeit
nicht eingeschränkt sind und dieselbe Klasse von Sprachen akzeptieren.

(Zusatzfrage, 2 Punkte)
Geben Sie eine möglichst einfache und sparsame Methode an, wie man aus
einem beliebigen NEA einen äquivalenten NEA mit nur einem
Anfangszustand konstruiert.

\item (0 Punkte)
Konstruieren Sie DEAs und NEAs für folgende Sprachen über $\{0,1\}$:
\begin{enumerate}
\item die Wörter, deren vierter Buchstabe eine 1 ist;
\item die Wörter, deren viertletzter Buchstabe eine 1 ist.
\end{enumerate}

\item (0 Punkte)
Gegeben seien zwei endliche Automaten $M_1$ und $M_2$, die die
Sprachen $L_1$ beziehungsweise $L_2$ akzeptieren.
Konstruieren Sie endliche Automaten, die die Sprachen
(a)~$L_1\cup L_2$, (b)~$L_1\cdot L_2$,
(c)~$L_1\cap L_2$ akzeptieren.
Sie dürfen dabei wahlweise mit deterministischen oder mit
nichtdeterministischen Automaten arbeiten, je nachdem, was
Ihnen für die jeweilige Aufgabe günstiger erscheint.

\end{enumerate}
\end{document}






