1. Welt
  2. Quests
  3. #1446
Alexander Fufaev

Sprache (gleich viele a's und b's) ist nicht regulär

aus dem Bereich: Quests
Mehr dazu

Deine Aufgabe ist...

Gegeben ist die folgende Sprache: \[ L = \{ a^n \, b^n ~:~ n \geq 0 \} \]

Zeige, dass \(L\) nicht regulär (keine Typ-3-Sprache) ist.

Lösungstipps

Benutze das negierte Pumping-Lemma für reguläre Sprachen.

Lösung anzeigen Pumping-Lemma (negiert)
\(L\) ist nicht regulär genau dann, wenn:

\(\forall ~ n \in \mathbb{N}\) gilt:
 \(\forall ~ w \in L\) mit \( |w| \geq n \):
  \(\exists ~ w = x\,y\,z\) mit \(|y|\geq1\) und \(|x\,y|\leq n \):
    \(\exists ~i \in \mathbb{N}\) sodass \(x\,y^i z ~\notin~ L\).

Gehe das Pumping-Lemma Schritt für Schritt durch. Dieses sagt in der ersten Zeile "\(\forall ~ n \in \mathbb{N}\) gilt". Also wird ein beliebiges \(n\) genommen.

(1) Sei \(n \in \mathbb{N}\) gegeben.

Die nächste Zeile des Pumping-Lemmas verlangt, dass ein beliebiges Wort \(w\) aus der Sprache \(L\) betrachtet wird, dessen Länge \(|w|\) größer ist als das gewählte \(n\). Die gegebene Sprache \(L\) ist von der Form \(a^n \, b^n\), wähle also \(w = a^n \, b^n \) als Wort, denn dieses erfüllt die vom Pumping-Lemma verlangte Bedingung \(|w| = 2n \geq n\). Also:

(2) Setze \(w = a^n \, b^n \), wobei \(|w| \geq n\) erfüllt ist.

Die dritte Zeile des Pumping-Lemmas sagt nun aus, dass es eine Zerlegung \(x\,y\,z\) des gewählten Worts \(w\) gibt und zwar so, dass der mittlere Teil \(y\) nicht leer ist: \(|y|\geq 1\) und der Wortteil \(x\,y\) kürzer ist als \(n\): \(|x\,y|\leq n\). Also:

(3) Zerlege nun folgendermaßen das gewählte Wort: \( w = a^n \, b^n = x\,y\,z\), mit \(|y|\geq 1\) und \(|x\,y|\leq n\). Da \(|a^n| = n \), aber \(|x\,y|\leq n\) gilt, besteht der Wortteil \(x\,y\) nur aus \(a\) Buchstaben.

In der letzten Zeile sagt das Pumping-Lemma, dass für diese Form der Zerlegung ein \(i \in \mathbb{N}\) existiert, sodass \(x\,y^i z\) nicht in der betrachteten Sprache ist. Finde dafür das passende \(i\) und begründe, warum das Wort dann nicht in der Sprache ist.

(4) Setze \( i = 2\). Dann ist die Zerlegung \( a^n \, b^n = x\,y^2 \, z \) nicht in der Sprache \(L\), weil: \[ |x\,y^2 \, z|_a = |(x\,y)\,y\,z|_a = |a^n \, a^k \, b^n|_a ~\neq~ |a^n \, a^k \, b^n|_b \] mit \(k \geq 1 \) (wegen \(|y|\geq 1\)). Das heißt: \( x\,y^2 \, z \) hat (\(n+k\))-mal \(a\)-Buchstaben und nur \(n\)-mal \(b\)-Buchstaben. Alle Wörter der Sprache \(L\) bestehen aber aus gleich vielen \(a\)'s und \(b\)'s.

(5) Damit ist \(L\) nicht regulär.

Weltkarte
Verwalten
Profil
Die Stimme fragt...
Wie erlange ich den Zugang?

Um das Portal von Ak'tazun betreten zu können, musst Du die rote Pille schlucken. Nachdem Du durch das Portal gegangen bist, gelangst Du in die Matrix, wo Du beispielsweise folgendes tun kannst:

  • Inhalte hinzufügen & verwalten
  • Illustrationen ohne Copyrightzeichen herunterladen
  • Einige Inhalte kommentieren
  • Mittels Kommunikator RT2000 chatten
  • Telegram-Gruppe beitreten
Bist Du dabei?
Ja, bin dabei!
Portale in die anderen Welten

Reise zu den sicheren anderen Welten des Internets, um nach dem Wissen zu suchen. Findest Du eine Welt besonders interessant, dann kannst Du in der Universaldenkerwelt ein Portal zu dieser Welt erbauen, um den anderen Besuchern den schnellen Zugang dazu zu gewährleisten.

Portalraum betreten
Kommunikator
ONLINE 2
Gäste online: 2
Denker online: 0
Der Kommunikator RT2000 funktioniert nur innerhalb der Matrix!
Ich will in die Matrix!Mayday! Kontakt aufnehmen.