Lema de bombeamento para CFG

Lema

E se L é uma linguagem livre de contexto, há um comprimento de bombeamento p de modo que qualquer corda w ∈ L de comprimento ≥ p pode ser escrito como w = uvxyz, Onde vy ≠ ε, |vxy| ≤ p, e para todos i ≥ 0, uvⁱxyⁱz ∈ L.

Aplicações do Lema de Bombeamento

O lema do bombeamento é usado para verificar se uma gramática está livre de contexto ou não. Vamos dar um exemplo e mostrar como ele é verificado.

Problema

Descubra se o idioma L = {xⁿyⁿzⁿ | n ≥ 1} é livre de contexto ou não.

Solução

Deixei Lé livre de contexto. Então,L deve satisfazer o lema do bombeamento.

Primeiro, escolha um número ndo lema do bombeamento. Então, considere z como 0 ⁿ 1 ⁿ 2 ⁿ .

Pausa z para dentro uvwxy, Onde

|vwx| ≤ n and vx ≠ ε.

Conseqüentemente vwxnão pode envolver 0s e 2s, uma vez que o último 0 e os primeiros 2 estão separados por pelo menos (n + 1) posições. Existem dois casos -

Case 1 - vwxnão tem 2s. Entãovxtem apenas 0s e 1s. Entãouwy, que teria que estar em L, tem n 2s, mas menos do que n 0s ou 1s.

Case 2 - vwx não tem 0s.

Aqui ocorre contradição.

Conseqüentemente, L não é uma linguagem livre de contexto.