O que há de errado com a minha prova de lema?

O idioma é obviamente regular - por exemplo, corresponde à expressão regular . Mas o seguinte argumento do lema de bombeamento parece mostrar que não é regular. O que deu errado?$L = \{0^{2n} \space |\space n \ge 0 \}$$(00)^*$

Eu encontrei uma maneira de dividir uma entrada como satisfazer os requisitos do lema do bombeamento, mas não é verdade que para todo  . Isso não significa que o idioma não é regular?$s$$xyz$$xy^iz\in L$$i$

Mais detalhadamente, o lema de bombeamento para idiomas regulares diz que, se um idioma  é regular, existe um comprimento de bombeamento , de forma que qualquer string com possa ser escrita como como aquele:$L$$p \ge 1$$s\in L$$|s|> p$$s = xyz$

1. $\lvert y \rvert \ge 1$
2. $\lvert xy \rvert \le p$
3. $xy^iz\in L$ para todos os .$i \ge 0$

Então, vamos pegar e escrever como (ou seja, , , ). Isso satisfaz 1. e 2. Mas, considerando , obtemos , que não está em  porque seu comprimento é ímpar. Parece que o idioma não é regular, afinal.$s = 0^{2p}$$s=\epsilon\, 0 \, 0^{2p-1}$$x = \epsilon$$y = 0$$z = 0^{2p-1}$$i=0$$xy^iz = \epsilon\, 0^0\,0^{2p-1} = 0^{2p-1}$$L$

^{Isto é pretendido como uma pergunta de referência que ilustra um erro comum no uso do lema de bombeamento para idiomas regulares. Agradecemos a Ariel por detectar o problema na versão original da pergunta.}

O problema está nos quantificadores. O lema de bombeamento diz que qualquer string com pode ser escrita como modo que as três propriedades sejam mantidas. Não diz que toda maneira de escrevê-lo como que mantém as duas primeiras propriedades também mantém a terceira.$s$$|s|\geq p$ $xyz$$xyz$

Para o idioma , procedemos da seguinte forma. Primeiro, observe que devemos ter , pois se , somos forçados a tomar , , e você já mostrou na pergunta que isso não funciona. Portanto, com , podemos escrever como ( , , ). Nós temos$\{0^{2n}\mid n\geq 0\}$$p\geq 2$$p=1$$x=\epsilon$$y=0$$z=0^{2p-1}$$p\geq 2$$s = 0^{2p}$$s=\epsilon\,00\,0^{2(p-1)}$$x=\epsilon$$y=00$$z=0^{2(p-1)}$$|\epsilon00| \leq p$, $|00|>1$ e $(00)^i\,0^{2(p-1)}\in L$ para todos $i\geq 0$. Portanto, existe uma maneira de decompor a string como$xyz$ isso satisfaz todas as propriedades, mesmo que a primeira decomposição em que você pensou não tenha funcionado.

Para mostrar que um idioma não é regular, você precisa mostrar que toda decomposição em$xyz$que satisfaz as duas primeiras propriedades falha em satisfazer a terceira. Não basta apenas mostrar que uma decomposição não funciona.

Para entender por que o lema de bombeamento é do jeito que é, ajuda a pensar na prova. Se um idioma é regular, é aceito por algum DFA. Que o DFA tem algum número de estados: chame-o$p$. Pelo princípio pigeonhole, sempre que o DFA lê uma string com mais de$p$, ele deve visitar algum estado duas vezes: diga estado $q$. Agora,$x$ é a parte da entrada lida até (e incluindo) a primeira visita a $q$, $y$ é a parte lida após a primeira visita e até e incluindo a segunda (que deve ter pelo menos um caractere) e $z$ é o resto. Mas agora você pode ver isso$xz$ deve ser aceito: $x$ leva você do estado inicial para $q$ e $z$ leva você de $q$para um estado de aceitação. Da mesma forma,$xy^iz$ deve ser aceito para qualquer positivo $i$, já que cada repetição de $y$ leva você de $q$ de volta a $q$. Observe que a decomposição da entrada em$x$, $y$ e $z$é inteiramente determinado pelo autômato que, por sua vez, é determinado (mas não exclusivamente) pelo idioma. Portanto, você não escolhe a decomposição: se o idioma é regular, existe alguma decomposição; para mostrar que um idioma não é regular, você deve mostrar que toda decomposição falha.