El uso de Pumping Lemma para probar el lenguaje

Estoy tratando de usar el lema de bombeo para demostrar que no es regular.$L = \{(01)^m 2^m \mid m \ge0\}$

Esto es lo que tengo hasta ahora: suponga que es regular y deje que p sea ​​la longitud de bombeo, entonces w = ( 01 ) p 2 p . Considere cualquier descomposición de bombeo w = x y z tal que | y | > 0 y | x y | ≤ p .$L$$p$$w = (01)^p 2^p$$w = xyz$$|y| >0$$|xy| \le p$

No estoy seguro de qué hacer a continuación.

¿Estoy en el camino correcto? ¿O estoy lejos?

Sugerencia: debe tener en cuenta cómo se ven todas las descomposiciones , entonces, ¿cuáles son todas las cosas posibles x , y y z que pueden darse que x $w=xyz$$x$$y$$z$ . Luego, bombea cada una y ve si tiene una contradicción, que será una palabra que no esté en su idioma. Cada caso debe conducir a una contradicción, que sería una contradicción del lema de bombeo. Voila! El lenguaje no sería regular.$xyz=(01)^p2^p$

Por supuesto, debe trabajar en los detalles y considerar todas las divisiones posibles.

Tiene una descomposición y una restricción de longitud | x y | ≤ p . ¿Qué dice esto acerca de cómo x , y y z pueden caber en la descomposición? En particular, el lema de bombeo le permite repetir y , por lo que su objetivo es encontrar alguna forma de repetir $xyz = (01)^p 2^p$$|xy| \le p$$x$$y$$z$$y$$y$ muchas veces (o eliminar , a veces esto es más simple) perturbará irremediablemente el patrón que define el lenguaje.$y$

Hay un límite obvio en el patrón: la primera parte contiene repeticiones de , la segunda parte contiene solo 2 's. Lo interesante es donde $01$$2$$y$ cae. Es siempre contenida en una de estas partes, o puede horcajadas sobre los dos?$y$

Desde , x y está completamente contenido en la parte ( 01 ) p , y z contiene todos los 2 's. Entonces, si repites y una vez más, obtienes una primera parte más larga, pero la parte 2 p sigue siendo la misma. En otras palabras, x y y z termina con exactamente p letras 2 . Para finalizar la prueba correctamente, demuestre que x y y z contiene demasiadas letras 0 y $|xy| \le p$$xy$$(01)^p$$z$$2$$y$$2^p$$xyyz$$p$$2$$xyyz$$0$$1$ para ajustarse a la expresión regular.

Tres años más tarde, vamos a demostrar que con Δ = { 0 , 1 , 2 } no es regular por contradicción usando las propiedades de cierre (una forma más rápida que usar el lema de bombeo )$L = \{(01)^m 2^m \mid m \ge0\}$$\Delta=\{0,1,2\}$

Primero suponemos que es regular. Sabemos que los idiomas regulares están cerrados bajo homomorfismo inverso.$L$

Considere el homomorfismo con:$h:\Sigma^* \rightarrow \Delta^*$

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

$h(a)= 01$

$h(b)= 2$

El homomorfismo inverso de es:$L$

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

Esto genera una contradicción porque es un ejemplo canónico de un lenguaje irregular, por lo que L no puede ser regular.$L'$$L$

Voy a dar una respuesta a esta pregunta, ya que este no es exactamente el lema de bombeo, pero tal vez arroje luz sobre cuál es la idea del lema de bombeo. Aquí hay un hecho básico sobre los autómatas deterministas de estado finito, que es la esencia del teorema de Myhill-Nerode: si dos cadenas y b conducen la FSA al mismo estado, entonces, para cualquier c , tanto a c como b c son aceptado, o tampoco lo es.$a$$b$$c$$ac$$bc$

Volviendo a su problema, suponga que un autómata determinista para su idioma tiene estados. Luego, al menos dos de ( 01 ) 1 , ( 01 ) 2 , ... , ( 01 ) n + 1 , digamos ( 01 ) p y ( 01 ) q con p ≠ q , conducen el autómata al mismo estado (este es el principio de agujero de paloma). De acuerdo con el hecho, entonces cualquiera de los dos ( 01 ) p 2 $n$$(01)^1$$(01)^2$$\ldots$$(01)^{n+1}$$(01)^p$$(01)^q$$p\neq q$$(01)^p2^p$ y están en L o ninguno lo está, lo cual es una contradicción.$(01)^q2^p$$L$