0 Daumen
56 Aufrufe

Gegeben ist folgende Sprache, anhand desser mit dem Pumping Lemma gezeigt werden soll, dass sie nicht regulär ist.


\( L = \{ a^{k + l}b^k |k,l \in \mathbb{N}_0 \}\)


Ich habe leider nicht verstanden, wie man die Sprache korrekt in Präfix, pumpbaren Infix und Suffix aufteilen soll, um das Pumping Lemma zu widerlegen .

von

1 Antwort

0 Daumen

Man teilt die Sprache nicht in Präfix, Infix und Suffix auf.

Man sucht sich ein Wort \(w\in L\) aus und teilt dieses in Präfix, Infix und Suffix auf.

Wichtig dabei: es genügt, sich ein einziges Wort auszusuchen, aber du musst für alle möglichen Aufteilungen \(w = xyz\) nachweisen, dass sie nicht die Forderungen des Pumping Lemmas erfüllen.

Sei dazu \(p\in \mathbb{N}\). Das soll die Pumping-Zahl sein.

Jetzt begibt man sich aus die Suche nach einem geeigneten \(w\).

\( L = \{ a^{k + l}b^k |k,l \in \mathbb{N}_0 \}\)

Mache dir klar, was das anschaulich bedeutet.

Dann siehst du, dass man \(w\) so wählen muss, dass man gezwungen ist

  • mehr \(b\) als \(a\) aufzupumpen oder
  • mehr \(a\) als \(b\) abzupumpen

Beispiel. Sei \(w = aab\). Bei \(p=3\) kann man dann \(y = ab\) wählen. Leider ist \(a(ab)^n\in L\), aufpumpen führt also nicht dazu, dass man aus \(L\) rausfällt. Auch abpumpen bringt nicht, weil \(a\in L\) ist. Also ist die Wahl \(w = aab\) ungeeignet.

Suche ein besser geeignetes \(w\).

Tipp. Für \(p = 2\) wäre \(w=aab\) geeignet, weil dann wegen \(|xy|\leq p\) die Wahl \(y = ab\) nicht zulässig wäre. Das Wort \(w\) hängt also von \(p\) ab.

von 3,5 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community