Pumping Lemma & Sprachen

Question

Aufgabe:
Wir sollen mit Hilfe des Pumping Lemma zeigen, dass die Sprache L nicht von endlichen Automaten erkennt werden kann.
L = {ww^(R) : w ∈ Σ*} (die Sprache der Palindrome)

Problem/Ansatz:
Hi,
ich verstehe die Aufageb nicht. Es gibt ja endlich viele palindrome. Dann wäre ja der Automat groß aber endlich. Mir fällt nichts anderes ein. Aber laut Aufgabenstellung kann die Sprache L nicht von einem endlichen Automaten erkannt werden.
Bin dankbar für jede Hilfe.

Answer 1

Es gibt ja endlich viele palindrome.

Sei w ein Palindrom.

Sei a ∈ Σ. Dann ist awa ein Palindrom mit |awa| > |w| .

Wie kommst du darauf, dass es nur endlich viele Palindrome gibt?

Comments

ah ok. Ich dachte es zählen nur ganze Worte also wie z.B. otto = otto. Ich habe nicht gedacht dass die palindrome nicht unbedingt echte Worte sein müssen, die auch ein Sinn ergeben. Danke

---

{ww^(R) : w ∈ Σ*}

Das ist maßgeblich, wenn es darum geht zu entscheiden ob ein Wort in der Sprache ist oder nicht.

(die Sprache der Palindrome)

Das ist eine zusätzliche Information, die der Autor angehängt hat, um die Aufgabe verständlicher zu machen oder um zu definieren, was ein Palindrom ist (nämlich ein Element von L).

Ich dachte es zählen nur ganze Worte
...
dass die palindrome nicht unbedingt echte Worte sein müssen

Ich weiß nicht, was du mit "ganze Worte" und mit "echte Worte" meinst. Hast du Definitionen parat, mit der man unterscheiden kann, ob eine Zeichenkette ein ganzes bzw. echtes Wort ist, oder nicht?