Ist L = {a^n b^m | n> m} eine normale oder irreguläre Sprache?

Question

Ich habe Probleme bei der Lösung dieses Problems. Irgendwelche Ideen bitte?

Answer 1

L = {a n b m | n> m} ist nicht reguläre Sprache.

Ja, das Problem ist schwierig bei ersten Versuch und verdient Abstimmung-up.

Pumping Lemma eine notwendige Eigenschaft der regulären Sprache ist Werkzeug für den formalen Beweis, dass Sprache keine reguläre Sprache ist.

formale Definition: Pumping lemma for regular languages

Lassen L eine reguläre Sprache sein. Dann gibt es eine ganze Zahl p ≥ 1 nur in Abhängigkeit von L so dass jede Zeichenfolgew in L der Länge mindestens p (p die "Pumplänge" genannt wird) kann sein geschrieben, wie w =xyz (dh w kann in drei Teilketten unterteilt werden), die folgenden Bedingungen erfüllen:

1. | y | ≥ 1
2. | xy | ≤ p
3. für alle i ≥ 0, xy ⁱ z ∈ L

Angenommen, wenn Sie Zeichenfolge wählen W = a ⁿ b ^m wo (n + m) ≥ p und n > m + 1. Wahl der W ist gültig, aber diese Wahl können Sie nicht zeigen, dass Sprache ist nicht reguläre Sprache. Denn mit dieser W immer Sie at-dest eine Auswahl von y=a müssen neue Saiten in Sprache pumpen von a für alle Werte von iWiederholung (für i = 0 und i> 1) .

Bevor ich meine Lösung zum Beweis schreibe, ist die Sprache nicht regelmäßig.Bitte haben Sie Verständnis für folgende Punkte und Hinweise: Ich habe every string w und all i in der formalen Definition des Pumping Lemma oben fett geschrieben.

• wenn auch mit einigen Sufficiently large W in Sprache, die Sie in der Lage, neue Zeichenfolge in Sprache aber nicht möglich, auf all zu generieren! Es gibt viele mögliche Optionen für W (unten in meinem Beweis) mit, dass Sie nicht keine Wahl von finden y neue Zeichenfolge in Sprache zu erzeugen für alle i> = 0. Also, weil jede Sufficiently large W nicht in der Lage ist, neue Zeichenfolge in der Sprache zu generieren, daher ist die Sprache NICHT regulär.

lesen: what pumping lemma formal definition says

Beweis: Verwendung von Pumpen Lemma

Schritt (1): wählen Zeichenfolge W = ein ⁿ b ^m wo (n + m) ≥ p und n = m + 1.

Is this choice ofWis valid according to pumping lemma?

Ja, so W ist in Sprache, weil Anzahl der a = n > Anzahl von b = m. W ist in Sprache und ausreichend groß> = p.

Schritt (2): wählte nun eine y neue Zeichenfolge zu erzeugen, für allei >= 0.

Und keine Wahl ist möglich für y dieses Mal! Warum?

Erste ist es Essay zu verstehen, dass wir nicht b Symbol in y haben können, weil sie entweder neue Saiten aus Muster wird oder in resultierenden String Gesamtzahl der b generieren mehr sein als die Gesamtzahl der a Symbole.

Zweite, können wir y nicht gewählt = einige ein ‚s weil mit i=0 würden Sie eine neue Zeichenfolge erhalten, in der Anzahl der a s wird b s dann Nummer kleiner sein, dass ist in der Sprache nicht möglich. (Anzahl von a in W erinnern, wurde das Entfernen nur ein weiteres dann b so dass jede ein Mittel in resultierende Zeichenfolge N (a) = N (b) die aufgrund n nicht akzeptabel ist> m)

So könnten wir einige W finden, die ausreichend groß sind, aber mit der wir keine neue Zeichenfolge in der Sprache erzeugen können, die der Pumping-Lemma-Eigenschaft der regulären Sprache widerspricht, also dann die Sprache {a ⁿ b ^| | n> m} ist nicht eine normale Sprache in der Tat.