Lösungen zum Aufgabenblatt 2 Formale Sprachen und Automaten

Lösungen zum Aufgabenblatt 2
Formale Sprachen und Automaten
Universität München, CIS, WS 2015/16
Hans Leiß
Ausgabe: Do 29.10.2015
Abgabe: Do 5.11.2015
Aufgabe 2.1 Sei Σ = {a, b, c}. Konstruiere zur Sprache
L = {abc, abb, acc, bac, cac, acb, bab, cab}.
das Monoid Σ∗ /≡L der Synonymieklassen von L. (Was enthalten die verschiedenen [v]≡L und
wie lautet die Multiplikationstabelle“ der Verkettung [v]≡L · [u]≡L ?)
(8 Punkte)
”
Lösung von Aufgabe 2.1 Da für alle v1 , v2 ∈ Σ∗
[v1 ]≡L = [v2 ]≡L ⇐⇒ DL (v1 ) = DL (v2 )
ist, gibt es genausoviele Synonymieklassen wie Distributionsklassen. Für alle w ∈ Σ∗ , die in
keinem Wort von L als Teilwort vorkommen, ist DL (w) = ∅ und daher
[w]≡L = { v ∈ Σ∗ | v kommt in keinem Wort von L als Teilwort vor }.
Wir berechnen für die übrigen Wörter, der Länge nach, ihre Distributionsklassen, indem wir die
Kontexte der Vorkommen (von links nach rechts in der Wortliste von L oben) sammeln, und
erhalten:
DL (ǫ) = {(ε, abc), (a, bc), (ab, c), (abc, ε), . . . , (ε, cab), (c, ab), (ca, b), (cab, ε)}
DL (a) = {(ε, bc), (ε, bb), (ε, cc), (b, c), (c, c), (ε, cb), (b, b), (c, b)}
DL (b) = {(a, c), (a, b), (ab, ǫ), (ǫ, ac), (ac, ǫ), (ǫ, ab), (ba, ǫ), (ca, ǫ)},
DL (c) = {(a, c), (a, b), (ab, ǫ), (ǫ, ac), (ac, ǫ), (ǫ, ab), (ba, ǫ), (ca, ǫ)},
DL (aa) = ∅
DL (ab) = {(ε, c), (ε, b), (b, ε), (c, ε)}
DL (ac) = {(ε, c), (b, ε), (c, ε), (ε, b)}
DL (ba) = {(ε, c), (ε, b)}
DL (bb) = {(a, ε)}
DL (bc) = {(a, ε)}
1
DL (ca) = {(ε, c), (ε, b)}
DL (cb) = {(a, ε)}
DL (cc) = {(a, ε)}
DL (w) = {(ε, ε)} für alle w ∈ L, da keines Teilwort eines anderen ist.
Man sieht an den Gleichheiten hierin, daß es 8 Synonymieklassen [v] := [v]≡L von L gibt:
[ε] = {ε},
[a] = {a},
[b] = {b, c},
[ab] = {ab, ac},
[ba] = {ba, ca},
[bb] = {bb, bc, cb, cc},
[abc] = L,
[aa] = { v ∈ Σ∗ | v kommt in keinem Wort von L als Teilwort vor }.
Die Operation · auf den Klassen ist daran ablesbar, z.B.
[a] · [b] = [ab],
[ab] · [ba] = [abba] = [aa].
Insgesamt erhält man folgende Multiplikationstabelle“:
”
·
[ε] [a] [b] [ab] [ba]
[ε]
[ε] [a] [b] [ab] [ba]
[a] [a] [aa] [ab] [aa] [aa]
[b]
[b] [ba] [bb] L [aa]
[ab] [ab] [aa] L [aa] [aa]
[ba] [ba] [aa] L [aa] [aa]
[bb] [bb] [aa] [aa] [aa] [aa]
L
L [aa] [aa] [aa] [aa]
[aa] [aa] [aa] [aa] [aa] [aa]
[v]
[bb]
[bb]
L
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
L
L
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
[aa]
[w]
[v] · [w]
Das Beispiel ist etwas einfach, da alle Wörter von L gleiche Länge haben und daher kein Wort
von L in einem anderen vorkommt.
Aufgabe 2.2 Sei t = a1 · · · an ∈ Σ∗ ein Text der Länge |t| = n > 0 (mit a1 , . . . , an ∈ Σ),
M = {0, . . . , n} die Menge der Positionen in t, T ok(t) = { (i, ai+1 · · · aj , j) | 0 ≤ i ≤ j ≤ n } die
Menge der Wortvorkommen in t.
Zeige, daß die Abbildung h : P(T ok(t)) → P(M × M ) mit
h(A) := { (i, j) | v ∈ Σ∗ , 0 ≤ i ≤ j ≤ n, (i, v, j) ∈ A }
ein injektiver Homomorphismus vom Monoid P(T ok(t)) der Tokenmengen von t in das Monoid
der zweistelligen Relationen zwischen Positionen in t ist.
Gib eine Relation R ⊆ M × M an, die nicht im Bild von h vorkommt, also kein h(A) mit
A ⊆ T ok(t) ist.
(4 Punkte)
2
Aufgabe 2.3 (vgl.Vorlesungsfolien) Sei Σ das Alphabet der deutschen Wörter, die mit einem
Leerzeichen (statt ·) verkettet werden. Jedes Wort w liefert eine Wortmenge, L(w) := {w}. Was
ist L(das) · L(T ier) im Monoid P(Σ∗ ) aller Wortmengen?
Sei t der Text das Tier frißt das Tier“ über dem Alphabet Σ, und T (w) die Tokenmenge des
”
Worts w in t, z.B.
T (das) = {(0, das, 1), (3, das, 4)}.
Was ist T (das) · T (T ier) im Monoid Tok(t) aller Tokenmengen von t? Wie viele Elemente hat
P(Σ∗ ), wieviele P(Tok(t))?
(2 Punkte)
Lösung von Aufgabe 2.3 Na ja, L(das) · L(T ier) ist natürlich
L(das) · L(Tier ) = {das} · {Tier } = {das Tier }.
In der Algebra der Tokenmengen über dem Text t ist
T (das) · T (Tier ) = {(0, das, 1), (3, das, 4)} · {(1, Tier , 2), (4, Tier , 5)}
= {(0, das Tier , 2), (3, das Tier , 5)}.
Im allgemeinen ist |P(Σ∗ )| = ∞, aber P(Tok(t)) = 2|Tok (t)| endlich – das werden wir bei der
Syntaxanalyse ausnutzen. Für einzelne w ∈ Σ∗ ist |L(w)| = 1, aber |T (w)| ist die Anzahl der
Vorkommen von w in t, was kleiner, gleich, oder größer als |L(w)| sein kann.
3

Download Report