O lema do bombeamento para linguagens livres de contexto é um teorema utilizado na teoria da computação para provar que certas linguagens não são livres de contexto. Esse lema afirma que, se uma linguagem L é livre de contexto, então existe um número inteiro positivo p, chamado de constante de bombeamento, tal que qualquer palavra w em L, com comprimento maior ou igual a p, pode ser dividida em cinco partes: w = uvxyz, onde as seguintes condições são satisfeitas: 1. Para todo i ≥ 0, a palavra uv^ixy^iz também pertence a L. 2. A palavra vxy não é vazia. 3. O comprimento de uvxy é no máximo p. Se alguma dessas condições não for satisfeita, então a linguagem L não é livre de contexto. Esse lema é útil para mostrar que certas linguagens não podem ser geradas por gramáticas livres de contexto.
Para escrever sua resposta aqui, entre ou crie uma conta
Compartilhar