Übungen zu Formalen Sprachen und Automaten

Aufgabe 1: Operationen auf Sprachen

Sei L eine Sprache, e das leere Wort und u, v zwei Wörter in L.

a) Was ist {e}L?

Antwort: {e}L = L.
Begründung: Die Konkatenation des leeren Wortes e mit einem beliebigen Wort w aus L ergibt wieder w. Formal: {e ∘ w : w ∈ L} = L.

b) Mächtigkeit von {u, v}L

Was ist die Mächtigkeit von {u, v}L, d.h. |{u, v}L|?
Antwort: |L| ≤ |{u, v}L| ≤ 2 × |L|.
Begründung: Die Mächtigkeit hängt davon ab, wie viele Wörter durch die Konkatenation identisch werden. Beispiel: {a, e} ∘ {a, aa, aaa} = {aa, aaa, aaaa, a, aa, aaa} = {a, aa, aaa, aaaa}, was eine Mächtigkeit von 4 ergibt.

c) Bedingung für Regularität

Unter welcher Bedingung ist die Sprache in a) regulär?
Antwort: {e} ∘ L ist regulär genau dann, wenn L regulär ist, da {e}L = L gilt.

Aufgabe 2: Reguläre Sprachen und Automaten

Seien L0, L1 die folgenden regulären Sprachen:
L0 = 01* ∪ 1*
L1 = {0,1}* – L0 = {w : w ∈ {0,1}* und w ∉ L0}

b) Komplementautomat und regulärer Ausdruck

Ein Komplementautomat tauscht Zustände und Endzustände.
Regulärer Ausdruck (RA): (0 ∪ 1)1*0(0 ∪ 1)*

c) Zustandsübergangsberechnung

R(1,2,2) = R(1,2,1) ∪ R(1,1,1) R(1,1,1)* R(1,2,1)
Allgemeine Formel: R(i,j,k+1) = R(i,j,k) ∪ R(i,k,k) R(k,k,k)* R(k,j,k)

{0,1} ∪ {e} ∘ {e}* ∘ {0,1} = {0,1}

Aufgabe 3: Kontextfreie Grammatik

Gib eine kontextfreie Grammatik G für L = { a^mbⁿc^p | n > m+p } an.

Grammatikregeln:
S → ABC
A → aAb | ε
B → bB | b
C → bCc | ε

Wortableitung

{w ∈ L : |w| ≤ 3} = {b, bb, bbb}

Ableitung von "bbb":
S → ABC → BC (da A → ε)
BC → bBC → bbBC → bbbC → bbb (da C → ε)

Aufgabe 1 (Teil 2): Parsing und Kellerautomaten

Betrachte die kontextfreie Grammatik G für L = { a^mbⁿc^p | n > m+p } aus der 1. Probeklausur.
(G = (V, Σ, R, S) mit V = {S, A, B, C, a, b, c}, Σ = {a, b, c} und R = {S → ABC, A → aAb, A → ε, B → bB, B → b, C → bCc, C → ε})

a) Bottom-up Parsing

Eignet sich G für Bottom-up Parsing? Nein, sie ist nicht bottom-up tauglich wegen der ε-Regeln.

b) Top-down Parsing

Eignet sich G für Top-down Parsing? Ja, sie ist top-down tauglich, da keine linksrekursiven Regeln vorliegen.

c) Top-down Kellerautomat

Gib den top-down Kellerautomaten zu G' an!
M = {K, Σ, Γ, Δ, s, F} mit K = {s, f}, F = {f}, Σ = {a, b, c}, Γ = {Σ ∪ {S, A, B, C}}

Übergangsrelation Δ:

• ((s, ε, ε), (f, s))
• ((f, ε, s), (f, ABC))
• ((f, ε, A), (f, aAb))
• ((f, ε, A), (f, ε))
• ((f, ε, B), (f, bB))
• ((f, ε, B), (f, b))
• ((f, ε, C), (f, bCc))
• ((f, ε, C), (f, ε))
• ((f, a, a), (f, ε))
• ((f, b, b), (f, ε))
• ((f, c, c), (f, ε))

Beispielkonfiguration (abbbc):
(s, abbbc, ε) ⊢ (f, abbbc, s) ⊢ (f, abbbc, ABC) ⊢ (f, abbbc, aAbBC) ⊢ (f, bbbc, AbBC) ⊢ (f, bbbc, bBC) ⊢ (f, bbc, BC) ⊢ (f, bbc, bC) ⊢ (f, bc, C) ⊢ (f, bc, bCc) ⊢ (f, c, Cc) ⊢ (f, c, c) ⊢ (f, ε, ε)

Aufgabe 2 (Teil 2): Deterministisch kontextfreie Sprachen

Zeige, dass diese Sprachen deterministisch kontextfrei (d.k.f.) sind.

a) Sprache {a^mbⁿ : m ≠ n}

Diese Sprache ist d.k.f. Die Sprache {aⁿbⁿ : n ≥ 0} ist ebenfalls d.k.f. und bildet eine Teilmenge von L1. Es gilt: {aⁿbⁿ : n ≥ 0} ∩ a*b* = L1.

b) Sprache {a^mcb^m : m ≥ 0} ∪ {a^mdb^2m : m ≥ 0}

M = {K, Σ, Γ, Δ, s, F} mit K = {s, p, q, f}, F = {f}, Σ = {a, b, $, c, d}, Γ = {b}

Übergänge:

• ((s, a, ε), (s, bb))
• ((s, c, ε), (p, ε))
• ((s, d, ε), (p, ε))
• ((p, b, bb), (q, ε))
• ((q, b, b), (q, ε))
• ((p, $, ε), (f, ε))
• ((q, $, ε), (f, ε))

Abschlusseigenschaften von Sprachklassen

Reguläre Sprachen

Die regulären Sprachen sind abgeschlossen unter:

• a) Vereinigung
• b) Konkatenation
• c) Kleene’scher Hüllenbildung
• d) Komplementbildung
• e) Schnittbildung

Kontextfreie Sprachen

Die Klasse der kontextfreien Sprachen ist abgeschlossen unter:

• a) Vereinigung
• b) Konkatenation
• c) Kleene’scher Hüllenbildung