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

8

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={02n | n0}(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?sxyzxyizLi

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:Lp1sL|s|>ps=xyz

  1. |y|1
  2. |xy|p
  3. xyizL para todos os .i0

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=02ps=ϵ002p1x=ϵy=0z=02p1i=0xyiz=ϵ0002p1=02p1L


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.

queimadura
fonte
4
O lema de bombeamento afirma que, para palavras com mais de algum comprimento pexiste essa decomposição. Você mostrou uma decomposição específica que não funciona, mas usa qualquer palavra com comprimento maior que 2 e y=02. (Deus tenha piedade de minha alma para responder)
Ariel
Existem guias muito bons nas postagens anteriores, por exemplo, cs.stackexchange.com/questions/1031/…
G. Ran G.
2
@Tocou. Esse post é um excelente guia sobre como provar que um idioma não é regular, mas parece que recebemos perguntas um pouco frequentes em que alguém tentou aplicar o lema de bombeamento e cometeu exatamente esse erro. Eu acho que é mais útil apontar qual é o erro em uma prova (por exemplo, marcando como uma bobagem desta pergunta) do que dizer: "Veja como fazê-lo corretamente; você descobre qual a diferença entre o seu abordagem e a correta é ".
David Richerby
2
@DavidRicherby você está certo, esta pergunta não é sobre mostrar não-regularidade usando bombeamento. O uso incorreto mais comum do lema é entender mal os quantificadores, e o guia da pergunta que mencionei tenta resolver esse problema (por exemplo, escrevendo em negrito: todas as maneiras de particioná-lo etc.)
Ran G.
O lema garante que haja alguma divisão que funcione se o idioma for regular. Para provar que isso não é regular, você precisa provar que nenhuma divisão funciona.
vonbrand

Respostas:

6

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|p xyzxyz

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{02nn0}p2p=1x=ϵy=0 0z=0 02p-1 1p2s=0 02ps=ϵ000 02(p-1 1)x=ϵy=00z=0 02(p-1 1)|ϵ00|p, |00|>1 e (00)i02(p1)L para todos i0. Portanto, existe uma maneira de decompor a string comoxyz 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 emxyzque 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-op. Pelo princípio pigeonhole, sempre que o DFA lê uma string com mais dep, 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 issoxz deve ser aceito: x leva você do estado inicial para q e z leva você de qpara um estado de aceitação. Da mesma forma,xyiz 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 emx, yzé 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.

David Richerby
fonte
Esta é uma boa explicação, mas estou me perdendo depois de ler cs.stackexchange.com/a/1051/10511 . Dê uma olhada no item 4. Ele está pensando em dividir a corda em três substrings. O jeito que eu leio é que eu deveria ser capaz de bombeá-lo de todas as maneiras que eu partisse a corda, assumindo que eu recebesse uma linguagem regular. Então, onde está o erro? Isso realmente me incomoda porque eu não entendo. A tal ponto que não consigo dormir normalmente à noite.
flashburn
11
@flashburn Se é suposto não ser regular, nenhuma divisão pode funcionar. Aqui encontramos um que funciona, portanto não podemos mostrar que ele não é regular usando esse lema.
Raphael
@flashburn Adicionei uma explicação sobre por que o lema de bombeamento é verdadeiro, o que pode ajudá-lo a entender, mostrando de onde vêm os requisitos do lema.
David Richerby
11
@flashburn Além disso, se seus estudos o estressam tanto que você não consegue dormir direito, converse com o serviço de aconselhamento da sua universidade. O lema de bombeamento é importante, mas sua saúde e bem-estar são muito mais importantes.
David Richerby
2
Sem mencionar que sono, nutrição e exercícios adequados farão sua mente funcionar muito melhor, @flashburn. Veja também aqui .
Raphael