¿Cómo puede usar el lema de bombeo para demostrar que un idioma no es regular?

El lema de bombeo para idiomas regulares es una herramienta poderosa para demostrar que un idioma es * no * regular. Funciona por contradicción:supone que el idioma * es * regular, luego demuestra que esta suposición conduce a una contradicción del lema mismo. Así es como funciona:

1. La declaración de lema de bombeo:

El lema de bombeo establece que para cualquier idioma regular l, existe una longitud de bombeo P tal que cualquier cadena w en l con longitud | w | ≥ P se puede dividir en tres subcadenas, w =xyz, satisfaciendo las siguientes condiciones:

* | xy | ≤ P: La longitud de la concatenación de x e y es menor o igual a p.

* | y |> 0: La subcadena y no está vacía.

* Para todos los i ≥ 0, xy i z ∈ L: Bombear y cero o más veces (incluido la eliminación por completo cuando i =0) da como resultado una cadena que todavía está en el lenguaje L.

2. Estrategia de prueba:

Para demostrar que un idioma L no es regular usando el lema de bombeo, siga estos pasos:

* Suponga que L es regular: Comience asumiendo, en aras de la contradicción, que L es un idioma regular.

* Elija una longitud de bombeo P: El lema de bombeo garantiza la existencia de una longitud de bombeo p; No necesita encontrar su valor real, solo consulte a él como 'P'.

* Elija una cadena w ∈ L tal que | w | ≥ P: Seleccione cuidadosamente una cadena W del idioma l cuya longitud es al menos p. La elección de W es crucial; Debe permitirle crear una contradicción en el siguiente paso. Esto a menudo involucra cadenas con una estructura específica relacionada con la definición del lenguaje.

* Demuestre que ninguna descomposición w =xyz satisface las condiciones de lema de bombeo: Este es el corazón de la prueba. Para * cualquier * posible descomposición de w en xyz satisfacer | xy | ≤ P y | y |> 0, debes demostrar que existe algunos I ≥ 0 tal que xy i Z ∉ L. Esto significa que el bombeo y viola la definición del lenguaje L. A menudo, demuestra esto al mostrar que el bombeo Y tampoco lo hará:

* Introducir un desequilibrio: Cambie el número de ocurrencias de algún símbolo, violando una restricción de conteo en L.

* Crear una estructura inválida: Romper el patrón o estructura requerida por la definición de L.

* Introducir una subcadena inválida: Cree una subcadena que no pertenezca al idioma.

* concluye que L no es regular: Dado que ha demostrado que no puede existir tal descomposición para la cadena elegida W, esto contradice el lema de bombeo. Por lo tanto, la suposición inicial de que L es regular debe ser falsa, y L no es regular.

Ejemplo:Probando {a n b n | n ≥ 0} no es regular:

Sea l ={a ^{n b n | n ≥ 0}.}

1. Suponga que L es regular.

2. Elija P: Deje que P sea la longitud de bombeo.

3. Elija W: Deje w =a ^{p B P . Claramente, w ∈ L y | W | ≥ p.}

4. no muestra descomposición satisface las condiciones: Consideremos cualquier descomposición w =xyz tal que | xy | ≤ P y | y |> 0. Desde | xy | ≤ P, y debe consistir * solo * de A (porque Y es una subcadena de los primeros personajes P). Por lo tanto, y =a ^{k Para algunos k> 0. Ahora, bomba y cero veces:xy 0 z =a P-K B P . Esta cadena no está en L porque el número de A y B son diferentes. Esto contradice el lema de bombeo.}

5. Concluir: Como hemos alcanzado una contradicción, nuestra suposición de que L es regular debe ser falsa. Por lo tanto, l ={a n b n | n ≥ 0} no es un idioma regular.

La clave es elegir cuidadosamente la cadena `W` y analizar inteligentemente todas las posibles descomposiciones` xyz` para mostrar que el bombeo `y` siempre conduce a una cadena fuera del idioma. Cuanto más complejo sea el lenguaje, más intrincada es la elección de `w` y el análisis.