O lema de bombeamento para idiomas regulares é uma ferramenta poderosa para provar que um idioma * não é * regular. Funciona por contradição:você assume que o idioma * é * regular e depois mostra que essa suposição leva a uma contradição do próprio lema. Aqui está como funciona:
1. A declaração do lema de bombeamento: O lema de bombeamento afirma que, para qualquer idioma regular L, existe um comprimento de bombeamento P, de modo que qualquer corda w em L com comprimento | W | ≥ p pode ser dividido em três substringas, w =xyz, satisfazendo as seguintes condições:
*
| xy | ≤ P: O comprimento da concatenação de x e y é menor ou igual a p.
*
| y |> 0: A substring y não está vazia.
*
para tudo i ≥ 0, xy
i
z ∈ L: Bombear zero ou mais vezes (incluindo removê -lo inteiramente quando i =0) resulta em uma string que ainda está no idioma L.
2. Estratégia de prova: Para provar que um idioma L não é regular usando o lema de bombeamento, siga estas etapas:
*
Suponha que L seja regular: Comece assumindo, por uma questão de contradição, que L é um idioma regular.
*
Escolha um comprimento de bombeamento p: O lema de bombeamento garante a existência de um comprimento de bombeamento p; Você não precisa encontrar seu valor real, apenas consulte -o como 'P'.
*
Escolha uma string w ∈ L tais que | W | ≥ P: Selecione cuidadosamente uma string w no idioma l cujo comprimento é pelo menos p. A escolha de W é crucial; Deve permitir que você crie uma contradição na próxima etapa. Isso geralmente envolve strings com uma estrutura específica relacionada à definição do idioma.
*
Mostre que nenhuma decomposição w =xyz satisfaz as condições do lema de bombeamento: Este é o coração da prova. Para * qualquer * possível decomposição de w em xyz satisfazendo | xy | ≤ p e | y |> 0, você deve mostrar que existe alguns i ≥ 0 tal que xy
i
Z ∉ L. Isso significa que o bombeamento y viola a definição da linguagem L. Frequentemente, você demonstra isso mostrando que a bombeamento y também:
*
Apresente um desequilíbrio: Altere o número de ocorrências de algum símbolo, violando uma restrição de contagem em L.
*
Crie uma estrutura inválida: Quebre o padrão ou estrutura exigida pela definição de L.
*
Apresente uma substring inválida: Crie uma substring que não pertence ao idioma.
*
Conclua que L não é regular: Como você mostrou que essa decomposição pode existir para a corda escolhida W, isso contradiz o lema de bombeamento. Portanto, a suposição inicial de que L é regular deve ser falsa e L não é regular.
Exemplo:Provando {a
n
B
n
| n ≥ 0} não é regular: Seja l ={a
n
B
n
| n ≥ 0}.
1.
Suponha que L seja regular. 2.
Escolha P: Seja p o comprimento do bombeamento.
3.
Escolha W: Seja w =a
p
b
p
. Claramente, w ∈ L e | W | ≥ p.
4.
Mostrar nenhuma decomposição satisfaz as condições: Vamos considerar qualquer decomposição w =xyz tal que | xy | ≤ p e | y |> 0. Desde | xy | ≤ p, y deve consistir * somente * de A's (porque y é uma substring dos primeiros caracteres P). Assim, y =a
k
para alguns k> 0. Agora, bomba y zero vezes:xy
0
z =a
p-k
b
p
. Essa string não está em L porque o número de A e B são diferentes. Isso contradiz o lema de bombeamento.
5.
Conclua: Desde que alcançamos uma contradição, nossa suposição de que L é regular deve ser falsa. Portanto, l ={a
n
B
n
| n ≥ 0} não é um idioma regular.
A chave é escolher cuidadosamente a string `W` e analisar de maneira inteligente todas as decomposições possíveis` xyz` para mostrar que o bombeamento `y` sempre leva a uma string fora do idioma. Quanto mais complexa a linguagem, mais complexa a escolha de `w` e a análise se tornará.
