+1 Daumen
3k Aufrufe

Guten Tag,

ich soll mit Hilfe des Pumping Lemma beweisen, dass die folgende Sprache L nicht regulär ist.

L={w | w ∈ {a,b,c}*, w ist ein Palindrom}

Ich habe eine Lösung, bin mir aber nicht sicher ob diese so stimmt:

Ich betrachte folgendes Wort aus dieser Sprache:

wL = an bn ban (Hier hätte auch aan funktioniert, oder?)

wende die Eigenschaften des Pumping Lemmas an:

wP=uvw

u = an-1

v = a

w = bba

Nun wird v gepumpt mit dem Pumpfaktor y∈ℕ

wP = an-1 ay  bban

Damit ist wP nicht in WL enthalten.

Stimmt das so, oder hätte ich das auch anders machen können/müssen?

Avatar von

1 Antwort

0 Daumen

Antwort vom Fragensteller:

Wir haben heute glücklicherweise diese Aufgabe mit dem Prof. durchgesprochen.

So wie ich das gemacht habe, ist es nicht ganz richtig, da der Widerspruchsbeweis nur allgemein gültig sein muss und nur der Pumpfaktor variabel gewählt werden darf.

Richtig sieht es so aus:

Anmerkung: Ich nehme nun die vereinfachte Form \(w=a^n c a^n \)
Es wird für u und v nur das erste an betrachtet, also sind u und v:

\(u = a^r\)  für 0 ≤ r≤ n-1 
\(v = a^s\)  für 1 ≤ s ≤ n 
\(w = a^{tc}\) an  für 0 ≤ t < n   
\(a^t\) wird benötigt, da noch weitere a's folgen können, aber nicht müssen. 
 
Die Bedingung |uv| ≤ n ist dennoch erfüllt.
Das Wort sieht demnach so aus:

\(w^p = a^r a^p a^{tc}a^n\)

Wenn man jetzt z.B. für den Pumpfaktor p=2 einsetzt, ist es bewiesen, dass die Sprache L nicht regulär ist.
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community