Lema de bombeo para CFG

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, uvⁱxyⁱz ∈ 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 = {xⁿyⁿzⁿ | 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 ⁿ 1 ⁿ 2 ⁿ .

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.