Beweisschablone

Grundlagen der Theoretischen Informatik
Beweisschablone
zur Anwendung des Pumping Lemmas für reguläre Sprachen
zur Vorlesung von Prof. Dr. Till Mossakowski
im Wintersemester 2014
Die Schablone
Behauptung. Die Sprache L = nichtreguläre Sprache ist nicht regulär.
Beweis. Angenommen L wäre regulär.
Dann gäbe es, laut dem Pumping Lemma für reguläre Sprachen, eine Zahl n ∈ N so dass für alle Wörter
w ∈ L mit Länge |w | ≥ n eine Zerlegung w = xyz existieren würde für die gilt
(1)
|xy| ≤ n
(2) y , ϵ
(3)
xy i z ∈ L für alle i ∈ N0 .
Wir betrachten nun das Wort w = clever gewähltes Wort . Da w ein Wort aus L ist1 das mit |w | =
Länge von w ≥ n lang genug ist, gäbe es also eine Zerlegung w = xyz mit (1), (2) und (3).
*
+
Beobachtungen darüber wie jede Zerlegung von w
mit Eigenschaften (1) und (2) aussehen muss.
Damit haben x, y und z die Form
*
+
Zusammenfassung der obigen Beobachtungen2 , etwa
x = ..., y = ..., z = ...
(F)
Nach Eigenschaft (3) müsste nun gelten, dass xy i z ∈ L für alle i ∈ N0 , aber für i = hˆı i beobachten wir
D
E
w 0 = xy hˆı iz = expandieren von xy hˆı iz mittels (F) < L ,
D
E
denn Begründung warum w 0 = xy hˆı iz nicht in L liegen kann . Dies ist ein Widerspruch!
Folglich war unsere Annahme falsch und L ist nicht regulär.
1 Dies
2 Hier
ist bei komplizierteren Sprachen zu begründen.
kann, je nach Sprache, eine Fallunterscheidung notwendig sein.
Ein Beispiel
Behauptung. Die Sprache L = {ak b k | k ≥ 0} ist nicht regulär.
Beweis. Angenommen L wäre regulär.
Dann gäbe es, laut dem Pumping Lemma für reguläre Sprachen, eine Zahl n ∈ N so dass für alle Wörter
w ∈ L mit Länge |w | ≥ n eine Zerlegung w = xyz existieren würde für die gilt
(1)
|xy| ≤ n
(2) y , ϵ
(3)
xy i z ∈ L für alle i ∈ N0 .
Wir betrachten nun das Wort w = an b n . Da w ein Wort aus L ist das mit |w | = 2n ≥ n lang genug ist,
gäbe es also eine Zerlegung w = xyz mit den Eigenschaften (1), (2) und (3).
• Weil w mit xy beginnt, weil |xy| ≤ n und weil w mit an beginnt, enthält xy und somit y nur as.
• Wegen y , ϵ, besteht y folglich aus mindestens einem a.
Damit haben x, y und z die Form
x = ar
y = as
z = an−r −s b n
für r + s ≤ n mit s ≥ 1 (wegen y , ϵ) .
Nach Eigenschaft (3) müsste nun gelten, dass xy i z ∈ L für alle i ∈ N0 , aber für i = 2 beobachten wir
w 0 = xy 2z = ar a 2·s an−r −s b n = an+s b n < L ,
denn w 0 = xy 2z hat, anders als die Wörter in L, mehr as als bs. Dies ist ein Widerspruch!
Folglich war unsere Annahme falsch und L ist nicht regulär.
Tipps & Hinweise
• Verwende bei der Wahl des Wortes w so wenige Buchstaben wie möglich.
• Versuche w so zu wählen, dass Buchstabengruppen als Vielfache von n auftreten.
• Beachte wo wir Wahlfreiheit haben und wo nicht:
– Die Zahl n wird durch das Pumping Lemma gegeben.
– Wir wählen ein Wort w ∈ L mit |w | ≥ n.
– Durch das Pumping Lemma ist eine Zerlegung w = xyz mit (1), (2) und (3) gegeben.
– Wir wählen ein i so dass w 0 = xy i z < L ist.
• Da wir uns die Zerlegung nicht aussuchen können, müssen wir bei (F) eine Beschreibung von
x, y und z finden, die für alle Zerlegungen von w mit (1) und (2) zutrifft.

Download Report