10. Übungszettel - Woche 06.

Prof. Dr. R. Schrader
Birgit Engels [[email protected]]
SS 2009
Theoretische Informatik
10. Übung
Aktuelle Informationen bezüglich der Vorlesung und der Übungen finden sich unter :
http://www.zaik.uni-koeln.de/AFS/teachings/courses/ThInf/index.html und
http://www.zaik.uni-koeln.de/AFS/teachings/courses/ThInf/uebungen.html
Aufgabe 36 (DEAs — Deterministische Eis(?)-Automaten (*)):
Entwerfen Sie einen deterministischen endlichen Eis-AutomatenA = (Q, q0 , F, Σ, δ) mit folgender Funktionalität:
• Der Automat verkauft Magnum zu 2 Euro, Cornetto zu 1 Euro und Wassereis zu 50 Cent.
• Der Automat akzeptiert 50-Cent-Stücke sowie 1- und 2-Euro-Stücke.
• Ein Einwurf, der den gesamten bisher eingeworfenen Geldbetrag über 2 Euro ansteigen lässt,
wird nicht akzeptiert. (Die eingeworfene Münze ’fällt durch’ und der Zustand des Automaten
ändert sich nicht.)
• Der Automat hat 4 Tasten : Magnum, Cornetto, Wassereis, Reset.
• Wird eine der Wahltasten gedrückt, so wird — falls genügend Geld eingeworfen wurde —
das entsprechende Eis, Restgeld ausgegeben und der Automat kehrt in den Ausgangszustand
zurück. Andernfalls tritt keine Veränderung ein.
• Wird die Taste Reset betätigt, so gibt der Automat sofort das bisher eingeworfene Geld aus
und kehrt in den Ausgangszustand zurück.
Hinweis: Geben Sie die Menge der Zustände Q, den Startzustand q0 , die Menge der (akzeptierenden) Endzustände F und das Alphabet Σ an und stellen Sie δ als gerichteten Graphen mit Knoten
aus Q und Kantenbeschriftungen aus Σ dar. Ausgaben (Eis,Geldstücke) können Sie ebenfalls (z.B.
durch ’/’ vom eingelesenen Zeichen getrennt) an den Kanten notieren.
Aufgabe 37 (DEA-Minimierung — Unerreichbare Zustände (**)):
Geben Sie einen Algorithmus (in Pseudo-Code) an, der alle nicht erreichbaren Zustände eines Automaten entfernt. Der Automat M kann in seiner Darstellung als Graph G(M) = (V, E) betrachtet
werden.
Aufgabe 38 (DEA-Minimierung — Äquivalente Zustände (*)):
Wenden Sie den Algorithmus zur Markierung äquivalenter Zustände (aus der Vorlesung) auf den
13
3
d
c
2
e
e
e
5
c
11
d
a,b
12
e
4
a
6
10
a,b
1
c
d
b
7
9
d
8
c
Abbildung 1: Nicht minimaler DEA und Kölner Kennzeichen.
untenstehenden Automaten M an und erzeugen Sie so den minimierten Automaten M ′ mit L(M) =
L(M ′ )! (Beachten Sie dabei auch Aufgabe 37.)
Aufgabe 39 (Reguläre Mengen, reguläre Ausdrücke (**)):
In der Vorlesung habe Sie reguläre Sprachen kennengelernt. Diese entsprechen im Prinzip einer
regulären Menge von Worten über einem Alphabet Σ. Reguläre Mengen können wie folgt induktiv
definiert und durch reguläre Ausdrücke beschrieben werden:
Reguläre Menge
∅ ist eine reguläre Menge über Σ.
{ǫ} ist eine reguläre Menge über Σ.
∀a ∈ Σ : {a} reguläre Menge über Σ.
Für 2 reguläre Mengen P und Q über Σ gilt:
P ∪ Q ist eine reguläre Menge über Σ.
P Q = {pq|p ∈ P, q ∈ Q} ist eine reguläre Menge über Σ.
P ∗ = ∪n≥0 P n ist eine reguläre Menge über Σ.
Es gibt keine weiteren regulären Mengen über Σ.
regulärer Ausdruck
∅
ǫ
a∈Σ
(p|q)
(pq)
(p∗ )
Beispielsweise lässt sich die Menge der Fliesskommazahlen über dem Alphabet Σ mittels des
regulären Ausdrucks
(0|(1| . . . |9)(0|1| . . . |9)∗), (0|1| . . . |9)∗, Σf = {0, . . . , 9} ∪ {, }
darstellen. (Zur eindeutigen Lesbarkeit werden Klammern verwendet.) Wiederkehrende Teilausdrücke können dabei auch durch eigene Benennungen ( ∈
/ Σ !) und geeignete Abkürzungen (. . .)
verkürzt werden:
(0|(1| . . . |9)zif ∗ ), zif ∗ mit zif = (0|1| . . . |9).
Weiterhin liesse sich z.B. die Anzahl n der Nachkommastellen begrenzen mittels
(0|(1| . . . |9)(0|1| . . . |9)∗ ), (0|1| . . . |9)n .
Zeigen Sie, dass die Sprache LKf z der zulässigen Kfz-Kennzeichen von Köln regulär ist, indem
Sie:
a) LKf z durch die Beschreibung mit regulären Ausdrücken als reguläre Menge ausweisen.
b) Einen (minimalen) DEA konstruieren, der LKf z akzeptiert!