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.