5

Estava lendo pelo HOPCROFT e tive dificuldade em aplicar o lema do bombeamento de maneira formal aos exercícios para provar que uma linguagem não é regular.

Neste caso, me refiro ao Lema do Bombeamento para linguagens regulares.

Em alguns casos consegui mostrar casos específicos, mas minha professora somente aceita provas generalistas na avaliação.

1
  • 1
    Ótima questão, mas estou meio sem cabeça pra responder. Dei exemplos em outras perguntas da tag linguagens-formais, deve ter um conhecimento espalhado por aí. Um desses exemplos foi recente, está nesta resposta. No caso, voltado a linguagens regulares. Mas deve ter em algum lugar um lema do bombeamento para LLC em alguma resposta solta. Não conheço lema do bombeamento para linguagens sensíveis a contexto, também acho que não haja para gramáticas irrestritas (só lembrando, gramáticas irrestritas são Turing-completas) Commented 13/07/2018 às 4:18

1 Resposta 1

4

O que é o lema do bombeamento

O lema do bombeamento é uma condição sine qua non de linguagens regulares/livres de contexto (dependendo de qual você esteja usando, claro). Porém, não é uma condição suficiente.

Como você pediu para focar apenas no lema do bombeamento para linguagens regulares, fica esta nota aqui dizendo que existe o lema do bombeamento para linguagens livres de contexto.

Isso significa que, para toda linguagem regular, é possível "bombear mais vezes" uma string. Dou mais exemplos sobre isso nesta resposta.

Qual o pensamento atrás do lema do bombeamento? Bem, que temos um processo de Markov rodando (esse processo é, como implicado por Chomsky em seu artigo, o autômato finito da linguagem regular) que gera/identifica palavras em uma linguagem regular. Então, isso significa que há uma rota entre o começo da palavra até o seu final. Se, por acaso, essa rota fizer um laço, eu poderia repeti-lo infinitas vezes e ainda assim seria algo válido no processo de Markov. Então, já que se trata de um processo de Markov, posso repetir o laço que a nova palavra gerada por essa nova rota estará na linguagem regular.

O artigo do Chomsky é de uma leitura muito boa e divertida, afinal, "incolores ideias verdes dormem furiosamente". Só que ele parece que foi escaneado e a fonte do PDF não ficou lá muito agradável de ler. Melhor ler impresso.

Leia também essa resposta, tem até mesmo um quadrado de curiosidade para tentar auxiliar a não se perder entre os termos de Chomsky e os termos dos cientistas da computação/matemáticos. Imagina, Chomsky usa um termo que existe para os matemáticos, porém com um significado totalmente distinto...

Tá, tem algum exemplo desse laço e do processo de Markov? Peguemos esse autômato finito:

autômato que reconhece todas as palavras em <code>{a,b}*</code> que não contenham a subpalavra <code>bbab</code>

Vamos supor que eu segui o seguinte caminho (ou supor que reconheci a palavra bbba):

q0 -> qb1 -> qb2 -> qb2 -> qa

Note que a aresta qb2 -> qb2 forma uma subrota que é um laço sobre qb2. O laço mais simples possível, mas é um laço: inicia em um vértice e pára sobre ele mesmo. Nesse laço, produzimos exatamente o terceiro b da palavra bbba. Isso significa que podemos percorrer esse laço quantas vezes for que a palavra nova pertencerá à mesma linguagem. Ou seja, bbbbbba também é uma palavra válida.

No lema do bombeamento, esse laço é indicado pela subpalavra y. O que ocorre antes de y são os passos para chegar até o laço, que é a subpalavra x. O que vem depois é a cauda longa, que serve basicamente para terminar em um estado de aceitação, a subpalavra w. Logo, para usar o lema do bombeamento você precisa de uma palavra x.y.z tal que você possa bombear y quantas vezes quiser.

Tem uma sacadas matemáticas (como |x.y| <= p para um p arbitrário dependente da linguagem e |y| >= 1) para garantir que o bombeamento é válido, porém não entrarei em maiores detalhes sobre ele, quis deixar uma ideia mais formal sobre o porquê do lema do bombeamento funcionar.

Trabalhei o lema do bombeamento mais fortemente nesta resposta

Como aplicá-lo

O lema do bombeamento é, como dito antes, uma condição sine qua non de linguagens regulares. Ou seja, se a linguagem não satisfizer o lema, então ela garantidamente não é regular. Portanto, esse lema deve ser usado para excluir linguagens de serem classificadas como regular. Ele não deve ser usado para classificar positivamente como regular.

Basicamente, você precisa escolher uma palavra que pertença a linguagem em questão e dividi-la em x.y.z. Como você não sabe quem é p, então escolha arbitrariamente uma palavra que, de algum modo, tenha essa característica já nela embarcada. Por exemplo, para provar que a linguagem sobre um alfabeto binário em que ambas as letras aparecem no mesmo número de vezes, escolhi a palavra "0"^p . "1"^p. Ou seja, não importa qual o valor de p, ele está contemplado. Não vou repetir minha prova detalhada, mas qualquer y que você fizer conterá apenas 0s, logo bombear mais vezes y vai gerar uma palavra com mais 0s do que 1s, logo a palavra bombeada não pertence à linguagem. Portanto, não é regular.


Anexo:

Como provar que uma linguagem é regular?

Construa uma gramática regular que a reconheça. Essa é a prova direta. O lema do bombeamento vem pra dizer que, não importa o quanto você se esforce, será impossível criar uma gramática que reconheça exatamente a linguagem desejada.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .