Lema
Si L es un lenguaje libre de contexto, hay una duración de bombeo p tal que cualquier cuerda w ∈ L de longitud ≥ p Se puede escribir como w = uvxyz, dónde vy ≠ ε, |vxy| ≤ py para todos i ≥ 0, uvixyiz ∈ L.
Aplicaciones de la lema de bombeo
El lema de bombeo se utiliza para comprobar si una gramática está libre de contexto o no. Tomemos un ejemplo y mostremos cómo se verifica.
Problema
Descubra si el idioma L = {xnynzn | n ≥ 1} es libre de contexto o no.
Solución
Dejar Les libre de contexto. Luego,L debe satisfacer el lema de bombeo.
Primero, elige un número ndel lema de bombeo. Luego, toma z como 0 n 1 n 2 n .
Descanso z dentro uvwxy, dónde
|vwx| ≤ n and vx ≠ ε.
Por lo tanto vwxno puede involucrar tanto 0 como 2, ya que el último 0 y los primeros 2 están separados por al menos (n + 1) posiciones. Hay dos casos:
Case 1 - vwxno tiene 2. Luegovxtiene solo 0 y 1. Luegouwy, que tendría que estar en L, tiene n 2 s, pero menos de n 0 o 1.
Case 2 - vwx no tiene ceros.
Aquí ocurre la contradicción.
Por lo tanto, L no es un lenguaje libre de contexto.