Das Verwenden von Pumping Lemma, um die Sprache

19

Ich versuche, Pump-Lemma zu verwenden, um zu beweisen, dass nicht regulär ist.L={(01)m2mm0}

Dies ist, was ich bisher habe: Angenommen, ist regulär und sei die Pumplänge, so ist . Man betrachte jede Pumpzerlegung so, dass und .p w = ( 01 ) p 2 p wLpw=(01)p2pw=xyz|y|>0|xy|p

Ich bin mir nicht sicher, was ich als nächstes tun soll.

Bin ich auf dem richtigen Weg? Oder bin ich weg?

Momagic
quelle
1
Sie sind auf dem richtigen Weg. Wenn Sie "pumpen", ändern Sie die Anzahl der Nullen und Einsen, aber nicht die Anzahl der Zweien (warum?). Dies wird zu einem Widerspruch führen.
Ran G.
oh, beachten Sie, dass es nicht sein kann und | x y | < p . Ich denke das ist ein Tippfehler und du meintest | y | > 0 . |y|>p|xy|<p|y|>0
Ran G.
1
Beachten Sie, dass das Pumplemma hier nicht der schnellste Weg ist, da kanonischen Beispielen für nicht reguläre Sprachen sehr nahe kommt. Versuchen Sie, die Verschlusseigenschaften von R E G zu verwenden ! LREG
Raphael
1
Oder überprüfen Sie den Beweis des Pumplemmas, um zu erkennen, dass Sie die gepumpte Saite auch am Ende haben können, und pumpen Sie die 2s, was einfacher ist.
vonbrand
@vonbrand oder nehmen Sie die Umkehrung der Sprache und wenden Sie das gerade Pumplemma auf diese an.
Al.G.

Antworten:

5

Hinweis: Sie müssen überlegen, wie alle Zerlegungen aussehen, damit für alle möglichen Dinge x , y und z angegeben werden kann, dass x y z = ( 01 ) p 2 p . Dann pumpen Sie jeden einzelnen und sehen, ob Sie einen Widerspruch bekommen, der ein Wort ist, das nicht in Ihrer Sprache vorkommt. Jeder Fall muss zu einem Widerspruch führen, der dann ein Widerspruch zum Pumplemma wäre. Voila! Die Sprache wäre nicht regelmäßig.w=xyzxyzxyz=(01)p2p

Natürlich müssen Sie die Details durcharbeiten und alle möglichen Aufteilungen berücksichtigen.

Dave Clarke
quelle
5

Sie haben eine Zerlegung und eine Längenbeschränkung | x y | p . Was sagt dies darüber aus, wie x , y und z in die Zerlegung passen können? Insbesondere das Pump-Lemma ermöglicht es Ihnen, y zu wiederholen. Ihr Ziel ist es also, einen Weg zu finden, wie Sie y viele Male wiederholen (oder y entfernen)xyz=(01)p2p|xy|pxyzyyy , manchmal einfacher) das Muster, das die Sprache definiert, unwiederbringlich stört.

Es gibt eine offensichtliche Grenze im Muster: Der erste Teil enthält Wiederholungen von , der zweite Teil enthält nur 2er . Das Interessante ist , wo y fällt. Ist y immer in einem dieser Teile enthalten, oder kann es die beiden überspannen?012yy

Seit , x y vollständig in dem enthalten ist ( 01 ) p seits und z enthält alle 2 s. Wenn Sie y also noch einmal wiederholen , erhalten Sie einen längeren ersten Teil, aber der 2 p- Teil bleibt der gleiche. Mit anderen Worten endet x y y z mit genau p Buchstaben 2 . Zeigen Sie, dass x y y z zu viele Buchstaben 0 und 1 enthält, um den Beweis ordnungsgemäß abzuschließen|xy|pxy(01)pz2y2pxyyzp2xyyz01 zum regulären Ausdruck passen.

Gilles 'SO - hör auf böse zu sein'
quelle
4

Drei Jahre später werden wir beweisen, dass mit Δ = { 0 , 1 , 2 }L={(01)m2mm0}Δ={0,1,2} nicht regelmäßig ist, indem Verschlusseigenschaften widersprechen (ein schnellerer Weg als die Verwendung des Pumplemmas) ).

Zuerst nehmen wir an, dass L regelmäßig ist. Wir wissen, dass reguläre Sprachen unter inversem Homomorphismus geschlossen sind.

Betrachten wir die Homomorphismus mit:h:ΣΔ

Σ={a,b}

h(a)=01

h(b)=2

Der inverse Homomorphismus von ist:L

h1(L)={anbn|n0}=L

Dies erzeugt einen Widerspruch, weil ein kanonisches Beispiel einer unregelmäßigen Sprache ist, so dass L nicht regelmäßig sein kann.LL

Renato Sanhueza
quelle
3

Ich werde auf diese Frage keine Antwort geben, da dies nicht genau das pumpfähige Lemma ist, aber vielleicht Aufschluss darüber gibt, was die Idee des pumpfähigen Lemmas ist. Hier ist eine einfache Tatsache über deterministischen endlichen Automaten, die das Wesen des Myhill-Nerode Satz ist: Wenn zwei Strings und b die FSA auf den gleichen Zustand fahren, dann für jedes c , entweder beide ein c und b c sind akzeptiert oder auch nicht.abcacbc

Angenommen, ein deterministischer Automat für Ihre Sprache hat Zustände. Dann fahren mindestens zwei von ( 01 ) 1 , ( 01 ) 2 , ... , ( 01 ) n + 1 , sagen wir ( 01 ) p und ( 01 ) q mit p q den Automaten in den gleichen Zustand (das ist der Taubenschlagprinzip). Entsprechend der Tatsache können dann sowohl ( 01 ) p 2 p als auchn(01)1(01)2(01)n+1(01)p(01)qpq(01)p2p sind in L oder keiner ist, was ein Widerspruch ist.(01)q2pL

Louis
quelle