theory - pumping - ¿Qué es el lema de bombeo en términos de Layman?

pumping lemma (9)

Básicamente, tiene una definición de un idioma (como XML), que es una manera de saber si una cadena dada 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 lenguaje es regular, estos cambios deberían producir una "palabra" que aún proviene del mismo idioma. Si la palabra que se te ocurre no está en el idioma, entonces el idioma no pudo haber sido regular en primer lugar.

Vi esta pregunta y tenía curiosidad sobre cuál era el lema del bombeo ( Wikipedia no ayudó mucho).

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

¿Alguien trata de explicarlo en un nivel bastante detallado de una manera comprensible para los doctorados no matemáticos / de ciencia ficción?

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 supongamos que tiene una cuerda, que es reconocida por un autómata finito, y que es lo suficientemente larga como para "exceder" la memoria de la automatización, es decir, en la que los 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. Como la lectura de la subcadena no cambia el estado, puede eliminarse o duplicarse un número arbitrario de veces, sin que el autómata sea más inteligente. Entonces estas cadenas modificadas también deben ser aceptadas.

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.

En términos simples, creo que lo tienes casi correcto. Es una técnica de prueba (dos en realidad) para probar que un idioma NO está en cierta clase.

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

Esto significa que si tiene un idioma que NO tiene esta propiedad, es decir, hay una cadena suficientemente larga con ninguna subcadena que puede repetir cualquier número de veces y aún estar en el idioma, entonces el idioma no es 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 nueva palabra siga siendo válida para el idioma.

En la práctica , los lemmas de bombeo no son suficientes para PROBAR un lenguaje correcto, sino como una forma de demostrar por contradicción y mostrar que un idioma no encaja en la clase de idiomas (Regular o Sin contexto) al mostrar el lema de bombeo no trabajar para eso.

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

Consideremos el lenguaje de paréntesis equilibrados (es decir, símbolos ''('' y '')'', e incluyendo 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 sintáctico es un tipo de mecanismo que podemos usar para ver si una cadena está en el idioma, por lo que debe poder distinguir la diferencia entre una cadena en el idioma o una cadena externa el lenguaje. 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 lenguaje y cadenas no 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 representando los caracteres y los cuadros que los conectan (actuando como "estados"). (Si es más complicado que eso, no es un lenguaje normal.) Si podemos obtener una cadena más larga que el número de cajas, significa que hemos pasado por una caja más de una vez. Eso significa que teníamos un bucle, y podemos pasar por el bucle 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, yz es lo que sea necesidad de 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 la cantidad de cuadros, obviamente hemos pasado por otra casilla mientras hacemos esto, y entonces hay un ciclo.

Entonces, en nuestro lenguaje equilibrado, podemos comenzar escribiendo cualquier número de paréntesis izquierdos. En particular, para cualquier analizador dado, podemos escribir más paréntesis 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 paréntesis izquierdos, y esto es fijo. y es también una cierta cantidad de pares izquierdos, y esto puede aumentar indefinidamente. Podemos decir que z es una cierta cantidad de parens derechos.

Esto significa que podríamos tener una cadena de 43 parens izquierdos y 43 parens derechos reconocidos por nuestro analizador sintáctico, pero el analizador sintáctico no puede decir eso a partir de una cadena de 44 parens izquierdos y 43 parens derechos, que no está en nuestro idioma, por lo el analizador no puede analizar nuestro lenguaje.

Dado que cualquier analizador sintáctico posible tiene un número fijo de casillas, siempre podemos escribir más paréntesis izquierdos que eso, y mediante el lema de bombeo podemos agregar más paréntesis izquierdos de una manera que el analizador no puede decir. 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.

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

Por definición, los lenguajes regulares son aquellos reconocidos por un autómata de estado finito. Piénselo como un laberinto: los estados son habitaciones, las transiciones son corredores de sentido único entre habitaciones, hay una sala 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 viajas por un pasillo, anotas la carta escrita en su pared. Se puede reconocer una palabra si puede encontrar un camino desde la habitación inicial hasta la habitación final, pasando por los 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 que puede pasear por el laberinto sin tener que volver a una habitación a través de la cual se haya ido antes. La idea es que, dado que solo hay tantas habitaciones distintas que puedes entrar, más allá de cierto punto, tienes que 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 ciclo (por lo menos uno) en su camino que podría eliminarse (si desea que su cruce del laberinto reconocer una palabra más pequeña) o repetida (bombeada) indefinidamente (lo que permite reconocer una palabra súper larga).

Hay un lema similar para los lenguajes sin contexto. Esos idiomas se pueden representar como palabra aceptada por pushdown autómatas, que son autómatas de estados finitos que pueden usar una pila para decidir qué transiciones realizar. No obstante, dado que hay una cantidad limitada 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 .

Por ejemplo, tome este lenguaje L = a ^ nb ^ n

Ahora intenta visualizar el 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 bucle si n = 2, la cadena w = a ^ 2b ^ 2. Aquí podemos hacer un autómata finito sin bucle

si n = p, la cadena w = a ^ pb ^ 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. Del mismo modo, desde la etapa 2 hasta 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 ser claros sobre y case a. y puede contener ''a'' solo caso b. y puede contener ''b'' solo caso c. y puede contener una combinación de ''a'' y ''b'' Entonces los estados autómatas finitos para la etapa y deberían poder tomar las entradas ''a'' y ''b'' y también no deberían tomar más a''s y b''s que no pueden contabilizarse.

Si la etapa y está tomando solo una ''a'' y una ''b'', entonces se requieren dos estados
Si está tomando dos ''a'' y una ''b'', se requieren tres estados con bucles de salida, etc.

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 idiomas más allá de L = a ^ nb ^ n. Entonces para este lenguaje no podemos construir un autómata finito. Por lo tanto, no es regular.

El lema de bombeo es una prueba simple para mostrar que un idioma no es regular, lo que significa que no se puede construir una Máquina de estados finitos. El ejemplo canónico es el lenguaje (a^n)(b^n) . Este es el lenguaje simple que es cualquier número de a , seguido de la misma cantidad de b s. Entonces las cuerdas

ab aabb aaabbb aaaabbbb

etc. están en el idioma, pero

aab bab aaabbbbbb

etc. no lo son

Es lo suficientemente simple como para construir un FSM para estos ejemplos:

Este funcionará hasta n = 4. El problema es que nuestro lenguaje no puso ninguna restricción en n, y las máquinas de estados finitos tienen que ser, bueno, finitas. No importa cuántos estados agregue a esta máquina, alguien me puede dar una entrada donde n es igual al número de estados más uno y mi máquina fallará. Entonces, si puede haber una máquina construida para leer este idioma, debe haber un bucle en algún lugar para mantener la cantidad de estados finitos. Con estos bucles añadidos:

todas las cuerdas en nuestro idioma serán aceptadas, pero hay un problema. Después de las primeras cuatro a s, la máquina pierde el recuento de cuántas se han ingresado porque permanece en el mismo estado. Eso significa que después de las cuatro, puedo agregar tantas como quiera a la cadena, sin agregar ninguna b s, y obtener el mismo valor de retorno. Esto significa que las cadenas:

aaaa(a*)bbbb

con (a*) representa cualquier número de a , todo será aceptado por la máquina a pesar de que obviamente no están todos en el idioma. En este contexto, diríamos que la parte de la cadena (a*) puede ser bombeada. El hecho de que la máquina de estados finitos es finita y n no está limitada, garantiza que cualquier máquina que acepte todas las cadenas en el idioma DEBE tener esta propiedad. La máquina debe realizar un bucle en algún punto, y en el punto en que bucles se puede bombear el idioma. Por lo tanto, no se puede construir una Máquina de estados finitos para este idioma, y el idioma no es regular.

Recuerde que las expresiones regulares y las máquinas de estados finitos son equivalentes , luego reemplace b con las etiquetas Html de apertura y cierre que pueden integrarse entre sí, y puede ver por qué no es posible usar expresiones regulares para analizar Html