regex - probar - ¿De qué manera las referencias inversas en expresiones regulares hacen que sea necesario el seguimiento?
probar expresiones regulares (4)
Leí http://swtch.com/~rsc/regexp/regexp1.html y en él el autor dice que para tener referencias inversas en expresiones regulares, uno necesita retroceso cuando se hacen coincidencias, y eso hace que la complejidad del peor de los casos sea exponencial. Pero no veo exactamente por qué las referencias inversas introducen la necesidad de realizar un seguimiento. ¿Alguien puede explicar por qué y quizás proporcionar un ejemplo (expresión regular y entrada)?
Documento muy interesante: Extender los autómatas finitos para combinar eficientemente las expresiones regulares compatibles con Perl , respaldar las referencias inversas y los casos contados de manera eficiente con NFA modificada.
Hay algunos ejemplos excelentes en este tutorial:
http://www.regular-expressions.info/brackets.html
El caso particular en el que estará interesado se muestra en "Retroceder en la captura de grupos" , donde se explica cómo se puede renunciar a toda la coincidencia varias veces antes de que se pueda encontrar la última que coincida con toda la expresión regular. Además, vale la pena señalar que esto podría llevar a coincidencias inesperadas.
NFA y DFA son autómatas finitos , también conocidos como máquinas de estados finitos, que son "máquinas abstractas que pueden estar en uno de un número finito de estados" [1] . Note el número finito de estados.
Los rápidos algoritmos NFA / DFA que se analizan en el artículo vinculado, la http://swtch.com/~rsc/regexp/regexp1.html , son rápidos porque pueden funcionar con un número finito de estados (independientemente de la longitud de entrada) como se describe en el artículo.
La introducción de referencias inversas hace que el número de estados (casi) sea "infinito" (en el peor de los casos, aproximadamente 256 n, donde n es la longitud de la entrada). El número de estados aumenta porque cada valor posible de cada referencia inversa se convierte en un estado de los autómatas.
Por lo tanto, el uso de una máquina de estado finito ya no es adecuado / adecuado, y en su lugar se deben usar algoritmos de rastreo.
Para llegar directamente a su pregunta, debe hacer un breve estudio de la Jerarquía de Chomsky . Esta es una forma antigua y hermosa de organizar lenguajes formales en conjuntos de complejidad creciente. El escalón más bajo de la jerarquía es el de los lenguajes regulares. Podría adivinar, y tendría razón, que los RL son exactamente aquellos que pueden representarse con expresiones regulares "puras": aquellos con solo el alfabeto, cadena vacía, concatenación, alternancia | y estrella Kleene * (mire, Ma, no hay referencias atrasadas). Un teorema clásico de la teoría del lenguaje formal, el Teorema de Kleene, es que las DFA, las NFA (como se describe en el artículo que usted citó) y las expresiones regulares tienen exactamente el mismo poder para representar y reconocer idiomas. La construcción de Thompson dada en el artículo es parte de la prueba del teorema.
Cada RL es también un CFL. Pero hay infinitos CFL que no son regulares. Una característica que puede existir en las CFL que las hace demasiado complejas para ser regulares son pares de cosas equilibradas: paréntesis, bloques de inicio-fin, etc. Casi todos los lenguajes de programación son CFL. Los CFL pueden ser reconocidos eficientemente por lo que se denomina un autómata pushdown. Esto es esencialmente una NFA con una pila pegada. La pila crece para ser tan grande como sea necesario, por lo que ya no es un autómata finito. Los analizadores de lenguajes de programación reales son casi todas las variaciones en los autómatas de empuje.
Considere la expresión regular con referencia inversa
^(b*a)/1$
En palabras, esto representa cadenas de longitud 2n para algunos n, donde los caracteres n''th y 2n''th son a y todos los demás caracteres son b . Este es un ejemplo perfecto de aa CFL que no es regular. Puede probar esto de manera rigurosa con otra herramienta de lenguaje formal y genial llamada lema de bombeo.
¡Esto es exactamente por qué las referencias anteriores causan problemas! Permiten "expresiones regulares" que representan idiomas que no son regulares. Por lo tanto, no hay NFA o DFA que puedan reconocerlos.
Pero espera, es incluso peor de lo que he hecho hasta ahora. Considerar
^(b*a)/1/1$
Ahora tenemos una cadena de longitud 3n donde los elementos n''th, 2n''th y 3n''th son a y todos los demás son b . ¡Hay otro sabor del lema de bombeo que permite una prueba de que este lenguaje es incluso demasiado complejo para ser un CFL! Ningún autómata pushdown puede reconocer este.
Las referencias anteriores permiten que estas expresiones regulares sobrealimentadas representen idiomas que son tres escalones de la jerarquía de Chomsky: los idiomas sensibles al contexto. En términos generales, la única forma de reconocer una CSL es verificar todas las cadenas en el idioma de igual longitud (al menos si P! = NP, pero eso es cierto para todos los propósitos prácticos y para una historia completamente diferente). El número de tales cadenas es exponencial en la longitud de la que está haciendo coincidir.
Es por esto que se necesita el buscador de expresiones regulares de búsqueda. Puedes ser muy inteligente en la forma en que diseñas la búsqueda. Pero siempre habrá alguna entrada que lo lleve a tomar un tiempo exponencial.
Así que estoy de acuerdo con el autor del documento que citó. Es posible escribir expresiones regulares de apariencia inocente sin ref ref. Que serán reconocidas de manera eficiente para casi todas las entradas, pero donde existe alguna entrada que causa un comparador de expresiones regulares de Perl o Java o Python (porque es una búsqueda de seguimiento) para requerir millones de Años para completar el partido. Esto es Loco. Puede tener un script que sea correcto y funcione bien durante años y luego se bloquee un día simplemente porque se tropezó con una de las entradas incorrectas. Supongamos que la expresión regular está enterrada en el analizador de mensajes del sistema de navegación en el avión que está montando ...
Editar
A petición, a^kba^kb cómo se puede usar el lema de bombeo para probar que el lenguaje a^kba^kb no es regular. Aquí a^k es una abreviatura de k repetidas veces. El PL dice que debe existir un entero positivo N tal que cada cadena en un lenguaje regular de longitud, al menos N debe tener el formato RST, de modo que RS ^ k T también esté en el lenguaje para todo k natural. Aquí R , S , T son cadenas y S puede no estar vacío.
La prueba del PL depende del hecho de que cada lenguaje regular corresponde a algún DFA. Una entrada aceptada en este DFA más larga que su número de estados (que equivale a L en el lema) debe hacer que se "repita" para repetir un estado. Llame a este estado X. La máquina consume algunas cadenas R para llegar desde el principio a X, luego S para volver a X, luego T para llegar a un estado de aceptación. Bueno, la adición de copias adicionales de S (o la eliminación de S) en la entrada corresponde solo a un número diferente de "bucles" de X a X. En consecuencia, también se aceptará la nueva cadena con copias adicionales (o eliminadas) de S .
Dado que cada RL debe satisfacer el PL, una prueba de que un lenguaje no es un producto regular demuestra que contradice el PL. Para nuestro idioma, esto no es difícil. Supongamos que intenta convencerme de que el lenguaje L = a^kba^kb satisface el PL. Debido a que lo hace, debe poder darme un valor de N (ver más arriba): el número de estados en un DFA hipotético que reconoce L. En ese momento, diré: "Muy bien, señor regular, considere el cadena B = a^N ba^N b ". Si L es regular, B debe hacer que este DFA (sin importar cómo se vea) se repita dentro de los primeros N caracteres, ¡lo que debe ser todo a s! Así que el bucle (cadena S arriba) consiste de todos a s, también. Con esto puedo mostrar de inmediato que su afirmación de que L es regular es falsa. Solo elijo dar la vuelta al bucle una segunda vez. Esto hará que este hipotético DFA tuyo acepte una nueva cadena a^M ba^N b , donde M> N porque agregué a s a su primera mitad. ¡Ay! Esta nueva cadena no está en L, por lo que el PL no es verdadero después de todo. Ya que puedo hacer este truco cada vez que no importa lo que N haya proporcionado, el PL no puede ser válido para L, y L no puede ser regular después de todo.
Como no es regular, el teorema de Kleene nos dice que no hay DFA ni FA ni regex "pura" que lo describa.
La prueba de que las referencias anteriores permiten que los idiomas que no están libres de contexto tiene un anillo muy similar, pero necesita antecedentes sobre los autómatas de pushdown que no voy a dar aquí. Google proporcionará.
NB: Ambos no son suficientes para demostrar que las referencias anteriores hacen que el reconocimiento NP sea completo. Simplemente dicen de una manera muy rigurosa que las referencias anteriores agregan una complejidad real a las expresiones regulares puras. Permiten idiomas que no se pueden reconocer con ninguna máquina que tenga memoria finita, ni tampoco con una memoria LIFO infinitamente grande. Dejaré NP prueba de integridad a los demás.