Theoretische Informatik (Vorlesung 6)

2.3) Pumping-Lemma

• Sei Σ ein Alphabet
• L ∈ Σ* eine Sprache
• Wortproblem L
  • Gegeben: w ∈ Σ*
  • Frage: Gilt w ∈ L?
• Fragen:
  • Für durch DEAs gegebene Sprachen einfach: δ*(q₀, w) ∈ F ?
  • Gibt es Sprachen, die nicht von einem DEA akzeptiert werden?
  • Wie zeigt man, dass eine Sprache von keinem DEA akzeptiert wird?
• Beispiel:
  • Q = { q₀,q₁,q₂}
  • Anfangszustand = q₀
  • F = {q₂} (Endzustände)
  • = A
  • L(A) = { w ∈ Σ*, δ(δ₀,w) ∈ F } = { w ∈ { 0,1}* w hat mehr als eine Null und die Anzahl der Nullen ist gerade }

ε (leeres Wort)	0	1	1	0	0	0
q0	q1	q1	q1	q2	q1	q2	∈ F

• Der Graph muss manche Zustände öfters besuchen, wenn ein Wort eine Länge hat, die größer ist als die Anzahl der Zustände. Es bilden sich dabei also Schleifen (rot markiert zur Hervorhebung).
• Theoretisch lassen sich die Teilabschnitte der Zustände in Bereiche mit Schleifen zusammenfassen lassen: x y z, es wäre z.B. auch x y² z oder x y⁴ z auch ein gültiges Wort der Sprache.
• Definition 2.10 ( Pumping Lemma)
  • Sei L eine von einem DEA akzeptierte Sprache.
  • Dann existiert n₀ ∈ ℕ so, dass gilt: Jedes Wort w ∈ L mit |w| ≥ n₀ lässt sich zerlegen in x y z mit:
    1. y ≠ ε (leeres Wort) und
    2. x y^k z ∈ L für alle k ∈ N

• Beispiel: Die Sprache L = {  aⁿ bⁿ; n ∈ ℕ₀ } wird von keinem DEA akzeptiert.
• Beweis: Angenommen, L wird von einem DEA azeptiert ( Widerspruch herleiten ). Dann existiert nach dem Pumping-Lemma eine natürliche Zahl n₀ ∈ ℕ so, dass für alle w ∈ L mit |w| ≥ n₀ ( Mehr Buchstaben als Zustände) eine Zerlegung xyz mit …
  1. y ≠ ε (leeres Wort)
  2. x y^k z ∈ L für alle k ∈ ℕ … existiert

• Sei w ∈ L mit |w| ≥ n₀, dann gilt w = aⁿ bⁿ mit 2n ≥ n₀.
• Sei weiter x y z = w eine Zerlegung von w mit y ≠ ε (leeres Wort)
• Ziel: Zeige  ( x y² z ∉ L ) Dann ist das Pumping-Lemma nicht erfüllt und wir haben einen Widerspruch zur Voraussetzung ( = „L wird von einem DEA akzeptiert“ )
• Fallunterscheidung: 
  1. Fall: y liegt ganz in aⁿ
  2. Fall: y liegt ganz in bⁿ
  3. Fall: y hat sowohl a’s als auch b’s
• zu 1: Dann existieren n₁+n₂+n₃ mit x=a^n₁, y=a^n₂, z=a^n₃*bⁿ und n₁+n₂+n₃ = n. Laut Pumping Lemma gilt dann auch x y² z ∈ L. Da x y² z = a^n₁ * a^2n₂ * a^n₃bⁿ. Da n₁+2*n₂+n₃ > n, ist das ein Widerspruch.

( w = aa…ab …..b // aⁿ = x, z=bⁿ –> y kann in x, z oder in beiden liegen )

2.4 Abschlusseigenschaften

• Definition 2.11: 
  • Seien L₁ und L₂Sprachen über dem Alphabet Σ, die jeweils von einem DEA akzeptiert werden. Dann werden auch die folgenden Sprachen akzeptiert:
  • L₁ ∪ L₂
  • ¬L₁ = { w ∈ Σ*; w ∉ L₁ }
  • L₁ ∩ L₂
  • L₁ \ L₂
  • L₁ * L₂ = { w₁w₂; w₁ ∈ L₁ und w₂ ∈ L₂ } 

• Beweise:
  1. 1 & 5 kommen später
  2. Sei A = ( Q, Σ, q₀, δ, F ) ein DEA für L₁ (d.h. die von A akzeptierte Sprache ist L₁ ↔ L(A) = L₁ ) Dann akzeptiert ¬A = (Q, Σ, q₀, δ, Q\F ) die Sprache ¬L₁.
     1. L (¬A) = { w ∈ Σ*; δ* (q₀, w) ∈ Q\F } ist das Gegenteil von L(A) = { w ∈ Σ*; δ* (q₀, w) ∈ F }
  3. 3 zeigen wir gleich
  4. L₁ \ L₂ = L₁ ∩ ¬L₂
• Aufgabe:
  • Seien L₁ und L₂ jeweils von den DEA A₁=(Q₁, Σ, q₀¹,d₁,F₁) und A₂ = (Q₂, Σ, q₀², δ₂, F₂) akzeptiert.
  • Ziel: Konstruktion eines DEAs für L₁ ∩ L₂
• Beispiel:
  • L = { w ∈ {0,1}*; w hat gerade viele Nullen und gerade viele Einsen }
  • L₁ = { w ∈  { 0,1 }*; w hat gerade viele Nullen }
  • L₂ = { w ∈ {0,1}*; w hat gerade viele Einsen}
  • L=L₁ ∩ L₂

• Wir definieren den sog. Produkautomaten:
  •  A=(Q₁xQ₂, Σ, (q₀¹, q₀²), δ, F₁xF₂).
  • d: (Q₁xQ₂) x Σ → (Q₁xQ₂); ((q,p)a) → (d1, (q,a), δ2(q,a))
  • Q₁xQ₂ = { (q,z); q ∈ Q₁, z ∈ Q₂ }
• Im Beispiel:
  • Q₁xQ₂= {(q₀,z₀), (q₀,z₁) , (q₁,z₀), (q₁,z₁) }
  • F₁xF₂ = { q₀ } x { z₀ } = { (q₀,z₀)}
  • δ((q₀,z₀),0) = (δ1, (q₀,0), δ2(z₀, 0)) → q_1, z₀
  • δ((q₀,z₀),1) = (δ1, (q₀,1), δ2(z₀, 1)) → q₀, z₁

Erläuterung: „Man verknüpft jeden Zustand aus Q1 mit jedem Zustand aus Q2 und setzt dann in die kombinierten Zustände die Buchstaben des Wortes ein. Man führt die Übergangsfunktion für die einzelnen Teile wie gewohnt mit dem Buchstaben aus, aber überführt dann aber wieder in den gemeinsamen Zustand“.

L₁ ∩ L₂

Bsp.:

• L₁= { aⁿ b^m; n,m ∈ ℕ und n ≠ m } → nein
• L₂ =  { aⁿ bⁿ; n ∈ ℕ } → nein
• L₃ = { aⁿ b^m; n, m ∈ ℕ } → ja
• ¬L₁ = L₂ 

3) Produktautomaten

• Sei A₁ = ( Q₁, Σ, q₀¹, δ₁, F₁) ein DEA für L₁
• Sei A₂ = (Q₂, Σ, q₀², δ₂, F₂) ein DEA für L₂
• Produktautomat : A=(Q₁xQ₂, Σ, (q₀¹, q₀²) δ, F₁xF₂)