Informatik: Pumping Lemma für reguläre Sprachen (Palindrom)

Question

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:

w_L = aⁿ bⁿ c bⁿ aⁿ (Hier hätte auch aⁿ c aⁿ funktioniert, oder?)

wende die Eigenschaften des Pumping Lemmas an:

w_P=uvw

u = a^n-1

v = a

w = bⁿ c bⁿ aⁿ 

Nun wird v gepumpt mit dem Pumpfaktor y∈ℕ

w_{P =} a^n-1 a^y  bⁿ c bⁿ aⁿ

Damit ist w_P nicht in W_L enthalten.

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

Answer 1

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.