Lema do Bombeamento e LLC

Prévia do material em texto

Com as LLC, surgiram dois mecanismos capazes de reconhecê-las, a saber: gramáticas livres de contexto e autômatos de pilha (AP). Dependendo do problema em que este último mecanismo for aplicado para resolver, pode ser dispendioso e às vezes nem ter uma resposta. Ainda que seja um ótimo reconhecedor em determinados contextos, é limitado em outros.
Considerando que pode haver uma resposta que não é possível com base no AP para determinado problema, é necessário verificar a possibilidade de alcançar uma solução com uma LLC.
Diante dessa problemática, pode-se aplicar o lema do bombeamento (LB), uma importante estrátégia para determinar se uma linguagem pertence ou não a determinada categoria da hierarquia de Chomsky. Com o LB, pode-se identificar se é viável implementar uma LLC para determinado contexto/problema ou se é necessário utilizar uma linguagem mais abrangente.
Suponha que você precise solucionar a seguinte questão:
Descreva o raciocínio utilizado para solucionar o problema. 
Resposta
Assuma que L1 ∈ LLC, sendo p o comprimento de bombeamento, de acordo com o LB, e a cadeia escolhida seja w = 0n, em que n > p, sendo n um número primo. Suponha que w pode ser dividido em uvxyz, |vy| > 0 e |vxy| ≤ p e, como consequência, uvixyiz para qualquer i >= 0 deve pertencer a L1, isto é, w = uvixyiz, ∀i >= 0.
Conforme as informações da suposição de que L1 ∈ LLC, tem-se que On = uvxyz, incorrendo em uvixyiz = 0n + (i -1)(|vy|). Desse modo, i deve ser do formato n + (i - 1)(|vy|) (expressão 1), de tal forma que tenha outros divisores além de si mesmo.
Para chegar à condição desejada, em que i não seja primo, usa-se i = n + 1 (expressão 2). Usando a expressão (2) na (1), tem-se: n + n|vy| = n(1 + |vy|).
Isso resulta em um número não primo, em virtude de |xy| > 0, em que x e y podem assumir valores quaisquer. Portanto, ao utilizarmos uvi+1xyi+1z ∉ L1, entrando em contradição com o LB, L1 não pode ser uma LLC.
image1.jpeg