Grundlagen der theoretischen Informatik, SS 2001 — 3. Übungsblatt

Abgabe bis Montag, 14. Mai 2001

12. (6 Punkte) Zeichnen Sie das Zustandsdiagramm des NEA ({a, b, c, d, e}, {0, 1}, δ, {a}, {e}) mit δ = {(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.

13.

(0 Punkte) Konstruieren Sie für den DEA M = ({a, b, c}, {0, 1}, δ, a, {b}) einen regulären Ausdruck, der die von M akzeptierte Sprache beschreibt. Die Übergangsfunktion δ ist in der nebenstehenden Tabelle angegeben.

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.

\begin{matrix}δ & 0 & 1 \\ a & a & b \\ b & c & b \\ c & b & a \end{matrix}

14. (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 nichtdeterministische endliche Automaten? Wie muss man die Konstruktion in diesem Falle anpassen, oder an welcher Stelle ist es wesentlich, dass der Automat deterministisch ist?

15. (0 Punkte) Betrachten Sie deterministische sowie nichtdeterministische endliche Automaten (mit oder ohne ε-Ü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?

16. (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.

17. (0 Punkte) Konstruieren Sie DEAs und NEAs für folgende Sprachen über {0, 1}:

(a) die Wörter, deren vierter Buchstabe eine 1 ist;

(b) die Wörter, deren viertletzter Buchstabe eine 1 ist.

18. (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} ∪ L_{2}, (b) L_{1} · L_{2}, (c) L_{1} ∩ 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.