Lösung 03 - Universität des Saarlandes

Universität des Saarlandes
Fakultät 6.2 – Informatik
Theoretische Informatik (WS 2015)
Team der Tutoren
Lösungsvorschlag 3
Aufgabe 3.1
(12 Punkte)
In dieser Aufgabe sollen sie für einige Sprachen zeigen, ob sie DEA- Sprachen sind oder nicht. Im positiven Fall
sollen sie das durch einen geeigneten endlichen Automaten, dargestellt durch seinen Übergangsgraphen beweisen.
Den negativen Fall können Sie durch das Zeigen von unendlich vielen Fortsetzungssprachen beweisen, oder auch
durch Anwendung des Pumping Lemmas.
Für einen Bitstring u ∈P
{0, 1}∗ bezeichnen wir mit hui die natürliche Zahl, die durch u binär dargestellt wird;
also huk−1 uk−2 ...u0 i = 0≤i<k ui 2i .
Hier sind vier zu untersuchende Sprachen.
(a) L0 = {w ∈ {a, b}∗ | #a (w)durch 3 teilbar und #b (w)durch 4 teilbar}
(b) L1 = {w ∈ {0, 1}∗ | hwidurch 6 teilbar}
(c) L2 = {w ∈ {0, 1}∗ | hwiist eine Quadratzahl}
(d) L3 = {w ∈ {0, 1}∗ | hwiist eine Primzahl}
Lösungsvorschlag 3.1
(a) Folgender Automat erkennt L0 :
b
start
b
q0,0
q0,1
a
a
a
b
q1,0
a
q1,1
a
b
q0,2
a
q1,2
a
b
q2,0
q2,1
q0,3
a
b
b
b
a
b
a
a
b
q2,2
q1,3
a
b
q2,3
b
(b) Vergleiche Übungsblatt 2, Aufgabe 2.4 a)
0
start
0
1
1
0
3
1
0
1
1
0
4
2
1
0
0
5
1
(c) Vergleiche Übungsblatt 2, Aufgabe 2.4 b)
Definiere für gerades n ≥ 2 : wn := 10n−2 1. Sei x die kleinste Binärzahl ungerader Länge, sodass wn x ∈ L5 .
1/4
Wegen |0n−2 1x| gerade, existiert ein k ∈ N mit h10n−2 1xi = 22k + a, wobei a = h1xi > 0.
Da a minimal gilt:
22k + a = (2k + 1)2 = 22k + 2k+1 + 1
⇒ a = 2k+1 + 1 und x = 0k 1
⇒ 2n+k + 2k+1 + 1 = h10n−2 10k 1i = 22k + 2k+1 + 1
⇒ n = k und x = 0n 1
Damit ist x = 0n 1 das kleinste Element in FL5 (wn ) mit ungerader Länge. Also gibt es unendlich viele
Fortsetzungssprachen und L5 ist nicht regulär.
(d) Wir definieren ein Wort w ∈ Σ∗ mit hwi = y und y > 2. Des weiteren sei wx1 ∈ FL3 (w), hwx1 i = x1 , sodass
wwx1 = y ∗ 2|w| + x1 eine Primzahl ist. Diese Kombination existiert wegen dem Hinweis. Wir definieren
nun:
hw(1) i = y
hw(2) i = y ∗ x1
hw(3) i = y ∗ x1 ∗ x2 , mit x2 = wx2 , sodass iw(2) wx2 h Prim ist.
Qi−1
hw(i) i = y ∗ k=1 xi , mit xj = wxj , sodass iw(j) wxj h Prim ist ∀j.
Sei nun i < j. FL3 (w(i) und FL3 (w(j) ) unterscheiden sich mindest in wxi , denn wxi L3 , aber
(j)
(j)
hw(j) i = 2|w | ∗ y ∗ x1 ∗ x2 ∗ ... ∗ xi ∗ ...xj−1 + xi = xi ∗ (2|w | ∗ y ∗ x1 ∗ x2 ∗ ... ∗ xi−1 ∗ xi+1 ∗ ... ∗ xj−1 + 1)
und damit keine Primzahl. Daraus folgt, dass es unendlich viele Fortsetzungssprachen gibt.
Aufgabe 3.2
(8 Punkte)
Es seien L1 und L2 zwei reguläre Sprachen, die von DEAs M1 und M2 akzeptiert werden, jeweils mit Zustandsmenge Q1 und Q2 .
Zeigen sie wie man aus M1 und M2 einen DEA M konstruieren kann, der L = L1 ∩ L2 akzeptiert und höchstens
|Q1 | · |Q2 | Zustände besitzt.
Lösungsvorschlag 3.2
Wir können M1 und M2 als folgende Quintupel darstellen: M1 = (Σ, Q1 , s1 , F1 , ∆1 ) und M2 = (Σ, Q2 , s2 , F2 , ∆2 )
Wir konstruieren M als das folgende Quintupel M = (Σ, Q, s, F, ∆) mit:
Q = Q1 × Q2
F = {(q1 , q2 ) ∈ Q|q1 ∈ F1 ∧ q2 ∈ F2 }
s = (s1 , s2 )
((q1 , q2 ), σ)∆(p1 , p2 ) ⇔ (q1 , σ)∆1 p1 ∧ (q2 , σ)∆2 p2
Ein Pfad in M mit der Beschriftung w endet im Zustand a = (a1 , a2 ) genau dann wenn ein Pfad in M1 mit der
Beschriftung w existiert, der im Zustand a1 endet und ein Pfad in M2 mit der Beschriftung w existiert, der im
Zustand a2 endet. M akzeptiert w genau dann, wenn M1 und M2 in akzeptierenden Zuständen enden, M1 und
M2 w akzeptieren.
Aufgabe 3.3
(10 Punkte)
Für n > 0 sei Ln die Sprache über {a, b}, die genau alle Strings enthält, deren n-letzter Buchstabe ein a ist.
(a) Zeigen Sie, dass Ln von einem NEA mit nur n + 1 Zuständen akzeptiert werden kann.
(b) Zeigen Sie, dass jeder DEA, der Ln akzeptiert mindestens 2n Zustände besitzen muss.
Lösungsvorschlag 3.3
(a) Ein NEA, der Ln erkennt ist gegeben durch:
(b) Seien w = w0 w1 ...wn−1 ∈ {a, b}n und v = v0 v1 ...vn−1 ∈ {a, b}n . Seien FLn (w) und FLn (v) die Fortsetzungssprachen zu w und v. Sei w =
6 v dann exstiert i < n mit wi 6= vi . Ohne Beschränkung darf
angenommen werden, dass wi = a und vi = b. Dann gilt bn−i−1 ∈ FLn (w) aber bn−i−1 ∈
/ FLn (v). Damit
ist FLn (w) 6= FLn (v) für alle unterschiedlichen w und v aus {a, b}n . Damit existieren mindestens 2n
2/4
Fortsetzungssprachen von Ln . Für jede Fortsetzungssprache muss der DEA mindestens einen anderen
Zustand besitzen.
Aufgabe 3.4
(12 Punkte)
Geben Sie einen regulären Ausdruck an, der genau alle binären Strings u beschreibt, sodass <u> mod 3 = 1.
Argumentieren Sie, warum Ihr Ausdruck tatsächlich die gewünschte Sprache beschreibt.
Lösungsvorschlag 3.4
Ein DEA, der die beschriebene Sprache akzeptiert, ist gegeben durch:
0
1
1
start
q0
0
q1
1
q2
0
Entsprechend vorrausgehenden Aufgaben gilt im Zustand qn für den bereits gelesenen Teilstring v <v> mod
3 = n.
a
Sei für i, j < 3 und a < 3 rij
der reguläre Ausdruck, der alle Beschriftungen von Pfaden von qi nach qj beschreibt,
die qa nicht als internen Knoten enthalten. Da der DEA nur einen Endzustand q1 besitzt, sind die Pfade, die in
1
q0 starten und in q1 enden die akzeptierenden Pfade. Es existiert nur ein Ausdruck r01
, der von q0 nach q1 führt
ohne q1 mehrmals zu durchlaufen.
1
1
r01
= r00
1 = 0∗ 1.
Es werden nun die Ausdrücke angehängt, die von q1 wieder nach q1 führen. Man betrachte zuerst nur die Pfade,
die von q1 nach q1 füheren ohne q1 als internen Knoten zu durchlaufen.
1
1
1
1 + 0r22
0 = 10∗ 1 + 01∗ 0
r11
= 1r00
Wir erhalten alle Pfade von q1 nach q1 durch die kleenesche Hülle dieser einfachen Pfade. Der gesuchte Ausdruck
lautet damit: 0∗ 1(10∗ 1 + 01∗ 0)∗
Aufgabe 3.5
Beweisen sie das sogenannte starkeP umpinglemma für reguläre Sprachen:
(8 Punkte)
Wenn L eine reguläre Sprache ist, dann gilt für sie folgende starke „Pumping-Eigenschaft“: Es gibt ein N ∈ N,
sodass für jedes Wort t ∈ L mit |t| ≥ N und für jede Unterteilung t = uvw mit |v| = N es eine Unterteilung
v = xyz mit |y| > 0 gibt, sodass uxy i zw ∈ L für jedes i ∈ N.
Lösungsvorschlag 3.5
Sei M = (Σ, Q, F, s, ∆) ein Automat, der L akzeptiert. Sei N = |Q| + 1 und seien u, v, w Wörter mit uvw ∈ L
und |v| ≥ N . Sei |u| = l, |v| = n und |w| = k. Da uvw ∈ L existiert ein Pfad q0 , q1 , ..., ql+n+k mit q0 = s,
ql+n+k ∈ F und ∀i < l + n + k
(qi , ui+1 )∆qi+1 falls i < l
(qi , vi+1−l )∆qi+1 falls l ≤ i < l + n
(qi , wi+1−l−n )∆qi+1 falls l + n ≤ i < l + n + k
Da n ≥ N , gibt es mehr Zustände ql , ..., ql+n als M verschiedene Zustände besitzt.Daher existieren i, j mit
l ≤ i < j ≤ l + n und qi = qj . Seien xyz = v mit |x| = i − m und |y| = j − i > 0. Dann existiert ein Teilpfad
q0 ...qi mit der Beschriftung ux, ein Teilpfad qi ...qj mit der Beschriftung y und ein Teilpfad qj ...ql+n+k mit der
Beschriftung zw. Da qi = qj können wir diesen Teilpfad beliebig oft, c-mal, durchlaufen und erhalten weiterhin
einen Pfad q0 ...ql+n+k mit dem das Wort uxy c zw akzeptiert wird. Damit gilt uxy c zw ∈ L.
Aufgabe 3.6
(10 Punkte)
Es sei Σ ein Alpahbet und ∈
/ Σ . Für Wort x = x1 . . . xk ∈ Σ∗ definiere I(x) als die Sprache, die durch den
regulären Ausdruck x1 + x2 + . . . + xk angegeben wird, dabei ist + eine Kurzform für ∗ (also eine nicht-leere
Folge von ’s.
Es sei ZΣ = (Σ∪{ })∗ ΣΣ(Σ∪ )∗ die Mege aller Strings über Σ∪ die mindestens zwei direkt aufeinanderfolgende
Zeichen aus Σ besitzen.
S
Für Sprache L ⊂ Σ∗ definiereI(L) = ZΣ ∪ x∈L I(x)
(a) Geben Sie eine verbale Beschreibung der Sprache I(L) an.
3/4
(b) Zeigen Sie, dass für jede Sprache L über Σ die Sprache I(L) über Σ ∪ { } die starke Pumping-Eigenschaft
mit N = 3 hat.
(c) Zeigen Sie, dass wenn I(L) regulär ist, dann ist auch L regulär.
(d) Geben Sie eine nicht-reguläre Sprache an, für die das starke Pumpinglemma gilt.
Lösungsvorschlag 3.6
(a) I(L) ist die Vereinigung der Menge aller Strings aus Σ∗ , wobei jedes Zeichen durch mindestens ein
Sonderzeichen ( ) getrennt ist und die Menge aller Strings über Σ ∪ { }, von denen mindestens zwei
aufeinanderfolgende Zeichen aus Σ sind.
S
(b) Sei N = 3. Dann ist jedes Wort t ∈ I(L) mit | t |≥ N entweder in ZΣ oder in x∈L I(x) . Sei nun t = uvw
die Unterteilung, mit | v |= N .
1. Fall Sei t ∈ ZΣ Wir unterscheiden hier wieder zwei Fälle:
1 v besteht aus mindestens einem . Dann wählen wir y = . Damit ist uxy i zw = ux i zw ∈ ZΣ
offensichtlich für alle i.
2 v = s1 s2 s3 mit s1 , s2 , s3 ∈ Σ. OBdA wählen wir nun y = s1. Dann gilt offensichtlich uxy i zw =
usi1S
s2 s3 zw ∈ ZΣ , da, unabhängig von der Wahl von i, s2 und s3 direkt aufeinander folgen.
2. Fall Sei t ∈ x ∈ LI(x). v besteht nun entweder nur aus , aus einem Zeichen xi oder aus zwei Zeichen
xi+1 .
1 Für v =
wähle y ein beliebiges . Offensichtlich ist uxy i zw immernoch in I(x).
2 Für v = xi xi+1 wähle y = . Für i = 0 ist ux1 y 0 xi+1 w = ux1 xi+1 w ∈ ZΣ , da x1 und xi+1 direkt
aufeinander folgen. Für i > 0 ist ux1 y i xi+1 w immernoch in I(x), da zwischen x1 und xi+1 noch
mindestens ein liegt.
3 Für v = xi wähle y zum Beispiel als erstes . Dann ist uxy i zw für i > 0 ∈ I(x) offensichtlich.
Für i = 0 ist uxy i zw enweder in ZΣ , wenn das letzte Zeichen in u = xi−1 oder in I(x), wenn das
letzte Zeichen in u ein ist. Die anderen beiden Fälle (v = xi und v = xi ) sind klar.
(c) Sei I(L) regulär. Damit besitzt I(L) nur endlich viele Fortsetzungssprachen FI(L) .
FZΣ = {{(Σ ∪ { })∗ ΣΣ(Σ ∪ )∗ }, {(Σ ∪ { })∗ }}, also endlich und F∪x∈L muss auch endlich sein.
Nun können wir die Menge der Fortestzungssprachen von L bestimmen, FL = {F 0 | ∃F ∈ FI(L) : ∀x0 :=
x1 x2 ...xn ∈ F 0 ∃x ∈ F : x = x1 x2 .. xn }. Da FI(L) endlich ist, muss auch FL endlich sein, und damit
ist L regulär.
(d) Zum Beispiel ist die Sprache I({an bn | n ∈ N}) ist nicht regulär, da im Umkehrschluss zu (c) gilt, dass
wenn L nicht regulär ist I(L) nicht regulär ist. Das starke Pumpinglemma gilt allerdings für diese Sprache.
4/4

Download Report