Das Verwenden von Pumping Lemma, um die Sprache

Ich versuche, Pump-Lemma zu verwenden, um zu beweisen, dass nicht regulär ist.$L = \{(01)^m 2^m \mid m \ge0\}$

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$L$$p$$w = (01)^p 2^p$$w = xyz$$|y| >0$$|xy| \le p$

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

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

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=xyz$$x$$y$$z$$xyz=(01)^p2^p$

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

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)^p 2^p$$|xy| \le p$$x$$y$$z$$y$$y$$y$ , 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?$01$$2$$y$$y$

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äß $|xy| \le p$$xy$$(01)^p$$z$$2$$y$$2^p$$xyyz$$p$$2$$xyyz$$0$$1$ zum regulären Ausdruck passen.

Drei Jahre später werden wir beweisen, dass mit Δ = { 0 , 1 , 2 $L = \{(01)^m 2^m \mid m \ge0\}$$\Delta=\{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:\Sigma^* \rightarrow \Delta^*$

$\Sigma = \{a,b\}$

$h(a)= 01$

$h(b)= 2$

Der inverse Homomorphismus von ist:$L$

$h^{-1}(L)= \{a^nb^n| n\geq 0 \} = L'$

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

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.$a$$b$$c$$ac$$bc$

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 auch$n$$(01)^1$$(01)^2$$\ldots$$(01)^{n+1}$$(01)^p$$(01)^q$$p\neq q$$(01)^p2^p$ sind in L oder keiner ist, was ein Widerspruch ist.$(01)^q2^p$$L$