Blatt 2

Wintersemester 2015/16
Übungsaufgaben zur Vorlesung
Diskrete Modellierung
Friedrich-Schiller-Universität Jena
Institut für Informatik
Stephan Fischer
Martin Mundhenk
Aufgaben zum 9.11.2015
Aufgabe 5: Endlicher Automat (Komplement)
4 Punkte
Geben Sie einen endlichen Automaten an, der alle Wörter über dem Alpabet Σ = {a, b}
akzeptiert, die nicht das Wort aab enthalten.
Aufgabe 6: Endlicher Automat (rückwärts)
2+3+1+2 Punkte
Die folgende Tabelle beschreibt die Zustandsübergänge eines endlichen Automaten M
mit dem Alphabet Σ = {a, b}, der Zustandsmenge Z = {1, 2, 3}, Startzustand S = 1 und
Endzustandsmenge E = {3}.
a b
1 2 1
2 1 3
3 3 2
1. Geben Sie einen regulären Ausdruck für die vom Automaten M akzeptierte Sprache
an.
2. Konstruieren Sie aus M einen neuen Automaten M 0 , der genau die Wörter akzeptiert,
die rückwärts gelesen von M akzeptiert werden. Z.B. akzeptiert M das Wort bbaba.
Also soll M 0 das Wort ababb akzeptieren.
3. Geben Sie einen regulären Ausdruck für die vom Automaten M 0 akzeptierte Sprache
an.
4. Die Konstruktion des Rückwärts-Automaten“ ist in diesem Beispiel sehr einfach.
”
Finden Sie ein anderes Beispiel, bei dem das nicht so einfach geht.
Aufgabe 7: Umwandlung endlicher Automat in regulären Ausdruck6 Punkte
Wandeln Sie den folgenden Automaten mit dem Verfahren aus der Vorlesung in einen
regulären Ausdruck um.
a
a
q0
q1
q3
start
b
a
b
b
q2
b
a
Aufgabe 8: reguläre Ausdrücke vereinfachen
8 Punkte
Vereinfachen Sie die folgenden regulären Ausdrücke. D.h. finden Sie einfachere reguläre
Ausdrücke für die Sprachen, die durch die regulären Ausdrücke über dem Alphabet {a, b}
beschrieben werden.
1. (a|b)∗ (a|ε)b∗
2. (∅∗ |b)b∗
3. (a∗ (ab)∗ )∗
4. ((a|b)|(ab|b)∗ )|a(ab|b)∗ b
Aufgabe 9:
reguläre Ausdrücke vergleichen
10 Punkte
Geben Sie an, ob die folgenden Aussagen wahr oder falsch sind. Begründen Sie kurz Ihre
Entscheidung.
1. L((ab)∗ a) = L(a(ba)∗ )
2. L((a|b)∗ b(a|b)∗ ) = L(a∗ b(a|b)∗ )
3. L((a|b)∗ a(a|b)∗ |(a|b)∗ b(a|b)∗ ) = L((a|b)∗ )
4. L((a|b)∗ a(a|b)∗ |(a|b)∗ b(a|b)∗ ) = L((a|b)+ )
5. L((a|b)∗ ba(a|b)∗ |a∗ b∗ ) = L((a|b)∗ )
(α+ = αα∗ für bel. reg. Ausdrücke α)

Download Report