Lema do bombeamento para linguagens livre de contexto

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Searchtool.svg
Esta página ou secção foi marcada para revisão, devido a inconsistências e/ou dados de confiabilidade duvidosa. Se tem algum conhecimento sobre o tema, por favor, verifique e melhore a consistência e o rigor deste artigo. Considere utilizar {{revisão-sobre}} para associar este artigo com um WikiProjeto e colocar uma explicação mais detalhada na discussão.

O lema do bombeamento para linguagens livres de contexto, também conhecido como o lema Bar-Hillel, é um lema que que sua propriedade é compartilhada por todas as linguagens livres de contexto. Declaração Formal Se uma linguagem L é livre de contexto, então existe algum inteiro p ≥ 1 tal que qualquer cadeia s em L com | s | ≥ p (onde p é um "comprimento de bombeamento") pode ser escrita como


Declaração formal[editar | editar código-fonte]

Se uma linguagem L é livre de contexto, então existe algum inteiro p ≥ 1 tal que qualquer cadeia s em L com | s | ≥ p (onde p é um "comprimento de bombeamento") pode ser escrita como

s = uvxyz

com as subcadeias u, v, x, y e z, de tal modo que

1. |vxy| ≤ p,
2. |vy| ≥ 1, e
3. uv nxy nz pertence a L para todo n ≥ 0.

Declaração Informal e explicação[editar | editar código-fonte]

O lema do bombeamento para linguagens livres de contexto (chamado apenas "o lema do bombeamento" para o resto deste artigo) descreve uma propriedade que todas as linguagens livres de contexto possuem. Propriedade que todas as cadeias da linguagem que têm comprimento de pelo menos p, onde p é uma constante chamada de bombeamento de comprimento que varia entre as linguagens livres de contexto. E s é uma sequência de tamanho pelo menos p, que está na linguagem.

Os estados de bombeamento de s podem ser dividida em cinco subcadeias, s = uvxyz onde vy não pode ser vazia e o comprimento de vxy é no máximo de p, de tal modo que qualquer repetição de v e y produz uma cadeia s que ainda está na linguagem. Este processo de "bombear" cópias adicionais de v e y é o que dá o lema do bombeamento seu nome. Observe que as linguagens finitas (que são regulares e, portanto, livre de contexto) obedecem ao lema do bombeamento trivialmente por ter p igual ao comprimento máximo da cadeia em L, mais um. Como não existem cadeias desse comprimento o lema do bombeamento não é violado. O lema do bombeamento é frequentemente usado para provar que uma determinada linguagem não é livre de contexto, mostrando que para cada p, podemos encontrar alguma cadeia s de comprimento pelo menos p na linguagem que não tem as propriedades descritas acima, ou seja, que ele não pode ser "bombeada", sem conseguir produzir alguma cadeia da linguagem.


Uso do lema[editar | editar código-fonte]

Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido. Ajude e colabore com a tradução.

Por exemplo, podemos mostrar que a linguagem L = \lbrace a^ib^ic^i|i>0\rbrace não é livre de contexto usando o lema do bombeamento em uma prova por contradição. Em primeiro lugar, assumimos que L é livre de contexto. Pelo lema de bombagem, existe um número inteiro p que é o comprimento de bombeamento da linguagem. Considere a cadeia s = a^pb^pc^p em L. O lema do bombeamento nos diz que pode ser escrito na forma s=uvxyz, onde u, v, x, y, and z são subcadeias, de tal forma que |vxy| \le p, |vy|\ge 1, euv^ixy^iz pertence a L para cada inteiro i\ge 0. Escolhendo s e o fato de |vxy| \le p, vê-se facilmente que a substring vxy não pode conter mais do que duas letras distintas. Ou seja, temos uma das cinco possibilidades para vxy:

  1. vxy = a^j para cada j \le p.
  2. vxy = a^jb^k para cada j e k com  j+k \le p.
  3. vxy = b^j para cada j \le p.
  4. vxy = b^jc^k para cada j e k com  j+k \le p.
  5. vxy = c^j para cada j \le p.

Para cada caso, é facilmente verificado que uv^ixy^iz não contem iguais números para cada letra em cada i\ne 1. Então, uv^2xy^2z não tem a forma a^ib^ic^i. Isso contradiz a definição de L. Portanto, o que assumimos no início para L, sendo livre de contexto é falso.

Enquanto o lema do bombeamento é muitas vezes uma ferramenta útil para provar que uma determinada linguagem não é livre de contexto, não dos da uma caracterização completa das linguagens livres de contexto. Se uma linguagem não satisfaz a condição dada pelo lema do bombeamento, sabemos que ela não é livre de contexto. Por outro lado, existem linguagens que não são livres de contexto, mas ainda satisfazem a condição dada pelo lema do bombeamento. Existem técnicas de prova mais poderosos disponíveis, tais como lema de Ogden, mas também não dão uma caracterização completa das linguagens livres de contexto.

Veja também[editar | editar código-fonte]

Referências

  • Bar-Hillel, Y.; Perles, M. and Shamir, E. (1961). "On formal properties of simple phrase-structure grammars". Zeitschrift fur Phonetik, Sprachwissenschaft, und Kommunikationsforschung 14: 143–177.
  • Michael Sipser. Introduction to the Theory of Computation. [S.l.]: PWS Publishing, 1997. ISBN 0-534-94728-X Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.