¿Cuál es el lema de bombeo en términos simples?

81

Vi esta pregunta y sentí curiosidad por saber cuál era el lema de bombeo ( Wikipedia no ayudó mucho).

Entiendo que es básicamente una prueba teórica que debe ser cierta para que un idioma esté en una determinada clase, pero más allá de eso, realmente no lo entiendo.

¿Alguien quiere tratar de explicarlo a un nivel bastante granular de una manera comprensible para los no matemáticos / doctorados en ciencias?

shsteimer
fuente
2
Tengo la firme convicción de que no hay atajos para las matemáticas / TCS: los "términos profanos" no te ayudarán a comprender. Dicho esto, por supuesto, hemos cubierto esto extensamente en Ciencias de la Computación ; ver aquí , aquí y aquí .
Raphael
1
Tenga en cuenta que se espera que los estudiantes de primer año comprendan el teorema y su demostración, y lo apliquen, de modo que la solicitud de algo "comprensible para los no [...] doctores" se cumple fácilmente consultando cualquier libro de texto de idiomas formales.
Raphael
El lema de bombeo no es una prueba: como sugiere el nombre, es un lema .
nbro

Respuestas:

157

El lema de bombeo es una prueba simple para demostrar que un lenguaje no es regular, lo que significa que no se puede construir una máquina de estados finitos para él. El ejemplo canónico es el idioma (a^n)(b^n). Este es el lenguaje simple que es cualquier número de as, seguido del mismo número de bs. Entonces las cuerdas

ab
aabb
aaabbb
aaaabbbb

etc. están en el idioma, pero

aab
bab
aaabbbbbb

etc. no lo son.

Es bastante simple construir un FSM para estos ejemplos:

FSM

Este funcionará hasta n = 4. El problema es que nuestro lenguaje no impuso ninguna restricción a n, y las máquinas de estado finito tienen que ser, bueno, finitas. No importa cuántos estados agregue a esta máquina, alguien puede darme una entrada donde n es igual al número de estados más uno y mi máquina fallará. Entonces, si se puede construir una máquina para leer este lenguaje, debe haber un bucle en algún lugar para mantener finito el número de estados. Con estos bucles agregados:

FSM 2

Se aceptarán todas las cadenas de nuestro idioma, pero hay un problema. Después de los primeros cuatro as, la máquina pierde la cuenta de cuántos as se han ingresado porque permanece en el mismo estado. Eso significa que después de cuatro, puedo agregar tantos as como quiera a la cadena, sin agregar ningún bs, y aún así obtener el mismo valor de retorno. Esto significa que las cadenas:

aaaa(a*)bbbb

con la (a*)representación de cualquier número de as, todos serán aceptados por la máquina aunque obviamente no están todos en el idioma. En este contexto, diríamos que (a*)se puede bombear la parte del hilo . El hecho de que la máquina de estados finitos sea finita yn no esté acotada, garantiza que cualquier máquina que acepte todas las cadenas en el lenguaje DEBE tener esta propiedad. La máquina debe realizar un bucle en algún punto, y en el punto en el que se repite, se puede bombear el lenguaje. Por lo tanto, no se puede construir una máquina de estados finitos para este lenguaje, y el lenguaje no es regular.

Recuerde que las Expresiones Regulares y las Máquinas de Estado Finito son equivalentes , luego reemplace ay bcon las etiquetas Html de apertura y cierre que se pueden incrustar entre sí, y puede ver por qué no es posible usar expresiones regulares para analizar Html

Noob de gráficos
fuente
2
Su segundo diagrama también es incorrecto porque puede producir baaaabbbb.
James
3
@James, eso es cierto, podría solucionarse simplemente agregando otro estado de aceptación, pero solo por simplicidad, lo dejaré como está.
Graphics Noob
1
Buena respuesta, pero no menciona que el lema de bombeo se puede usar para demostrar que un lenguaje ES libre de contexto, no solo para refutar la regularidad
MobileMon
1
Esto ni siquiera muestra de manera concluyente que a^n b^nno sea regular, ni propone una gran intuición sobre el lema del bombeo.
Raphael
1
@GraphicsNoob El lema de bombeo NO es una prueba, es un lema, como sugiere el nombre. Un lema es una proposición probada. Un lema puede pensarse como un teorema más pequeño y no tan importante, que generalmente se usa para probar o mostrar otras proposiciones o enunciados. No creo que una respuesta que comience diciendo que "el lema de bombeo es una prueba" tenga actualmente 114 votos a favor, es por eso que las preguntas y respuestas deben ser votadas con una descripción o una explicación.
nbro
15

Es un dispositivo destinado a demostrar que un idioma determinado no puede pertenecer a una clase determinada.

Consideremos el lenguaje de los paréntesis equilibrados (que significan los símbolos '(' y ')', e incluyen todas las cadenas que están equilibradas en el significado habitual y ninguna que no lo esté. Podemos usar el lema de bombeo para mostrar que esto no es regular.

(Un idioma es un conjunto de cadenas posibles. Un analizador es algún tipo de mecanismo que podemos usar para ver si una cadena está en el idioma, por lo que tiene que poder distinguir entre una cadena en el idioma o una cadena fuera el idioma. Un idioma es "regular" (o "sin contexto" o "sensible al contexto" o lo que sea) si hay un analizador regular (o lo que sea) que pueda reconocerlo, distinguiendo entre cadenas en el idioma y cadenas que no están en el idioma.)

LFSR Consulting ha proporcionado una buena descripción. Podemos dibujar un analizador para un lenguaje regular como una colección finita de cuadros y flechas, con las flechas que representan caracteres y los cuadros que los conectan (actuando como "estados"). (Si es más complicado que eso, no es un lenguaje común). Si podemos obtener una cadena más larga que el número de casillas, significa que pasamos por una casilla más de una vez. Eso significa que teníamos un bucle y podemos recorrerlo tantas veces como queramos.

Por lo tanto, para un lenguaje normal, si podemos crear una cadena arbitrariamente larga, podemos dividirla en xyz, donde x son los caracteres que necesitamos para llegar al inicio del ciclo, y es el ciclo real y z es lo que sea que Necesito hacer que la cadena sea válida después del ciclo. Lo importante es que las longitudes totales de xey son limitadas. Después de todo, si la longitud es mayor que el número de cajas, obviamente hemos pasado por otra caja mientras hacíamos esto, y entonces hay un bucle.

Entonces, en nuestro lenguaje equilibrado, podemos comenzar escribiendo cualquier número de paréntesis izquierdos. En particular, para cualquier analizador, podemos escribir más parientes izquierdos que cuadros, por lo que el analizador no puede decir cuántos parientes izquierdos hay. Por lo tanto, x es una cierta cantidad de parientes izquierdos, y esto es fijo. y también es un número de parientes izquierdos, y esto puede aumentar indefinidamente. Podemos decir que z es un número de parientes derechos.

Esto significa que podríamos tener una cadena de 43 paréntesis izquierdos y 43 parientes derechos reconocidos por nuestro analizador, pero el analizador no puede distinguir eso de una cadena de 44 paréntesis izquierdos y 43 paréntesis derechos, que no está en nuestro idioma, así que el analizador no puede analizar nuestro idioma.

Dado que cualquier posible analizador normal tiene un número fijo de casillas, siempre podemos escribir más paréntesis izquierdos que ese, y mediante el lema de bombeo podemos agregar más paréntesis izquierdos de una manera que el analizador no puede distinguir. Por lo tanto, el lenguaje de paréntesis equilibrado no puede ser analizado por un analizador regular y, por lo tanto, no es una expresión regular.

David Thornley
fuente
Excelente respuesta y lectura para aquellos que buscan capturar cadenas equilibradas con expresiones regulares.
Justin Johnson
9

Es algo difícil de entender en términos sencillos, pero básicamente las expresiones regulares deben tener una subcadena no vacía dentro de ella que pueda repetirse tantas veces como desee mientras toda la palabra nueva sigue siendo válida para el idioma.

En la práctica , los lemas de bombeo no son suficientes para DEMOSTRAR que un lenguaje es correcto, sino más bien como una forma de hacer una prueba por contradicción y mostrar que un idioma no encaja en la clase de idiomas (regular o libre de contexto) mostrando que el lema de bombeo sí no funciona para ello.

Alexwood
fuente
¿Qué quiere decir con "no es suficiente para PROBAR que un idioma es correcto"? Por "correcto" supongo que te refieres a regular. De hecho, un lenguaje regular exhibe la propiedad de bombeo, pero si un lenguaje exhibe la propiedad de bombeo, no significa necesariamente que sea regular. Por otro lado, si el lenguaje no exhibe la propiedad de bombeo, entonces estamos seguros de que no es regular. Básicamente, la propiedad de bombeo es necesaria pero no suficiente para demostrar que un idioma es regular.
nbro
4

Básicamente, tiene una definición de un idioma (como XML), que es una forma de saber si una determinada cadena de caracteres (una "palabra") es miembro de ese idioma o no.

El lema de bombeo establece un método mediante el cual puede elegir una "palabra" del idioma y luego aplicarle algunos cambios. El teorema establece que si el idioma es regular, estos cambios deberían producir una "palabra" que todavía es del mismo idioma. Si la palabra que se te ocurrió no está en el idioma, entonces el idioma no podría haber sido regular en primer lugar.

Welbog
fuente
3

El lema de bombeo simple es el de los lenguajes regulares, que son los conjuntos de cadenas descritos por autómatas finitos, entre otras cosas. La principal característica de una automatización finita es que solo tiene una cantidad finita de memoria, descrita por sus estados.

Ahora suponga que tiene una cadena, que es reconocida por un autómata finito, y que es lo suficientemente larga para "exceder" la memoria de la automatización, es decir, en qué estados deben repetirse. Luego hay una subcadena donde el estado del autómata al comienzo de la subcadena es el mismo que el estado al final de la subcadena. Dado que la lectura de la subcadena no cambia el estado, puede eliminarse o duplicarse un número arbitrario de veces, sin que el autómata se dé cuenta. Por lo tanto, estas cadenas modificadas también deben aceptarse.

También hay un lema de bombeo algo más complicado para los lenguajes sin contexto, donde puede eliminar / insertar lo que intuitivamente puede verse como paréntesis coincidentes en dos lugares de la cadena.

estrella azul
fuente
Su segundo párrafo es bueno, pero el primero es un poco malo: "El lema de bombeo simple es el de los lenguajes regulares". ¿Es el de los lenguajes regulares para hacer qué? ¿Por qué necesitamos el lema de bombeo? ¿Cuál es la relación entre el lema de bombeo y ser un lenguaje regular? Debería responder a todas estas preguntas, en mi opinión.
nbro
@starblue: ¿Podría decirnos por qué? Si el idioma es $ {a} $, la duración mínima de bombeo es $ 2 $; si el idioma es $ {a ^ n: n∈ℕ} $, entonces la longitud mínima de bombeo es $ 1 $ .más aquí :( math.stackexchange.com/questions/1508471/minimum-pumping-length/… ).
justin
0

Por definición, los lenguajes regulares son aquellos reconocidos por un autómata de estado finito. Piense en ello como un laberinto: los estados son habitaciones, las transiciones son pasillos de un solo sentido entre habitaciones, hay una habitación inicial y una sala de salida (final). Como dice el nombre "autómata de estado finito", hay un número finito de habitaciones. Cada vez que recorre un pasillo, anota la letra escrita en su pared. Se puede reconocer una palabra si se puede encontrar un camino desde la habitación inicial hasta la última, pasando por pasillos etiquetados con sus letras, en el orden correcto.

El lema de bombeo dice que hay una longitud máxima (la longitud de bombeo) por la cual puedes deambular por el laberinto sin tener que volver a una habitación por la que has pasado antes. La idea es que, dado que solo hay un número limitado de habitaciones distintas en las que puede caminar, más allá de cierto punto, debe salir del laberinto o cruzar las vías. Si logra caminar un camino más largo que esta longitud de bombeo en el laberinto, entonces está tomando un desvío: está insertando un (al menos un) ciclo en su camino que podría eliminarse (si desea que su cruce del laberinto sea reconocer una palabra más pequeña) o repetida (bombeada) indefinidamente (permitiendo reconocer una palabra superlarga).

Existe un lema similar para los lenguajes libres de contexto. Esos lenguajes se pueden representar como palabra aceptada por autómatas pushdown, que son autómatas de estado finito que pueden hacer uso de una pila para decidir qué transiciones realizar. No obstante, dado que todavía hay un número finito de estados, la intuición explicada anteriormente se traslada, incluso a través de la expresión formal de la propiedad puede ser un poco más compleja .

Francois G
fuente
@Buscando una respuesta como esta. ¿Podrían ser iguales la sala inicial y la final? Estoy atascado con este comentario: si el idioma es $ {a} $, la longitud mínima de bombeo es $ 2 $; si el idioma es $ {a ^ n: n∈N} $, entonces la longitud mínima de bombeo es $ 1 $. ¿Podrían ayudarme más aquí :( math.stackexchange.com/questions/1508471/minimum-pumping-length /… ).
Justin
0

En términos sencillos, creo que lo tienes casi bien. Es una técnica de prueba (dos en realidad) para probar que un idioma NO pertenece a una determinada clase.

Por ejemplo, considere un lenguaje regular (regexp, autómatas, etc.) con un número infinito de cadenas. En cierto momento, como dijo starblue, te quedas sin memoria porque la cuerda es demasiado larga para el autómata. Esto significa que tiene que haber un trozo de la cadena que el autómata no pueda decir cuántas copias tiene (estás en un bucle). Entonces, cualquier número de copias de esa subcadena en el medio de la cadena, y todavía estás en el idioma.

Esto significa que si tiene un idioma que NO tiene esta propiedad, es decir, hay una cadena lo suficientemente larga SIN subcadena que puede repetir cualquier número de veces y aún estar en el idioma, entonces el idioma no es regular.

Brian Postow
fuente
La última oración, al menos, es falsa. El lenguaje que consiste en la cadena "a" es normal, pero no puede bombearlo. Si puedes bombear una cuerda de cierta manera, no es regular. Por ejemplo, el lenguaje con los símbolos '(' y ')', formado por todas las expresiones equilibradas (y no desequilibradas) no es regular, y lo demuestra pulsando "()".
David Thornley
@David, gracias, corrigió la última oración. Pero creo que te equivocas acerca de los parens equilibrados. No creo que pueda probar que los padres no son regulares mediante el bombeo del lema. Creo que las bombas de parens.
Brian Postow
0

Por ejemplo, tome este lenguaje L = a n b n .

Ahora intente visualizar un autómata finito para el lenguaje anterior para algunas n .

si n = 1, la cadena w = ab . Aquí podemos hacer un autómata finito sin bucles si n = 2, la cadena w = a 2 b 2 . Aquí podemos hacer un autómata finito sin bucles

si n = p , la cadena w = a p b p . Esencialmente, se puede suponer un autómata finito con 3 etapas. Primera etapa, toma una serie de entradas y entra en la segunda etapa. De manera similar, de la etapa 2 a la etapa 3. Llamemos a estas etapas como x , y y z .

Hay algunas observaciones

  1. Definitivamente x contendrá 'a' yz contendrá 'b'.
  2. Ahora tenemos que tener claro y :
    • caso a : y puede contener solo 'a'
    • caso b : y solo puede contener 'b'
    • caso c : y puede contener una combinación de 'a' y 'b'

Entonces, los estados de autómatas finitos para la etapa y deberían poder tomar las entradas 'a' y 'b' y tampoco deberían tomar más a y b que no pueden ser contables.

  1. Si la etapa y toma solo una 'a' y una 'b', entonces se requieren dos estados
  2. Si toma dos 'a' y una 'b', se requieren tres estados sin bucles y así sucesivamente ....

Entonces, el diseño de la etapa y es puramente infinito. Solo podemos hacerlo finito poniendo algunos bucles y si ponemos bucles, el autómata finito puede aceptar lenguajes más allá de L = a n b n . Entonces, para este lenguaje no podemos construir un autómata finito. Por tanto, no es regular.

Sajeev Ramakrishnan
fuente
-1

Esta no es una explicación como tal, pero es simple. Para a ^ nb ^ n, nuestro FSM debe construirse de tal manera que b debe conocer el número de a ya analizado y aceptará el mismo n número de b. Un FSM no puede simplemente hacer cosas así.

SMUsamaShah
fuente