CCT-UFCA/Ciência da Computação/Autômatos e Linguagens Formais/Lema do Bombeamento

O lema do bombeamento é um resultado que afirma que todas as linguagens regulares têm uma propriedade especial. Logo, se dada linguagem não possui essa propriedade, ela não é regular. Contudo, essa propriedade não é um "se e somente se", significando que caso uma linguagem tenha essa propriedade, não é garantido que ela seja regular. Parar provar que uma linguagem é regular, é necessário ainda mostrar um AFD, AFN ou uma ER que a reconheça.

Lema

Se L é uma linguagem regular, então existe um número p tal que toda cadeia w ∈ L com |w| > p pode ser escrita da forma w = xyz em que:

y ≠ ε;
|xy| ≤ p;
para todo i >= 0, xyⁱz ε L.

A principal ideia do lema do bombeamento é a garantia que, com p = |Q| e n sendo a quantidade de estados, ao passar por n + 1, há repetição de estados ao ler a cadeia de entrada, pois n + 1 > p (princípio da casa dos pombos).

Ideia da prova: Seja M = (Q, Σ, δ, q₁, F) um AFD que reconhece A. Atribuímos o comprimento de bombeamento p como sendo o número de estados de M. Mostramos que qualquer cadeia s em A de comprimento pelo menos p pode ser quebrada nas três partes xyz satisfazendo nossas três condições. E se nenhuma cadeia em A é de comprimento pelo menos p? Então, nossa tarefa é ainda mais fácil porque o teorema se torna vacuamente verdadeiro: obviamente as três condições se verificam para todas as cadeias de comprimento pelo menos p se não existem tais cadeias.

Se s em A tem comprimento pelo menos p, considere a sequência de estados pelos quais M passa quando computando com a entrada s. Ele começa com o estado inicial q₁, e então vai para, digamos, q₃, e daí para, digamos, q₂₀, e então para q₉, e assim por diante, até que ele atinge o final de s no estado q₁₃. Com s em A, sabemos que M aceita s, portanto q₁₃ é um estado de aceitação.

Se dissermos que n é o comprimento de s, a sequência de estados q₁, q₃, q₂₀, q₉, ..., é maior que p, o número de estados de M. Por conseguinte a sequência tem que conter um estado repetido. Esse resultado é um exemplo do princípio da casa-de-pombos, um nome pomposo para o fato um tanto óbvio de que se p pombos são colocados em menos que p casas, alguma casa tem que ter mais que um pombo.

Agora dividimos s em três partes x, y e z. A parte x é a parte de s que aparece ant6es de q₉, a parte y é a parte entre as duas apartições de q₉. Portanto x leva M do estado q₁ para q₉, y leva M de q₉ e z leva M de q₉ para o estado de aceitação q₁₃.

Vamos ver por que essa divisão satisfaz as três condições. Suponha que rodemos M sobre a entrada xyyz. Sabemos que x leva M de q₁ para q₉, e então o primeiro y o leva de q₉ de volta a q₉, o mesmo fazendo o segundo y, e então z o leva para q₁₃. Com q₁₃ sendo um estado de aceitação, M aceita a cadeia xyyz. Igualmente, ele aceitará xyⁱz para qualquer i > 0. Para o caso i = 0, xyⁱz = xz, que é aceita por razões semelhantes. Isso estabelece a condição 1.

Verificando a condição 2, vemos que |y| > 0, pois era a parte de s que ocorria entre duas ocorrências diferentes do estado q₉.

De modo a obter a condição 3, asseguramos que q₉ seja a primeira repetição na sequência. Pelo princípio da casa-de-pombos, os primeiros p+1 estados na sequência têm que conter uma repetição. Por conseguinte |xy| ≤ p.

Linguagens não regulares

Dado uma linguagem, para provar que ela é regular, devemos mostrar um AFD, AFN ou uma ER que a reconheça. Pelo lema do bombeamento, existe alguma forma de bombear sua cadeia. Para provar que ela não é regular, devemos utilizar a contradição do lema de bombeamento, mostrando que para todo p, existe w ∈ L com |w| > p, para todo x, y e z com w = xyz, uma das 3 condições do lema não vale. A ideia é mostrar a divisão da cadeia em x, y e z de uma forma que seja impossível de ser bombeada.

Seja a linguagem L = {0ⁿ1ⁿ: n ≥ 1}'. Vamos provar que ela é uma linguagem não regular. Primeiramente, suponha que ela é regular, logo o lema vale. Seja p o valor dado pelo lema e w = 0^p1^p. Como |w| ≥ p, w pode ser escrita como xyz tal que valem as 3 propriedades. Bombeando para cima (i = 2), w terá o formato xyyz. Pela propriedade 2, |xy| ≤ p, xy precisa ter no máximo p zeros. Contudo, como bombeamos para cima, aumentamos o valor de 0s, o que acarreta em 0^p'1^p, onde p < p. Como L precisa ter quantidade iguais de 0s e 1s, temos que xy²z ∉ L. Logo, L não é regular.