En la teoría de los lenguajes formales , el lema de bombeo de los lenguajes regulares es un lema que describe una propiedad esencial de todos los lenguajes regulares . De manera informal, dice que todas las palabras lo suficientemente largas en un idioma regular pueden bombearse —es decir, hacer que una sección intermedia de la palabra se repita un número arbitrario de veces— para producir una nueva palabra que también se encuentre dentro del mismo idioma.
Específicamente, el lema de bombeo dice que para cualquier idioma regular existe una constante tal que cualquier palabra en con longitud al menos se puede dividir en tres subcadenas, , donde la parte del medio no debe estar vacío, de modo que las palabras construido repitiendo cero o más veces todavía están en . Este proceso de repetición se conoce como "bombeo". Además, el lema de bombeo garantiza que la longitud de será como máximo , imponiendo un límite a las formas en que puede estar dividido. Los lenguajes finitos satisfacen vacuamente el lema de bombeo al tener igual a la longitud máxima de la cuerda en mas uno.
El lema de bombeo es útil para refutar la regularidad de un idioma específico en cuestión. Fue probado 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]
Declaración formal
Dejar ser un idioma habitual. Entonces existe un entero dependiendo solo de tal que cada cuerda en de longitud al menos (se llama "longitud de bombeo") [4] se puede escribir como (es decir, se puede dividir en tres subcadenas), cumpliendo las siguientes condiciones:
es la subcadena que se puede bombear (eliminar o repetir cualquier número de veces, y la cadena resultante siempre está en ). (1) significa el buclepara ser bombeado debe tener una longitud de al menos uno; (2) significa que el bucle debe ocurrir dentro del primer caracteres. debe ser menor que (conclusión de (1) y (2)), pero aparte de eso, no hay restricción en y .
En palabras sencillas, para cualquier idioma habitual , cualquier palabra lo suficientemente larga (en ) se puede dividir en 3 partes. es decir , tal que todas las cuerdas por también están en .
A continuación se muestra una expresión formal del lema de bombeo.
Uso del lema
El lema de bombeo se utiliza a menudo para demostrar que un idioma en particular no es regular: una prueba por contradicción puede consistir en exhibir una palabra (de la longitud requerida) en el idioma que carece de la propiedad descrita en el lema de bombeo.
Por ejemplo, el idioma sobre el alfabeto se puede demostrar que no es regular de la siguiente manera:
Dejar , y ser como se usa en la declaración formal para el lema de bombeo anterior. Suponga que alguna constanteexiste como lo requiere el lema. Dejar en ser dado por , que es una cadena más larga que . Por el lema de bombeo, debe existir una descomposición con y tal que en para cada . Desde, la cuerda solo consta de instancias de . Además, porque, contiene al menos una instancia de la letra . Sin emabargo, tiene más instancias de la letra que la letra , ya que algunos casos de pero ninguno de fueron agregados. Por lo tanto, no está dentro que contradice el lema de Bombeo. Por lo tanto, no puede ser regular.
La prueba de que el lenguaje de los paréntesis equilibrados (es decir, correctamente anidados) no es regular sigue la misma idea. Dado, hay una serie de paréntesis equilibrados que comienza con más de dejó paréntesis, de modo que consistirá enteramente en paréntesis izquierdos. Repitiendo, se puede producir una cadena que no contenga el mismo número de paréntesis izquierdo y derecho, por lo que no se pueden equilibrar.
Prueba del lema de bombeo
Para cada idioma regular hay un autómata de estado finito (FSA) que acepta el idioma. Se cuenta el número de estados en tal FSA y ese recuento se usa como la longitud de bombeo. Para una cadena de longitud al menos, dejar ser el estado de inicio y dejar ser la secuencia del siguiente estados visitados cuando se emite la cadena. Porque la FSA solo tiene estados, dentro de esta secuencia de estados visitados debe haber al menos un estado que se repita. Escribirpara tal estado. Las transiciones que toman la máquina desde el primer encuentro de estado al segundo encuentro de estado coincidir con alguna cuerda. Esta cadena se llama en el lema, y dado que la máquina coincidirá con una cadena sin el porción, o con la cuerda repetido cualquier número de veces, se cumplen las condiciones del lema.
Por ejemplo, la siguiente imagen muestra una FSA.
La FSA acepta la cadena: abcd . Dado que esta cadena tiene una longitud al menos tan grande como el número de estados, que es cuatro, el principio de casillero indica que debe haber al menos un estado repetido entre el estado de inicio y los siguientes cuatro estados visitados. En este ejemplo, soloes un estado repetido. Dado que la subcadena bc lleva a la máquina a través de transiciones que comienzan en el estado y terminar en el estado , esa parte podría repetirse y la FSA aún aceptaría, dando la cadena abcbcd . Alternativamente, la parte bc podría eliminarse y la FSA aún aceptaría proporcionar el anuncio de cadena . En términos del lema de bombeo, la cadena abcd se divide en unporción a , aporción bc y aporción d .
Como observación al margen, 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 .
Versión general del lema de bombeo para idiomas regulares
Si un idioma es regular, entonces existe un número (la longitud de bombeo) tal que cada cuerda en con se puede escribir en la forma
con cuerdas , y tal que , y
- es en por cada entero . [5]
De esto, la versión estándar anterior sigue un caso especial, con ambos y siendo la cadena vacía.
Dado que la versión general impone requisitos más estrictos al idioma, se puede utilizar para probar la irregularidad de muchos más idiomas, como . [6]
El inverso del lema no es cierto
Si bien el lema de bombeo establece que todos los lenguajes regulares satisfacen las condiciones descritas anteriormente, lo contrario de esta afirmación no es cierto: un lenguaje que satisfaga estas condiciones puede ser aún no regular. En otras palabras, tanto el la versión general del bombeo original y hacerle un lema necesario pero no suficiente condición para un lenguaje que sea regular.
Por ejemplo, considere el siguiente idioma:
- .
En otras palabras, contiene todas las cadenas sobre el alfabeto con una subcadena de longitud 3 que incluye un carácter duplicado, así como todas las cadenas sobre este alfabeto donde exactamente 1/7 de los caracteres de la cadena son 3. Este lenguaje no es regular, pero aún se puede "bombear" con. Suponga que alguna cadena s tiene una longitud de al menos 5. Entonces, dado que el alfabeto tiene sólo cuatro caracteres, al menos dos de los primeros cinco caracteres de la cadena deben estar duplicados. Están separados por un máximo de tres caracteres.
- Si los caracteres duplicados están separados por 0 caracteres o 1, bombee 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, bombee 2 de los caracteres que los separan. Bombear hacia abajo o hacia arriba da como resultado la creación de una subcadena de tamaño 3 que contiene 2 caracteres duplicados.
- La segunda condición de asegura que no es regular: considere la cadena . Esta cadena está en Exactamente cuando y por lo tanto no es regular según el teorema de Myhill-Nerode .
El teorema de Myhill-Nerode proporciona una prueba que caracteriza exactamente los lenguajes regulares. El método típico para probar que un lenguaje es regular es construir una máquina de estados finitos o una expresión regular para el lenguaje.
Ver también
Notas
- ^ Rabin, Michael ; Scott, Dana (abril de 1959). "Autómatas finitos y sus problemas de decisión" (PDF) . Revista de investigación y desarrollo de IBM . 3 (2): 114-125. doi : 10.1147 / rd.32.0114 . Archivado desde el original el 14 de diciembre de 2010.CS1 maint: URL no apta ( enlace ) Aquí: Lema 8, p.119
- ^ Bar-Hillel, Y .; Perles, M .; Shamir, E. (1961), "Sobre las propiedades formales de las gramáticas de estructura sintagmática simple", Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung , 14 (2): 143-172
- ^ John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). Introducción a la teoría, los lenguajes y la computación de los autómatas . Addison Wesley. Aquí: Sección 4.6, p.166
- ^ Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatoria de palabras. Christoffel palabras y repeticiones en palabras . Serie de monografías CRM. 27 . Providence, RI: Sociedad Matemática Estadounidense . pag. 86. ISBN 978-0-8218-4480-9. Zbl 1161.68043 .
- ^ Savitch, Walter (1982). Máquinas abstractas y gramáticas . pag. 49 . ISBN 978-0-316-77161-0.
- ^ John E. Hopcroft y Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Lectura / MA: Addison-Wesley. ISBN 978-0-201-02988-8.Aquí: p. 72, Ejercicio 3.2 (que da una versión un poco menos general, que requiere | w | = p ) y 3.3
Referencias
- Lawson, Mark V. (2004). Autómatas finitos . Chapman y Hall / CRC. ISBN 978-1-58488-255-8. Zbl 1086.68074 .
- Sipser, Michael (1997). "1.4: Idiomas no regulares". Introducción a la Teoría de la Computación . Publicación de PWS. 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, los lenguajes y la computación de los autómatas . Reading, Massachusetts: Addison-Wesley Publishing. ISBN 978-0-201-02988-8. Zbl 0426.68001 . (Ver capítulo 3.)
- Bakhadyr Khoussainov; Anil Nerode (6 de diciembre de 2012). Teoría de los autómatas y sus aplicaciones . Springer Science & Business Media. ISBN 978-1-4612-0171-7.