Lema de bombeo para lenguajes regulares

En la teoría de lenguajes formales , el lema de bombeo para lenguajes regulares describe una propiedad esencial de todos ellos . En términos informales, afirma que cualquier cadena suficientemente larga en un lenguaje regular puede ser bombeada —es decir, se puede repetir una sección central un número arbitrario de veces— para generar una nueva cadena que también pertenece al lenguaje. El lema de bombeo resulta útil para demostrar que un lenguaje específico no es regular, al mostrar que carece de dicha propiedad.

Específicamente, el lema de bombeo dice que para cualquier lenguaje regular${\displaystyle L}$, existe una constante${\displaystyle p}$de tal manera que cualquier cadena${\displaystyle w}$en${\displaystyle L}$con una longitud al menos${\displaystyle p}$se puede dividir en tres subcadenas${\displaystyle x}$,${\displaystyle y}$y${\displaystyle z}$(${\displaystyle w=xyz}$, con${\displaystyle y}$siendo no vacías), de tal manera que las cadenas${\displaystyle xz,xyz,xyyz,xyyyz,...}$también están en${\displaystyle L}$. El proceso de repetición${\displaystyle y}$cero o más veces se conoce como "bombeo". Además, el lema de bombeo garantiza que la longitud de${\displaystyle xy}$será como máximo${\displaystyle p}$, dando así una subcadena "pequeña"${\displaystyle xy}$que tenga la propiedad deseada.

Los lenguajes con un número finito de cadenas satisfacen trivialmente el lema de bombeo al tener${\displaystyle p}$igual a la longitud máxima de la cadena en${\displaystyle L}$más uno. Al hacerlo, no hay ninguna cuerda en absoluto en${\displaystyle L}$tener longitud al menos${\displaystyle p}$.

El lema de bombeo fue demostrado por primera vez por Michael Rabin y Dana Scott en 1959, ^{[ 1 ]} y redescubierto poco después por Yehoshua Bar-Hillel , Micha A. Perles y Eli Shamir en 1961, como una simplificación de su lema de bombeo para lenguajes libres de contexto . ^{[ 2 ] [ 3 ]}

Dejar${\displaystyle L}$sea ​​un lenguaje regular. Entonces existe un número entero${\displaystyle p\geq 1}$dependiendo únicamente de${\displaystyle L}$de tal manera que cada cuerda${\displaystyle w}$en${\displaystyle L}$de longitud al menos${\displaystyle p}$(${\displaystyle p}$se denomina "longitud de bombeo" ^{[ 4 ]} y se puede escribir como${\displaystyle w=xyz}$(es decir,${\displaystyle w}$puede dividirse en tres subcadenas), que satisfacen las siguientes condiciones:

1. ${\displaystyle |y|\geq 1}$
2. ${\displaystyle |xy|\leq p}$
3. ${\displaystyle (\forall n\geq 0)(xy^{n}z\in L)}$

${\displaystyle y}$es la subcadena que se puede bombear (eliminar o repetir cualquier número de veces, y la cadena resultante siempre está en${\displaystyle L}$). (1) significa el bucle${\displaystyle y}$para ser bombeado debe tener una longitud de al menos uno, es decir, no una cadena vacía; (2) significa que el bucle debe ocurrir dentro del primero${\displaystyle p}$personajes.${\displaystyle |x|}$debe ser más pequeño que${\displaystyle p}$(conclusión de (1) y (2)), pero aparte de eso, no hay ninguna restricción en${\displaystyle x}$y${\displaystyle z}$.

En pocas palabras, para cualquier lenguaje regular${\displaystyle L}$cualquier cadena suficientemente larga${\displaystyle w}$(en${\displaystyle L}$) se puede dividir en 3 partes, es decir${\displaystyle w=xyz}$, de tal manera que todas las cadenas${\displaystyle xy^{n}z}$para${\displaystyle n\geq 0}$también están en${\displaystyle L}$.

A continuación se presenta una expresión formal del lema de bombeo.

${\displaystyle {\begin{array}{l}\forall L\subseteq \Sigma ^{*},{\mbox{regular}}(L)\implies \\\quad \exists p\geq 1,\forall w\in L,|w|\geq p\implies \\\qquad \exists x,y,z\in \Sigma ^{*},(w=xyz)\land (|y|\geq 1)\land (|xy|\leq p)\land (\forall n\geq 0,xy^{n}z\in L)\end{array}}}$

El lema de bombeo se usa a menudo para demostrar que un lenguaje en particular no es regular: una prueba por contradicción puede consistir en mostrar una cadena (de la longitud requerida) en el lenguaje que carece de la propiedad descrita en el lema de bombeo.

Ejemplo: El idioma${\displaystyle L=\{a^{n}b^{n}:n\geq 0\}}$sobre el alfabeto${\displaystyle \Sigma =\{a,b\}}$Se puede demostrar que no es regular de la siguiente manera:

1. Supongamos que alguna constante${\displaystyle p\geq 1}$existe según lo exige el lema.
2. Dejar${\displaystyle w}$en${\displaystyle L}$ser dado por${\displaystyle w=a^{p}b^{p}}$, que es una cadena más larga que${\displaystyle p}$.
3. Según el lema de bombeo, debe existir una descomposición.${\displaystyle w=xyz}$con${\displaystyle |xy|\leq p}$y${\displaystyle |y|\geq 1}$de tal manera que${\displaystyle xy^{i}z}$en${\displaystyle L}$por cada${\displaystyle i\geq 0}$.
4. Desde${\displaystyle |xy|\leq p}$, la cadena${\displaystyle y}$solo consta de instancias de${\displaystyle a}$.
5. Porque${\displaystyle |y|\geq 1}$, contiene al menos una instancia de la letra${\displaystyle a}$.
6. Bombeo${\displaystyle y}$dar${\displaystyle xy^{2}z}$da una palabra con más instancias de la letra${\displaystyle a}$que la carta${\displaystyle b}$, ya que algunos casos de${\displaystyle a}$pero ninguno de${\displaystyle b}$se añadieron.
7. Por lo tanto,${\displaystyle xy^{2}z}$no está en${\displaystyle L}$lo cual contradice el lema de bombeo.
8. Por lo tanto,${\displaystyle L}$no puede ser regular.

La prueba de que el lenguaje de paréntesis balanceados (es decir, anidados correctamente) no es regular sigue la misma idea. Dado${\displaystyle p}$, hay una serie de paréntesis equilibrados que comienza con más de${\displaystyle p}$paréntesis izquierdos, de modo que${\displaystyle y}$consistirá enteramente en paréntesis izquierdos. Al repetir${\displaystyle y}$Se puede producir una cadena que no contenga el mismo número de paréntesis izquierdos y derechos, por lo que no se pueden equilibrar.

Para cada lenguaje regular existe un autómata de estados finitos (AEF) que acepta dicho lenguaje. Se cuenta el número de estados en dicho AEF y ese conteo se utiliza como la longitud de bombeo.${\displaystyle p}$. Para una cadena de longitud al menos${\displaystyle p}$, dejar${\displaystyle q_{0}}$sea ​​el estado inicial y deje que${\displaystyle q_{1},...,q_{p}}$ser la secuencia del siguiente${\displaystyle p}$estados visitados a medida que se emite la cadena. Porque el FSA solo tiene${\displaystyle p}$estados, dentro de esta secuencia de${\displaystyle p+1}$De los estados visitados, debe haber al menos un estado que se repita. Escribe${\displaystyle q_{s}}$para tal estado. Las transiciones que llevan a la máquina desde el primer encuentro del estado${\displaystyle q_{s}}$al segundo encuentro de estado${\displaystyle q_{s}}$coincide con alguna cadena. Esta cadena se llama${\displaystyle y}$en el lema, y ​​dado que la máquina coincidirá con una cadena sin la${\displaystyle y}$porción, o con la cuerda${\displaystyle y}$Si se repite cualquier número de veces, se cumplen las condiciones del lema.

Por ejemplo, la siguiente imagen muestra un FSA.

El FSA acepta la cadena: abcd . Dado que esta cadena tiene una longitud al menos igual al número de estados, que es cuatro (por lo que el número total de estados por los que pasa la máquina para escanear abcd sería 5), ​​el principio del palomar indica que debe haber al menos un estado repetido entre el estado inicial y los siguientes cuatro estados visitados. En este ejemplo, solo${\displaystyle q_{1}}$es un estado repetido. Dado que la subcadena bc lleva a la máquina a través de transiciones que comienzan en el estado${\displaystyle q_{1}}$y terminar en el estado${\displaystyle q_{1}}$, esa porción podría repetirse y el FSA aún aceptaría, dando la cadena abcbcd . Alternativamente, la porción bc podría eliminarse y el FSA aún aceptaría, dando la cadena ad . En términos del lema de bombeo, la cadena abcd se divide en una${\displaystyle x}$porción a , una${\displaystyle y}$porción bc y a${\displaystyle z}$porción d .

Como comentario adicional, el problema de comprobar si una cadena dada puede ser aceptada por un autómata finito no determinista dado sin visitar ningún estado repetidamente, es NP-difícil .

Si un idioma${\displaystyle L}$es regular, entonces existe un número${\displaystyle p\geq 1}$(la longitud de bombeo) de tal manera que cada cuerda${\displaystyle uwv}$en${\displaystyle L}$con${\displaystyle |w|\geq p}$puede escribirse en la forma

${\displaystyle uwv=uxyzv}$

con cuerdas${\displaystyle x}$,${\displaystyle y}$y${\displaystyle z}$de tal manera que${\displaystyle |xy|\leq p}$,${\displaystyle |y|\geq 1}$y

${\displaystyle uxy^{i}zv}$está en${\displaystyle L}$para cada entero${\displaystyle i\geq 0}$. ^{[ 5 ]}

A partir de esto, la versión estándar anterior sigue un caso especial, con ambos${\displaystyle u}$y${\displaystyle v}$siendo la cadena vacía.

Dado que la versión general impone requisitos más estrictos al lenguaje, puede utilizarse para demostrar la no regularidad de muchos más lenguajes.

Si bien el lema del bombeo afirma que todos los lenguajes regulares satisfacen las condiciones descritas anteriormente, lo contrario no es cierto: un lenguaje que satisface estas condiciones aún puede ser no regular. En otras palabras, tanto la versión original como la general del lema del bombeo proporcionan una condición necesaria , pero no suficiente, para que un lenguaje sea regular.

Por ejemplo, considere el siguiente lenguaje:

${\displaystyle {\begin{matrix}L&=&\{uvwxy:u,y\in \{0,1,2,3\}^{*};v,w,x\in \{0,1,2,3\}\land (v=w\lor v=x\lor x=w)\}\\&&\cup \ \{w:w\in \{0,1,2,3\}^{*}\land {\text{precisely }}{\tfrac {1}{7}}{\text{ of the characters in }}w{\text{ are 3's}}\}\end{matrix}}}$.

En otras palabras,${\displaystyle L}$contiene todas las cadenas sobre el alfabeto${\displaystyle \{0,1,2,3\}}$con una subcadena de longitud 3 que incluye un carácter duplicado, así como todas las cadenas sobre este alfabeto donde precisamente 1/7 de los caracteres de la cadena son 3. Este lenguaje no es regular pero aún puede ser "bombeado" con${\displaystyle p=5}$Supongamos que una cadena s tiene una longitud de al menos 5. Entonces, dado que el alfabeto solo tiene cuatro caracteres, al menos dos de los primeros cinco caracteres de la cadena deben ser duplicados. Están separados por como máximo tres caracteres.

• Si los caracteres duplicados están separados por 0 o 1 caracteres, inserte uno de los otros dos caracteres de la cadena, lo que no afectará a la subcadena que contiene los duplicados.
• Si los caracteres duplicados están separados por 2 o 3 caracteres, se eliminan 2 de los caracteres que los separan. Al eliminar o aumentar los caracteres, se crea una subcadena de tamaño 3 que contiene 2 caracteres duplicados.
• La segunda condición de${\displaystyle L}$garantiza que${\displaystyle L}$no es regular: Considere la cadena${\displaystyle (013)^{3m}(012)^{i}}$Esta cadena está en${\displaystyle L}$exactamente cuando${\displaystyle i=4m}$y por lo tanto${\displaystyle L}$no es regular según el teorema de Myhill-Nerode .

El teorema de Myhill-Nerode proporciona una prueba que caracteriza con precisión los lenguajes regulares. El método típico para demostrar que un lenguaje es regular consiste en construir una máquina de estados finitos o una expresión regular para dicho lenguaje.

• El lema de Ogden
• Lema de bombeo para lenguajes libres de contexto
• Lema de bombeo para lenguajes de árboles regulares

• Lawson, Mark V. (2004). Autómatas finitos . Chapman and Hall/CRC. ISBN 978-1-58488-255-8. Zbl 1086.68074 . 
• Sipser, Michael (1997). «1.4: Lenguajes no regulares». Introducción a la teoría de la computación . PWS Publishing. págs. 77–83 . ISBN  978-0-534-94728-6. Zbl 1169.68300 . 
• Hopcroft, John E.; Ullman , Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación . Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl 0426.68001 . (Véase el capítulo 3.)
• Bakhadyr Khoussainov; Anil Nerode (6 de diciembre de 2012). Teoría de autómatas y sus aplicaciones . Springer Science & Business Media. ISBN 978-1-4612-0171-7.