Tô estudando aqui, vamos estudar juntos comigo.
Matéria: Linguagens Formais e Autômatos
Assunto: Linguagens Livres de Contexto
Sub-Assunto: Lema do Bombeamento para provar que uma Linguagem não é Livre de Contexto.
Amigos, vamos provar que a Linguagem w = a^n b^n c^n, com n >=0, não é uma LLC.
Supondo que a^k b^k c^k = uvwxy, |vxw| <= k e vx == vazio, temos duas possibilidades:
1) vx contém algum a. Como |vxw| <= k, vx não contém c's. Portanto, uv²wx²y contém mais a's do que c's. Portanto, uv²wx²y não pertence a Linguagem.
OU
2) vx não contém a algum. Como vx == vazio, uv²wx²y contém menos a's do que c's ou/e b's. Portanto, uv²wx²y não pertence a Linguagem.
Mas, há outro jeito para fazer, quando eu aprender eu posto aqui.
TELECURSO 2010.