Warum ist {a^nb^n | n> = 0} nicht regelmäßig?

Question

In einem CS Kurs Ich nehme es ist ein Beispiel für eine Sprache, die nicht regulär ist:

{a^nb^n | n >= 0} 

kann ich verstehen, dass es nicht normal ist, da keine endlicher Automat/Maschine, das validates geschrieben werden und akzeptiert diese Eingabe, da keine Speicherkomponente vorhanden ist. (Bitte korrigieren Sie mich, wenn ich falsch liege)

Die wikipedia entry on Regular Language listet auch dieses Beispiel auf, bietet aber keinen (mathematischen) Beweis dafür, warum es nicht regelmäßig ist.

Kann mir jemand dazu aufklären und dafür einen Nachweis erbringen, oder mich auch auf eine gute Ressource hinweisen?

Answer 1

Was Sie suchen, ist Pumping lemma for regular languages. Hier

ist ein example mit Ihren genauen Problem:

Beispiele:
Sei L = {a ^m b ^m | m ≥ 1}.
Dann ist L nicht regulär.
Beweis: Sei n wie im Pumping Lemma.
Es sei w = a ⁿ b ⁿ.
Sei w = xyz wie im Pumping Lemma.
Also xy z ∈ L jedoch xy z enthält mehr a's als b's.

Answer 2

Weil Sie keine endliche Automaten schreiben können, die identische Folgen von 'a' und 'b' Symbolen 'zählen'. Kurz gesagt, FSMs können nicht "zählen". Versuchen Sie sich eine solche FSM vorzustellen: Wie viele Zustände würden Sie dem Symbol "a" geben? Wie viele zu "b"? Was ist, wenn Ihre Eingabefolge mehr hat?

Beachten Sie, dass, wenn Sie n < = X mit X einen ganzzahligen Wert hätten, Sie solche FSM vorbereiten könnten (indem Sie eine mit vielen Zuständen, aber immer noch eine endliche Zahl haben); Eine solche Sprache wäre regelmäßig.

Answer 3

Finite State Automaton hat keine Datenstruktur (Stack) - Speicher wie im Falle eines Push-Down-Automaten. Ja, es kann dir ein 'a' geben, gefolgt von einigen 'b' s, aber nicht genau 'a', gefolgt von 'no b'.