Bombeo de lema para gramáticas regulares

Teorema

Sea L un idioma regular. Entonces existe una constante‘c’ tal que por cada cuerda w en L -

|w| ≥ c

Podemos romper w en tres cuerdas, w = xyz, tal que -

• | y | > 0
• | xy | ≤ c
• Para todo k ≥ 0, la cadena xy ^k z también está en L.

Aplicaciones de la lema de bombeo

Pumping Lemma debe aplicarse para demostrar que ciertos idiomas no son regulares. Nunca debe usarse para mostrar que un idioma es regular.

• Si L es regular, satisface Pumping Lemma.

• Si L no satisface el Pumping Lemma, no es regular.

Método para demostrar que una lengua L no es regular

• Al principio, tenemos que asumir que L es regular.

• Entonces, el lema de bombeo debe mantenerse para L.

• Utilice el lema de bombeo para obtener una contradicción:

  • Seleccione w tal que |w| ≥ c

  • Seleccione y tal que |y| ≥ 1

  • Seleccione x tal que |xy| ≤ c

  • Asignar la cuerda restante a z.

  • Seleccione k tal que la cadena resultante no esté en L.

Hence L is not regular.

Problem

Pruebalo L = {aⁱbⁱ | i ≥ 0} no es regular.

Solution -

• Al principio, asumimos que L es regular y n es el número de estados.

• Sea w = a ⁿ b ⁿ . Así | w | = 2n ≥ n.

• Al bombear lema, sea w = xyz, donde | xy | ≤ n.

• Sea x = a ^p , y = a ^q , yz = a ^r b ⁿ , donde p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Así | y | ≠ 0.

• Sea k = 2. Entonces xy ² z = a ^p a ^2q a ^r b ⁿ .

• Número de as = (p + 2q + r) = (p + q + r) + q = n + q

• Por tanto, xy ² z = a ^{n + q} b ⁿ . Dado que q ≠ 0, xy ² z no tiene la forma a ⁿ b ⁿ .

• Por tanto, xy ² z no está en L. Por tanto, L no es regular.