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

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?

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:

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:

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

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.

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.

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.

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.

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 .

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.

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

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 ² b ² . 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 ⁿ b ⁿ . Entonces, para este lenguaje no podemos construir un autómata finito. Por tanto, no es regular.

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í.