FSK Probeklausur
Prof. Dr. David Sabel Ludwig-Maximilians-Universität München
Stephan Barth Institut für Informatik
Sebastian Sturm 24. Mai 2019
Lösungsvorschlag zur Pfingst-Probe-Teil-Klausur zur Vorlesung
Formale Sprachen und Komplexität
Probeklausur für den ersten Vorlesungsteil! Diese Probeklausur deckt nur die bislang
behandelten Themen ab, die Hauptklausur wird sich natürlich auf den kompletten
Vorlesungsinhalt beziehen!
Zudem sind die Aufgaben in der Probeklausur natürlich nicht genau die Aufgaben aus der
Hauptklausur.
Keine Abgabe!
Aufgabe 1 Grammatiken An den Stellen, an denen in dieser Aufgabe nach einem Typ
(einer Sprache oder Grammatik) gefragt ist, ist der vollständige Typ gemeint, also ob die
Sprache bzw. Grammatik von Typ 0, von Typ 1, von Typ 2 und von Typ 3 ist. Es reicht aber
aus, jeweils diejenigen Typen anzugeben, mit denen bereits alle Typen eindeutig bestimmt
sind, also beispielsweise: Typ 2 aber nicht Typ 3.
a) Sei H = (V,Σ, P, S), wobei
• V = {S,A,B}
• Σ = {a, b}
• P = {S → ASB | AB,AA→ a,BB → b}
Geben Sie den Typ der Grammatik H und der Sprache L(H) an. Begründen Sie Ihre
Antwort.
LÖSUNGSVORSCHLAG:
Typ der Grammatik: Typ 0, aber nicht Typ 1. Typ 0, da es eine Grammatik ist, aber
nicht Typ 1, da es verkürzende Regeln gibt.
Typ der Sprache: Typ 2, aber nicht Typ 3, da die Sprache {aibi | i ∈ N>0} ist; die-
se Sprache ist nicht regulär (unendliche viele Nerode-Äquivalenzklassen, beispielsweise
[aib]) aber kontextfrei, kann beispielsweise gezeigt werden durch die kontextfreie Gram-
matik H = (V,Σ, P, S), wobei
• V = {S}
• Σ = {a, b}
• P = {S → aSb | ab, }
Geben Sie 2 Wörter aus L(H) an, sowie zwei Wörter aus Σ∗, die nicht in L(H) liegen.
LÖSUNGSVORSCHLAG: Wörter in L(H): ab, aabb; Wörter nicht in L(H): ba, a
b) Zeigen Sie für jedes i ∈ {0, 1, 2}: Für jede Grammatik I vom Typ i gibt es eine Gram-
matik J vom Typ i mit L(J) = {w | w ∈ L(I)}.
LÖSUNGSVORSCHLAG:
Sei I = (V,Σ, PI , S), dann ist J = (V,Σ, PJ , S), wobei PJ = {p → q | p → q ∈ PI}
eine Grammatik mit der gewünschten Eigenschaft. Denn mit ihr können genau die
Wortformen u erzeugt werden, bei denen mit I die Wortform u erzeugt werden kann.
Dies kann beispielsweise durch Induktion über die Anzahl notwendiger Schritte k zur
Herleitung des Wortes gezeigt werden:
• k = 0: Mit 0 Schritten kann nur die Wortform S in I hergeleitet werden, S = S
und in J kann ebenfalls nur die Wortform S hergeleitet werden.
• k → k+1: Sei v eine Wortform, die in I in k+1 Schritten hergeleitet werden kann.
Wähle eine Wortform u, die in I in k Schritten hergeleitet werden kann und bei
der I die Ableitung u→ v erlaubt (so ein u muss es geben, da v in k+ 1 Schritten
hergeleitet werden kann).
Nun erlaubt J die Herleitung von u in k Schritten. Wird mit der entsprechenden
umgedrehten Regel, mit der man von u nach v kommt in u die Ersetzung durch-
geführt, so wird damit v erzeugt; v ist damit ebenfalls in k + 1 Schritten in J
herleitbar.
Damit ist jede in I in k+ 1 Schritten herleitbare Wortform in J in k+ 1 Schritten
in umgedrehter Reihenfolge herleitbar.
Da das Umdrehen in den Produktionen die gleiche Argumentation von J nach I
erlaubt, sind in I und J sogar genau die gleichen Wortformen (bis auf Umdrehen)
herleitbar.
Aufgabe 2 Syntaxbaum
a) Sei G = (V,Σ, P, S), wobei
• V = {S,A,C}
• Σ = {a, b, c}
• P = {S → AbC,A→ ab | aAb,C → bc | bCc}
Entscheiden Sie für folgende Wörter, welche in L(G) liegen. Geben Sie für die Wörter in
L(G) einen Syntaxbaum an und für die Wörter, die nicht in L(G) liegen eine Begründung
an, warum sie nicht in L(G) liegen.
LÖSUNGSVORSCHLAG: Wörter in L(G) sind immer von der Form aibi+j+1cj , da
A immer Teilwörter der Form aibi produziert und C Teilwörter der Form bjcj .
• abbccc
LÖSUNGSVORSCHLAG: Nicht in L(G), da das Wort a1b2c3 ist, aber 1 + 1 +
3 6= 2
• acbbabcba
LÖSUNGSVORSCHLAG: Nicht in L(G), da Wort nicht in der Form aibjck
• abc
LÖSUNGSVORSCHLAG: Nicht in L(G), da das Wort a1b1c1 ist, aber 1 + 1 +
1 6= 1
• aabbbbc
LÖSUNGSVORSCHLAG:
In L(G), da das Wort a2b4c1 ist und 1 + 2 + 1 = 4
Syntaxbaum:
a a b b b b c
A C
A
S
• aaabbbbbbbbccc
LÖSUNGSVORSCHLAG: Nicht in L(G), da das Wort a3b8c3 ist, aber 1 + 3 +
3 6= 8
Aufgabe 3 Kleenescher Abschluss
a) Beweisen oder widerlegen Sie:
Sind A und B minimale DFA und es gilt L(A)∗ = L(B), so hat B mindestens so viele
Zustände wie A.
LÖSUNGSVORSCHLAG: Die Behauptung gilt nicht. Ein Gegenbeispiel ist das fol-
gende: Über dem Alphabet Σ = {a, b}. Ist L(A) = L(a | b | aaaaaaaa), so hat A mehr
als 1 Zustand. Es ist aber L(A)∗ = Σ∗. Ist B minimal mit L(B) = Σ∗, so hat B nur 1
Zustand.
b) Beweisen oder widerlegen Sie:
Sei L eine Sprache über dem Alphabet {a, b}, die nur Wörter enthält, die maximal die
Länge 4 haben.
Wenn aabaa ∈ L∗, dann gilt auch aaaa ∈ L∗
LÖSUNGSVORSCHLAG: Wähle v1, . . . , vk ∈ L mit v1 . . . vk = aabaa und ∀i ≤
k.|vi| > 0 (solche vi gibt es, da aabaa ∈ L∗ und Wörter der Länge 0 keine Buchstaben
beitragen, also nicht verwendet werden müssen; da |aabaa| > 4 ist k ≥ 2).
b kann nicht als Teilwort sowohl in v1 wie auch in vk vorkommen, da aabaa nur ein b
enthält.
Es ist also v ∈ {v1, vk} ∩ L(aa∗) 6= ∅. Sei nun v ∈ {v1, vk} ∩ L(aa∗).
Damit ist v ∈ L und v = a ∨ v = aa. Es ist also vvvv = aaaa ∨ vv = aaaa, also
aaaa ∈ L∗.
Aufgabe 4 Grammatiken und Automaten
Gegeben sei die Grammatik G = ({S,A,B}, {a, b}, {S → aA, A→ aA | aB,B → b | bS}, S).
a) Geben Sie einen NFA A mit L(G) = L(A) an.
LÖSUNGSVORSCHLAG:
S
A
B
zE
a
a
a
b
b
b) Verwenden Sie die Potenzmengenkonstruktion, um aus A einen DFA B mit L(B) =
L(A) herzuleiten. Es genügt hierbei, für den DFA B nur die vom Startzustand erreich-
baren Zustände zu betrachten.
LÖSUNGSVORSCHLAG:
Wir zeichnen nur die erreichbaren Zustände
{S} {A} {A,B}
∅ {S, zE}
a a
b
b
b
a
b
a
a, b
c) Erzeugen Sie gemäß der Konstruktion aus der Vorlesung aus B eine Grammatik H mit
L(B) = L(H).
LÖSUNGSVORSCHLAG:
Neubenennung der Zustände (um sie klarer erkenntlich als Variablennamen schreiben
zu können):
VS := {S}, VA := {A}, VAB := {A,B}, VSE := {S, zE}, Vn := ∅
H = ({VS , SA, VAB, VSE , Vn}, {a, b}, {
VS → aVA | bVn,
VA → aVAB | bVn,
VAB → aVAB | bVSE | b,
VSE → aVA | bVn,
Vn → aVn | bVn
}, VS)
Aufgabe 5 Produktautomat
a)
Seien A = sowie B =
p0 p1 p2
p3
a a
aa, b
b b b
q0 q1 q2
b b
a a
a b
Berechnen Sie einen Produktautomaten C mit L(C) = L(A) ∩ L(B).
Es genügt, die erreichbaren Teile des Produktautomatens anzugeben.
LÖSUNGSVORSCHLAG:
p0, q0
p0, q1
p0, q2
p1, q0
p1, q1 p1, q2
p2, q0
p2, q1
p2, q2
p3, q0
p3, q1
a
a
a
a
a
a
a
a
a
a
a
b
b
b
b
b
b
b
b
b
b
b
b) Wenn bei der Produktautomatenkonstruktion auch die nicht erreichbaren Zustände
gezählt werden:
Wie viele Zustände brauchen zwei Automaten D und F zusammengenommen mindes-
tens, damit der Produktautomat aus D und F mindestens 100 Zustände benötigt?
LÖSUNGSVORSCHLAG:
Bei Zustandszahlen n und m der Automaten D und F hat der Produktautomat aus D
und F genau n ·m Zustände, da nicht erreichtbare Zustände gezählt werden.
n ·m ≥ 100 mit n+m minimal erreicht man mit n = 10 = m.
Also haben D und F zusammengenommen 20 Zustände.
Aufgabe 6 Minimierung
Berechnen Sie einen äquivalenten minimalen DFA zu folgendem Automaten:
z0
z1 z2 z3
z4z5z6
z7 z8
b
a
a
b
b
a
b
a
b
a, ba
b
a
b
a
b
a
LÖSUNGSVORSCHLAG:
Ausgefüllte Tabelle der Automatenminimierung. Für die Nachvollziehbarkeit der Lösung:
• XE steht für inital ausgefüllte Zellen (Aufgrund dessen, dass Endzustände und nicht-
Endzustände nie vereinigt werden dürfen).
• i[pq], i ∈ N>0, p, q ∈ Z, Z ist die Zustandsmenge von A, steht für Zellen, die im i-ten
Durchlauf ausgefüllt werden; dass die Zustände p und q nicht vereinigt werden dürfen,
ist der Grund, wieso das durch diese Tabellenposition festgelegte Zustandspaar auch
nicht vereinigt werden darf.
Diese Tabelle ist symmetrisch, darum ist die halbe Tabelle ausreichend,
”
—“ kennzeich-
net die Zellen, die deshalb nicht angegeben werden müssen:
z0 z1 z2 z3 z4 z5 z6 z7 z8
z0 — — — — — — — —
z1 XE — — — — — — —
z2 1[z3z1] XE — — — — — —
z3 3[z4z1] XE 1[z4z3] — — — — —
z4 XE 2[z5z2] XE XE — — — —
z5 1[z6z1] XE 1[z6z4] 1[z6z4] XE — — —
z6 XE 1[z1z3] 3[z1z4] XE 1[z1z6] — —
z7 XE 1[z1z3] 3[z1z4] XE 1[z1z6] —
z8 1[z6z1] XE 1[z7z4] 1[z6z4] XE 1[z6z1] 1[z6z1]
Es können nun die Zustände zusammengefasst werden. Es ist also B =
z0, z6, z7 z1 z2
z3
z4z5, z8
a,b
b
a
b
b
a,b
a
a
a
b
Aufgabe 7 Abschlusseigenschaften
a) Zeigen Sie, dass Typ 0-Sprachen unter Konkatenation abgeschlossen sind.
LÖSUNGSVORSCHLAG:
Seien G = (VG,Σ, PG, SG), H = (VH ,Σ, PH , SH) Typ 0-Grammatiken, die auf der lin-
ken Seite ihrer Produktionen keine Terminale haben; ferner gibt es keine gemeinsamen
Nonterminale, also VG ∩ VH = ∅.
Dies ist trotzdem allgemein, da die Grammatiken in diese Form gebracht werden können:
Durch Umbenennung und durch Erzeugung von zusätzlichen Nonterminalsymbolen.
Sei ferner S ein frisches Nonterminal, also S 6∈ VG ∪ VH .
(VG∪VH∪{S},Σ, PG∪PH∪{S → SGSH}, S) ist eine Typ 0-Grammatik für die Sprache
L(G)L(H).
b) Zeigen Sie, dass Typ 1-Sprachen unter Vereinigung abgeschlossen sind.
LÖSUNGSVORSCHLAG:
Seien G = (VG,Σ, PG, SG), H = (VH ,Σ, PH , SH) Typ 1-Grammatiken, die auf der lin-
ken Seite ihrer Produktionen keine Terminale haben; ferner gibt es keine gemeinsamen
Nonterminale, also VG ∩ VH = ∅.
Dies ist trotzdem allgemein, da die Grammatiken in diese Form gebracht werden können:
Durch Umbenennung und durch Erzeugung von zusätzlichen Nonterminalsymbolen.
Sei ferner S ein frisches Nonterminal, also S 6∈ VG ∪ VH .
(VG ∪ VH ∪ {S},Σ, PG ∪ PH ∪ {S → SG | SH}, S) ist eine Typ 1-Grammatik für die
Sprache L(G)L(H).
Aufgabe 8 Reguläre Ausdrücke
a) Geben Sie einen regulären Ausdruck an, der alle grob wohlgeformten Worte der deut-
schen Sprache akzeptiert, d.h. alle Worte, welche alle der folgenden Eigenschaften erfüllen:
• Der erste Buchstabe ist ein Klein- oder Großbuchstabe.
• Alle weiteren Buchstaben sind Kleinbuchstaben.
• Das Wort enthält mindestens zwei Buchstaben.
• Alle Buchstaben entstammen dem normalen Alphabet (a-z bzw. A-Z), sind ein
Umlaut (ä, ö, ü bzw. Ä,Ö,Ü), oder ein ß; ß ist nicht der erste Buchstabe.
LÖSUNGSVORSCHLAG: (a | · · · | z | A | . . .Z | Ä | Ö | Ü | ä | ö | ü)(a | · · · | z | ä |
ö | ü | ß)(a | · · · | z | ä | ö | ü | ß)∗
b) Geben Sie einen regulären Ausdruck an, welcher korrekt geschriebene Datumsangaben
im JJJJ-MM-TT-Format akzeptiert
• Zum Beispiel ist 2019-02-01 der erste Februar im Jahr 2019.
• Es sollen beliebige 4-stellige Jahreszahlen erlaubt sein.
• Tage und Monate sollen zueinander passen, z.B. ist 2001-02-31 nicht erlaubt.
• Schaltjahr soll nicht überprüft werden, d.h. der 29-ste Februar ist immer zulässig.
LÖSUNGSVORSCHLAG:
Sei
• X1 := 0(1 | · · · | 9) | 1(0 | 1 | 2), der Ausdruck für alle Monate
• X2 := 0(1 | 3 | · · · | 9) | 1(0 | 1 | 2), der Ausdruck für alle Monate außer Februar
• X3 := 0(1 | 3 | 5 | 7 | 8) | 1(0 | 2), der Ausdruck für alle langen Monate
• X4 := (1 | 2)0 | (0 | 1 | 2)(1 | · · · | 9), der Ausdruck für die Tage im Monat
Damit setzt sich der Reguläre Ausdruck für das Datum zusammen als
(0 | · · · | 9)(0 | · · · | 9)(0 | · · · | 9)(0 | · · · | 9)− (X1 −X4 | X2 − 30 | X3 − 31)
Aufgabe 9 Pumping-Lemma
a) Zeigen Sie, dass die Sprache {anbn+mam | n,m ∈ N0} nicht regulär ist.
LÖSUNGSVORSCHLAG:
Für jedes k ∈ N>0 müssen wir ein ausreichend langes Wort finden, für das keine pum-
pende Zerlegung existiert.
Wir wählen z = akbk. In jeder Zerlegung uvw = z mit |uv| ≤ k bestehen u und v nur
aus dem Buchstaben a.
Damit ist uviw = ak+(i−1)·|v|bk. Dies ist nicht in {anbn+mam | n,m ∈ N0} für i 6= 1.
Damit erfüllt diese Sprache nicht die Pumpingeigenschaft, damit ist sie nicht regulär.
b) Zeigen Sie, dass für zwei Sprachen L und M , die beide die Pumpingeigenschaft erfüllen,
die Sprache LM ebenfalls die Pumpingeigenschaft erfüllt.
LÖSUNGSVORSCHLAG:
Zum Zeitpunkt der Aufgabenstellung war nur das Pumpinglemma regulärer Sprachen
bekannt, die Aufgabe meint also das Pumpinglemma regulärer Sprachen.
Pumpingeigenschaft: ∃n ∈ N>0∀z ∈M, |z| ≥ n∃u, v, w ∈ Σ∗(z = uvw ∧ |uv| ≤ n ∧ |v| ≥
1 ∧ ∀i ∈ N0.uviw ∈M)
Die Sprachen L und M haben so ein n, die sogenannte Pumpingzahl. Die Pumpingzahl
von L nennen wir nL, die Pumpingzahl von M nennen wir nM .
Wir wählen n = nL + nM als Pumpingzahl von LM .
Wir müssen zeigen, dass jedes z ∈ LM eine geeignete Zerlegung besitzt. Sei also z ∈ LM .
Damit gibt es nun s ∈ L und t ∈M mit z = st.
Fallunterscheidung
• |s| < nL: Da z ≥ nL + nM , ist t ≥ nM . Da t ∈M und M die Pumpingeigenschaft erfüllt, gibt es eine Zerlegung t = uvw mit |uv| ≤ nM ∧|v| ≥ 1∧∀i ∈ N0.uviw ∈M . Damit ist z = u′vw mit u′ = su eine geeignete Zerlegung von z, denn z = st = suvw = u′vw, |u′v| = |suv| = |s| + |uv| ≤ nL + |uv| ≤ nL + nM = n, |v| ≥ 1 gilt immernoch, ∀i ∈ N0.u′viw = suviw ∈ LM , denn s ∈ L und uviw ∈M , da dies die Zerlegung aus dem Pumpinglemma ist. • |s| ≥ nL: Da s ∈ L und L die Pumpingeigenschaft erfüllt, gibt es also eine Zerlegung s = uvw mit |uv| ≤ nL ∧ |v| ≥ 1 ∧ ∀i ∈ N.uviw ∈ L. Damit ist z = uvw′ mit w′ = wt eine geeignete Zerlegung von z, denn z = st = uvwt = uvw′, |uv| ≤ nL ≤ nL + nM = n, |v| ≥ 1 gilt immernoch, ∀i ∈ N0.uviw′ = uviwt ∈ LM , denn t ∈ M und uviw ∈ L, da dies die Zerle- gung aus dem Pumpinglemma ist. Aufgabe 10 Myhill-Nerode Geben Sie den Nerode-Index folgender Sprachen an und begründen Sie Ihre Antwort a) {aibici | i ∈ N>0} über dem Alphabet {a, b, c}
LÖSUNGSVORSCHLAG: [aibi] 6= [ajbj ] ⇐⇒ i 6= j, denn jedes [aibi] hat genau ein
Wort, welches dahinter gehängt werden darf, damit das entstehende Wort in der Sprache
liegt, nämlich ci; diese sind alle unterschiedlich, damit sind auch die Äquivalenzklassen
unterschiedlich. Damit sind dies alleine bereits unendlich viele Äquivalenzklassen, der
Nerode-Index ist also ∞.
b) {ai | i > 1000} über dem Alphabet {a, b, c}
LÖSUNGSVORSCHLAG:
Die Äquivalenzklassen sind [b], sowie [ai], i ∈ {0, . . . , 1001}.
[b] beinhaltet genau diejenigen Wörter, die nicht zu einem Wort in der Sprache erweitert
werden können; dies sind genau diejenigen Wörter, die ein b oder c enthalten. Jedes [ai]
kann mit a1000−i zu einem Wort erweitert werden, das nicht in der Sprache ist, aber mit
a1001−i zu einem Wort, das in der Sprache ist. [a1001] beinhaltet ebenfalls die Wörter
a1001a∗.
Damit sind die Äquivalenzklassen alle unterschiedlich und es sind insgesamt 1003 Äqui-
valenzklassen, der Nerode-Index ist also 1003.
Aufgabe 11 Formalismen für Reguläre Sprachen
Sei M die formale Sprache über dem Alphabet {0, 1}, die genau alle solchen Worte enthält,
die ungerade Binärzahlen ohne führende Nullen darstellen.
a) Geben Sie einen NFA A an, sodass L(A) = M gilt.
LÖSUNGSVORSCHLAG:
z0 z1
z2
1
1
1 0, 1
b) Geben Sie einen regulären Ausdruck α an, sodass L(α) = M gilt.
LÖSUNGSVORSCHLAG: 1 | 1(0 | 1)∗1
c) Geben Sie eine reguläre Grammatik G an, sodass L(G) = M gilt.
LÖSUNGSVORSCHLAG:
G = (V,Σ, P, S), wobei
• V = {S,A}
• Σ = {0, 1}
• P = {S → 1 | 1A,A→ 1 | 0A | 1A}
A0-1 Grammatiken
A0-2 Syntaxbaum
A0-3 Kleenescher Abschluss
A0-4 Grammatiken und Automaten
A0-5 Produktautomat
A0-6 Minimierung
A0-7 Abschlusseigenschaften
A0-8 Reguläre Ausdrücke
A0-9 Pumping-Lemma
A0-10 Myhill-Nerode
A0-11 Formalismen für Reguläre Sprachen