Usar o Lemma de bombeamento para provar o idioma não é regular

Estou tentando usar o lema de bombeamento para provar que não é regular.$L = \{(01)^m 2^m \mid m \ge0\}$

É o que tenho até agora: suponha que seja regular e seja o comprimento do bombeamento, então . Considere qualquer decomposição de bombeamento tal que e .p w = ( 01 ) p 2 p w = x y z | y | > 0 | x y | ≤ $L$$p$$w = (01)^p 2^p$$w = xyz$$|y| >0$$|xy| \le p$

Não tenho certeza do que fazer a seguir.

Estou no caminho certo? Ou estou longe?

Dica: Você precisa considerar o que todas as decomposições aparência, então o que são todas as coisas possíveis x , y e z pode ser dada de que x y z = ( 01 ) p 2 p . Então você bombeia cada uma delas e vê se há uma contradição, que será uma palavra que não está no seu idioma. Cada caso precisa levar a uma contradição, que seria então uma contradição do lema de bombeamento. Voila! O idioma não seria regular.$w=xyz$$x$$y$$z$$xyz=(01)^p2^p$

Obviamente, você precisa trabalhar com os detalhes e considerar todas as possíveis separações.

Você tem uma decomposição e uma restrição de comprimento | x y | ≤ p . O que isso diz sobre como x , y e z pode caber na decomposição? Em particular, o lema de bombeamento permite que você repita y ; portanto, seu objetivo é encontrar uma maneira pela qual repetir y muitas vezes (ou remover y , às vezes isso é mais simples) perturbar irremediavelmente o padrão que define o idioma.$xyz = (01)^p 2^p$$|xy| \le p$$x$$y$$z$$y$$y$$y$

Há um limite óbvio no padrão: a primeira parte contém repetições de , a segunda parte contém apenas 2 's. O interessante é onde y cai. É y sempre contido em uma dessas partes, ou pode ficar em cima do dois?$01$$2$$y$$y$

Desde , x y está inteiramente contido na parte ( 01 ) p , e z contém todos os 2 's. Então, se você repetir y mais uma vez, você tem um longo primeira parte, mas o 2 p parte permanece o mesmo. Em outras palavras, x y y z termina com exatamente p letras 2 . Para concluir a prova adequadamente, mostre que x y y z contém muitas letras 0 e $|xy| \le p$$xy$$(01)^p$$z$$2$$y$$2^p$$xyyz$$p$$2$$xyyz$$0$$1$ para se ajustar à expressão regular.

Três anos depois, provaremos que com Δ = { 0 , 1 , 2 } não é regular por contradição, usando propriedades de fechamento (uma maneira mais rápida do que usar o lema de bombeamento) )$L = \{(01)^m 2^m \mid m \ge0\}$$\Delta=\{0,1,2\}$

Primeiro, supomos que seja regular. Sabemos que linguagens regulares são fechadas sob homomorfismo inverso.$L$

Considere o homomorfismo com:$h:\Sigma^* \rightarrow \Delta^*$

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

$h(a)= 01$

$h(b)= 2$

O homomorfismo inverso de é:$L$

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

Isso gera uma contradição, porque é um exemplo canônico de uma linguagem irregular, portanto L não pode ser regular.$L'$$L$

Vou dar uma não resposta a essa pergunta, já que esse não é exatamente o lema de bombeamento, mas talvez elucide qual é a idéia do lema de bombeamento. Aqui está um fato básico sobre autômatos de estados finitos determinísticos, que é a essência do teorema de Myhill-Nerode: Se duas cadeias e $a$$b$ conduzir o FSA para o mesmo estado, em seguida, para qualquer , ou ambos de um c e b c são aceito, ou nem é.$c$$ac$$bc$

De volta ao seu problema, suponha que um autômato determinístico para o seu idioma tenha estados. Então, pelo menos dois dos ( 01 ) 1 , ( 01 ) 2 , ... , ( 01 ) n + 1 , por exemplo ( 01 ) p e ( 01 ) q com p ≠ q , conduzir o autômato para o mesmo estado (este é o princípio do buraco do pombo). De acordo com o fato, então ( 01 ) p 2 p e$n$$(01)^1$$(01)^2$$\ldots$$(01)^{n+1}$$(01)^p$$(01)^q$$p\neq q$$(01)^p2^p$ estão em L ou nenhum é, o que é uma contradição.$(01)^q2^p$$L$