Lösungen zum Aufgabenblatt 6
Formale Sprachen und Automaten
Universität München, CIS, WS 2015/16
Hans Leiß
Ausgabe: Do 26.11.2015
Abgabe: Do 3.12.2015
Aufgabe 6.1
Sei Σ = {a, b} und A der im folgenden dargestellte Automat:
a
A=
2
b
b
b
1
a
3
Eine Relation R ⊆ Q × Q ist (links-)total, wenn es zu jedem p ∈ Q ein q ∈ Q mit (p, q) ∈ R
gibt, und R heißt funktional, wenn es zu jedem p ∈ Q höchstens ein q ∈ Q mit (p, q) ∈ R gibt.
(a) Warum ist der Automat A nicht determinstisch?
a
b
a
b
(b) Sind die Relationen −→ und −→ von A auf Q = {1, 2, 3} total?
(c) Sind die Relationen −→ und −→ von A auf Q = {1, 2, 3} funktional?
a
(d) Stelle die Relationen −→
a1,1
A = a2,1
a3,1
b
und −→ als 3 × 3-Matrizen
b1,1
a1,2 a1,3
und
B = b2,1
a2,2 a2,3
b3,1
a3,2 a3,3
b1,2
b2,2
b3,2
b1,3
b2,3
b3,3
mit Einträgen ai,j , bi,j ∈ B dar und berechne A + B und A · B nach den Formeln der
Vorlesungsfolien.
(e) Gib für das Wort aba eine akzeptierende und eine nicht akzeptierende Berechnung (Konfigurationsfolge) an!
(f) Erweitere den Automaten um einen Zustand 4 (eine Senke“) und einige Kanten zu einem
”
a
b
vollständigen Automaten A′ (d.h. mit totalen Relationen −→ und −→ ) mit L(A′ ) =
L(A).
1
Lösung von Aufgabe 6.1
(a) Weil vom Zustand 2 zwei b-Kanten zu verschiedenen Zuständen (1 und 3) führen.
a
b
(b) −→ ist nicht total, weil vom Zustand 2 keine a-Kante ausgeht, und −→ ist nicht total,
weil vom Zustand 1 keine b-Kante ausgeht.
a
(c) Die Relation −→ ist funktional und entspricht der partiellen Funktion
falls i = 1,
2,
falls i = 3,
fa (i) := 1,
undefiniert, sonst.
b
Die Relation −→ ist nicht funktional, da von Zustand 2 ja b-Kanten zu verschiedenen
Zuständen ausgehen.
a
(d) Wir haben nach der Definition ai,j = 1 ⇐⇒ i −→ j usw.:
0 1 0
0 0 0
A = 0 0 0
und
B = 1 0 1
1 0 0
0 0 1
P
Nach der Definition von A · B = ( c )i,j mit ci,j = 3k=1 ai,k bk,j = ai,1 b1,j + ai,2 b2,j + ai,3 b3,j
ist
0·0+1·1+0·0 0·0+1·0+0·0 0·0+1·1+0·1
1 0 1
A · B = 0 · 0 + 0 · 1 + 0 · 0 0 · 0 + 0 · 0 + 0 · 0 0 · 0 + 0 · 1 + 0 · 1 = 0 0 0,
1·0+0·1+0·0 1·0+0·0+0·0 1·0+0·1+0·1
0 0 0
und in der Tat kommt man mit ab in A von Zustand 1 nach 1 und von Zustand 1 nach 3,
ab
ab
was sozusagen 1 −→ 1 und 1 −→ 3 entspricht.
(e) Eine akzeptierende Berechung zu aba ist
(1, aba) ⊢ (2, ba) ⊢ (1, a) ⊢ (2, ǫ),
eine nicht akzeptierende Berechnung zu aba ist
(1, aba) ⊢ (2, ba) ⊢ (3, a) ⊢ (1, ǫ).
(f) Ergänze einen neuen Zustand 4 und die Kanten
a
2 −→ 4,
a
4 −→ 4,
a
b
1 −→ 4,
b
b
4 −→ 4.
Dann sind die neuen Relationen −→ und −→ total, und es wird kein weiteres Wort
akzeptiert, da jeder vorher nicht vorhandene Weg zum Zustand 4 führt und im NichtEndzustand 4 endet.
2
Aufgabe 6.2
Sei Σ = {a, b} und A der Automat aus Aufgabe 6.1:
a
A=
b
2
b
b
1
3
a
(a) Berechne einen (vollständigen) deterministischen Automaten Adet mit L(Adet ) = L(A)
(nach der Potenzmengenkonstruktion“).
(3 Punkte)
”
(b) Gib zwei verschiedene Berechnungen für ababa mit dem nichtdeterministischen Automaten
A an und vergleiche sie mit der einzigen Berechung mit dem deterministischen Automaten
Adet .
(2 Punkte)
(c) Gib A in Matrixform huI , A, vF i an.
(2 Punkte)
(d) Berechne die Iterierte A∗ von A nach der Rekursionsformel für A∗ .
(3 Punkte)
(e) Berechne einen regulären Ausdruck für L(A) durch uTI · A∗ · vF , wobei
T
u1,1
uT = u2,1 := ( u1,1 u2,1 u3,1 )
u3,1
die transponierte“ Matrix zu u ist.
(2 Punkte)
”
(f) Gib A durch ein Ungleichungssystem an wie im Beweis des Satzes von Kleene. (2 Punkte)
Benutze bei (c) bis (e) die Definitionen der Vorlesungsfolien zu Matrizen, Matrixmultiplikation
und die Rekursionsformel zur Berechnung der iterierten Matrix A∗ .
Bem. Wenn Ihnen die Rekursionsformel für A∗ zu kompliziert ist, können Sie den regulären
Ausdruck für L(A) auch durch Lösen des Gleichungssystems aus (f) bestimmen.
Lösung von Aufgabe 6.2
(a) Der durch die Potenzmengenkonstruktion aus A berechnete (vollständige) deterministische
Automat ist
b
a
{}
b
a
{1}
A
det
a
{2}
=
a
b
b
a
{1,3}
{1,2}
a
b
b
{3}
3
(b) Mit A gibt es zu ababa eine akzeptierende Berechnung,
(1, ababa) ⊢ (2, baba) ⊢ (1, aba) ⊢ (2, ba) ⊢ (1, a) ⊢ (2, ǫ),
und eine nicht-akzeptierende:
(1, ababa) ⊢ (2, baba) ⊢ (1, aba) ⊢ (2, ba) ⊢ (3, a) ⊢ (1, ǫ).
Mit Adet gibt es nur eine Berechnung, und diese ist akzeptierend:
({1}, ababa) ⊢ ({2}, baba) ⊢ ({1, 3}, aba) ⊢ ({1, 2}, ba) ⊢ ({1, 3}, a) ⊢ ({1, 2}, ǫ).
Wie man sieht, enthalten die durchlaufenen Zustände von Adet mindestens die Zustände
von A, die A bei der akzeptierenden Berechnung durchläuft.
(c)
1
0
A = hu, M, vi = h 0 , b
0
a
a 0
0
0 b , 1 i.
0 b
0
(d) Zerlege M (zum Beispiel) gemäß
0 a 0
A
b 0 b
M=
=
C
a 0 b
B
D
und benutze die Rekursionsformel
F∗
F ∗ BD∗
∗
M =
mit F = A + BD∗ C,
D∗ CF ∗ D∗ + D∗ CF ∗ BD∗
analog zur Berechnung von F ∗ . Das ergibt wegen D∗ = (b)∗ = (b∗ ) und
0 ˙ ∗
0
und D∗ C = (b∗ ) · ( a 0 ) = ( b∗ a
BD∗ =
(b ) =
b
bb∗
0)
zunächst
∗
F = A + BD C =
0 a
b 0
0
+
·( a
bb∗
0) =
0 a
b 0
0
+
bb∗ a
0
0
=
0
b + bb∗ a
a
0
und dann mit der Rekursionsformel für F ∗ und f = 0 + a0∗ (b + bb∗ a) = a(b + bb∗ a):
f∗
f ∗ a0∗
f∗
f ∗a
F∗ =
=
.
0∗ (b + bb∗ a)f ∗ 0∗ + 0∗ (b + bb∗ a)f ∗ a0∗
(b + bb∗ a)f ∗ 1 + (b + bb∗ a)f ∗ a
Also wird
∗
∗
∗
F BD = F ·
0
bb∗
=
f ∗ abb∗
(1 + (b + bb∗ a)f ∗ a)bb∗
und
D∗ CF ∗ = ( b∗ a 0 ) · F ∗ = ( b∗ af ∗
4
b∗ af ∗ a )
sowie
∗
∗
∗
D CF BD =
( b∗ af ∗
b∗ af ∗ a )
·
0
bb∗
= (b∗ af ∗ abb∗ )
schließlich
f∗
∗
M = (b + bb∗ a)f ∗
b∗ af ∗
f ∗a
1 + (b + bb∗ a)f ∗ a
b∗ af ∗ a
f ∗ abb∗
(1 + (b + bb∗ a)f ∗ a)bb∗ .
b∗ + b∗ af ∗ abb∗
(e) Mit dem vorigen Teil der Aufgabe erhalten wir
uT · M ∗ · v = ( 1
0 0 ) · M∗ · v = ( f∗
f ∗a
f ∗ abb∗ ) · v = (f ∗ a) = ((a(b + bb∗ a))∗ a).
Der Ausdruck f ∗ a beschreibt alle Wege vom Anfangszustand 1 zum Endzustand 2.
(f) Das am Bild abgelesene Ungleichungssystem ist
x0 ≥ x1
x1 ≥ ax2
x2 ≥ bx1 + bx3 + 1
x3 ≥ ax1 + bx3 .
Durch Variablenelimination erhalten wir aus der letzten Ungleichung
x3 ≥ b∗ ax1 ,
setzen das in die Ungleichung für x2 ein und erhalten die bezüglich x2 schon gelöste Ungleichung
x2 ≥ bx1 + bx3 + 1 ≥ bx1 + bb∗ ax1 + 1 = (b + bb∗ a)x1 + 1.
Einsetzen in die Ungleichung für x1 ergibt
x1 ≥ a((b + bb∗ a)x1 + 1) = a(b + bb∗ a)x1 + a ≥ (a(b + bb∗ a))∗ a.
Das ergibt für x0 ≥ x1 denselben Ausdruck f ∗ a wie in Teil (e) der Aufgabe.
5
© Copyright 2024 ExpyDoc
