Lema bombeando para gramáticas regulares
Teorema
Seja L uma linguagem regular. Então existe uma constante‘c’ de modo que para cada corda w no L -
|w| ≥ c
Nós podemos quebrar w em três cordas, w = xyz, de modo que -
- | y | > 0
- | xy | ≤ c
- Para todo k ≥ 0, a string xy k z também está em L.
Aplicações do Lema de Bombeamento
O Lema de Bombeamento deve ser aplicado para mostrar que certas línguas não são regulares. Nunca deve ser usado para mostrar que o idioma é regular.
E se L é regular, ele satisfaz o Lema de Bombeamento.
E se L não satisfaz o Lema do Bombeamento, é não regular.
Método para provar que uma linguagem L não é regular
Em primeiro lugar, temos que assumir que L é regular.
Então, o lema do bombeamento deve valer para L.
Use o lema do bombeamento para obter uma contradição -
Selecione w de tal modo que |w| ≥ c
Selecione y de tal modo que |y| ≥ 1
Selecione x de tal modo que |xy| ≤ c
Atribuir a string restante para z.
Selecione k de modo que a string resultante não esteja em L.
Hence L is not regular.
Problem
Provar que L = {aibi | i ≥ 0} não é regular.
Solution -
No início, assumimos que L é regular en é o número de estados.
Seja w = a n b n . Assim, | w | = 2n ≥ n.
Ao bombear o lema, deixe w = xyz, onde | xy | ≤ n.
Seja x = a p , y = a q , ez = a r b n , onde p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Assim, | y | ≠ 0.
Seja k = 2. Então xy 2 z = a p a 2q a r b n .
Número de como = (p + 2q + r) = (p + q + r) + q = n + q
Portanto, xy 2 z = a n + q b n . Como q ≠ 0, xy 2 z não tem a forma a n b n .
Assim, xy 2 z não está em L. Portanto, L não é regular.