¿Afecta la búsqueda a qué idiomas pueden coincidir con las expresiones regulares?

Hay algunas características en los motores de expresiones regulares modernas que le permiten hacer coincidir idiomas que no podrían combinarse sin esa característica. Por ejemplo, la siguiente expresión regular usando como referencia anterior coincide con el idioma de todas las cadenas que consisten en una palabra que se repite: (.+)\1. Este idioma no es regular y no puede ser igualado por una expresión regular que no use referencias anteriores.

¿La búsqueda también afecta qué idiomas pueden coincidir con una expresión regular? Es decir, ¿hay algún idioma que se pueda combinar usando una búsqueda que no se podría comparar de otra manera? Si es así, ¿es esto cierto para todos los tipos de lookaround (lookahead o lookbehind negativo o positivo) o solo para algunos de ellos?

Como afirman las otras respuestas, las revisiones no agregan ningún poder adicional a las expresiones regulares.

Creo que podemos mostrar esto usando lo siguiente:

One Pebble 2-NFA (consulte la sección Introducción del documento que se refiere a él).

El 2NFA de 1 guijarro no se ocupa de los lookaheads anidados, pero podemos usar una variante de 2NFA de varios guijarros (ver la sección a continuación).

Introducción

Un 2-NFA es un autómata finito no determinista que tiene la capacidad de moverse hacia la izquierda o hacia la derecha en su entrada.

Una máquina de un guijarro es donde la máquina puede colocar un guijarro en la cinta de entrada (es decir, marcar un símbolo de entrada específico con un guijarro) y hacer posiblemente diferentes transiciones en función de si hay un guijarro en la posición de entrada actual o no.

Se sabe que el One Pebble 2-NFA tiene el mismo poder que un DFA normal.

Lookaheads no anidados

La idea básica es la siguiente:

El 2NFA nos permite retroceder (o 'pista delantera') moviéndonos hacia adelante o hacia atrás en la cinta de entrada. Entonces, para una búsqueda anticipada, podemos hacer la coincidencia de la expresión regular anticipada y luego retroceder lo que hemos consumido, al hacer coincidir la expresión anticipada. Para saber exactamente cuándo dejar de dar marcha atrás, ¡usamos el guijarro! Dejamos caer el guijarro antes de ingresar al dfa para que la mirada hacia adelante marque el lugar donde debe detenerse el retroceso.

Por lo tanto, al final de ejecutar nuestra cadena a través del guijarro 2NFA, sabemos si coincidimos con la expresión anticipada o no y la entrada que queda (es decir, lo que queda por consumir) es exactamente lo que se requiere para igualar el resto.

Entonces, para una búsqueda anticipada de la forma u (? = V) w

Tenemos los DFA para u, v y w.

Desde el estado de aceptación (sí, podemos asumir que solo hay uno) de DFA para u, hacemos una transición electrónica al estado inicial de v, marcando la entrada con un guijarro.

Desde un estado de aceptación para v, pasamos a un estado que sigue moviendo la entrada hacia la izquierda, hasta que encuentra un guijarro, y luego pasa al estado inicial de w.

Desde un estado de rechazo de v, hacemos una e-transición a un estado que sigue moviéndose hacia la izquierda hasta que encuentra el guijarro, y pasa al estado de aceptación de u (es decir, donde lo dejamos).

La prueba utilizada para NFA regulares para mostrar r1 | r2, o r *, etc., se transfieren a estos 2nfas de un guijarro. Ver http://www.coli.uni-saarland.de/projects/milca/courses/coal/html/node41.html#regularlanguages.sec.regexptofsa para obtener más información sobre cómo se ensamblan las máquinas componentes para obtener una máquina más grande para la expresión r *, etc.

La razón por la que funcionan las pruebas anteriores para r * etc es que el retroceso asegura que el puntero de entrada esté siempre en el lugar correcto, cuando ingresamos el componente nfas para la repetición. Además, si se está utilizando un guijarro, una de las máquinas de componentes anticipados lo está procesando. Dado que no hay transiciones de una máquina de mirar hacia adelante a una máquina de mirar hacia adelante sin retroceder completamente y recuperar el guijarro, todo lo que se necesita es una máquina de un guijarro.

Por ejemplo, considere ([^ a] | a (? = ... b)) *

y la cuerda abbb.

Tenemos abbb que pasa por peb2nfa para a (? = ... b), al final del cual estamos en el estado: (bbb, emparejado) (es decir, en la entrada bbb está restante, y ha coincidido con 'a' seguido de '..b'). Ahora, debido al *, volvemos al principio (ver la construcción en el enlace de arriba) e ingresamos el dfa para [^ a]. Haga coincidir b, vuelva al principio, ingrese [^ a] nuevamente dos veces y luego acepte.

Tratar con Lookaheads anidados

Para manejar lookaheads anidados, podemos usar una versión restringida de k-pebble 2NFA como se define aquí: Resultados de complejidad para autómatas bidireccionales y multi-pebble y sus lógicas (ver Definición 4.1 y Teorema 4.2).

En general, 2 autómatas guijarros pueden aceptar conjuntos no regulares, pero con las siguientes restricciones, se puede demostrar que los autómatas k-guijarros son regulares (Teorema 4.2 en el artículo anterior).

Si los guijarros son P_1, P_2, ..., P_K

• P_ {i + 1} no se puede colocar a menos que P_i ya esté en la cinta y P_ {i} no se puede recoger a menos que P_ {i + 1} no esté en la cinta. Básicamente, los guijarros deben usarse de manera LIFO.

• Entre el momento en que se coloca P_ {i + 1} y el momento en que se toma P_ {i} o se coloca P_ {i + 2}, el autómata puede atravesar solo la subpalabra ubicada entre la ubicación actual de P_ {i} y el final de la palabra de entrada que se encuentra en la dirección de P_ {i + 1}. Además, en esta subpalabra, el autómata sólo puede actuar como un autómata de 1 guijarro con Guijarro P_ {i + 1}. En particular, no está permitido levantar, colocar o incluso sentir la presencia de otro guijarro.

Entonces, si v es una expresión de anticipación anidada de profundidad k, entonces (? = V) es una expresión de anticipación anidada de profundidad k + 1. Cuando ingresamos a una máquina de mirar hacia adelante, sabemos exactamente cuántos guijarros se han colocado hasta ahora y, por lo tanto, podemos determinar exactamente qué guijarro colocar y cuando salimos de esa máquina, sabemos qué guijarro levantar. Todas las máquinas en la profundidad t se ingresan colocando el guijarro ty se sale (es decir, volvemos al procesamiento de una máquina de profundidad t-1) quitando el guijarro t. Cualquier ejecución de la máquina completa parece una llamada dfs recursiva de un árbol y las dos restricciones anteriores de la máquina multi-guijarros pueden ser atendidas.

Ahora, cuando combina expresiones, para rr1, ya que concat, los números de guijarros de r1 deben incrementarse por la profundidad de r. Para r * y r | r1, la numeración de los guijarros sigue siendo la misma.

Por lo tanto, cualquier expresión con lookaheads se puede convertir en una máquina de múltiples guijarros equivalente con las restricciones anteriores en la colocación de guijarros y, por lo tanto, es regular.

Conclusión

Básicamente, esto soluciona el inconveniente de la prueba original de Francis: poder evitar que las expresiones de anticipación consuman cualquier cosa que sea necesaria para futuras coincidencias.

Dado que los Lookbehind son solo cadenas finitas (no realmente expresiones regulares), podemos tratar con ellos primero y luego con los lookaheads.

Perdón por la redacción incompleta, pero una prueba completa implicaría dibujar muchas figuras.

Me parece correcto, pero me alegrará saber si hay algún error (que parece que me gusta :-)).

La respuesta a la pregunta que hace, que es si una clase de lenguajes más grande que los lenguajes regulares puede reconocerse con expresiones regulares aumentadas por la búsqueda, es no.

Una prueba es relativamente sencilla, pero un algoritmo para traducir una expresión regular que contiene una mirada a otra es complicado.

Primero: tenga en cuenta que siempre puede negar una expresión regular (sobre un alfabeto finito). Dado un autómata de estado finito que reconoce el lenguaje generado por la expresión, simplemente puede intercambiar todos los estados de aceptación por estados de no aceptación para obtener una FSA que reconozca exactamente la negación de ese lenguaje, para el cual hay una familia de expresiones regulares equivalentes. .

Segundo: debido a que los lenguajes regulares (y por lo tanto las expresiones regulares) están cerrados bajo negación, también están cerrados bajo intersección ya que A interseca B = neg (neg (A) unión neg (B)) según las leyes de Morgan. En otras palabras, dadas dos expresiones regulares, puede encontrar otra expresión regular que coincida con ambas.

Esto le permite simular expresiones de búsqueda. Por ejemplo, u (? = V) w solo coincide con expresiones que coincidirán con uv y uw.

Para una búsqueda anticipada negativa, necesita la expresión regular equivalente de la teoría de conjuntos A \ B, que es simplemente A intersect (neg B) o equivalentemente neg (neg (A) union B). Por lo tanto, para cualquier expresión regular rys, puede encontrar una expresión regular rs que coincida con aquellas expresiones que coinciden con r que no coinciden con s. En términos de búsqueda anticipada negativa: u (?! V) w solo coincide con las expresiones que coinciden con uw - uv.

Hay dos razones por las que la búsqueda es útil.

Primero, porque la negación de una expresión regular puede resultar en algo mucho menos ordenado. Por ejemplo q(?!u)=q($|[^u]).

En segundo lugar, las expresiones regulares hacen más que coincidir con expresiones, también consumen caracteres de una cadena, o al menos así es como nos gusta pensar en ellos. Por ejemplo, en python me preocupan los .start () y .end (), por lo tanto, por supuesto:

>>> re.search('q($|[^u])', 'Iraq!').end()
5
>>> re.search('q(?!u)', 'Iraq!').end()
4

En tercer lugar, y creo que esta es una razón bastante importante, la negación de las expresiones regulares no supera la concatenación. neg (a) neg (b) no es lo mismo que neg (ab), lo que significa que no puede traducir una búsqueda fuera del contexto en el que la encuentra; debe procesar toda la cadena. Supongo que eso hace que sea desagradable para la gente trabajar y rompe la intuición de las personas sobre las expresiones regulares.

Espero haber respondido a su pregunta teórica (es tarde en la noche, así que perdóneme si no lo tengo claro). Estoy de acuerdo con un comentarista que dijo que esto tiene aplicaciones prácticas. Me encontré con el mismo problema al intentar raspar algunas páginas web muy complicadas.

EDITAR

Mis disculpas por no ser más claro: no creo que pueda dar una prueba de la regularidad de las expresiones regulares + revisión por inducción estructural, mi ejemplo de u (?! V) w estaba destinado a ser solo eso, un ejemplo, y uno fácil a eso. La razón por la que una inducción estructural no funcionará es porque las alternativas se comportan de una manera no composicional, el punto que estaba tratando de hacer sobre las negaciones anteriormente. Sospecho que cualquier prueba formal directa tendrá muchos detalles confusos. He tratado de pensar en una manera fácil de mostrarlo, pero no se me ocurre ninguna.

Para ilustrar el uso del primer ejemplo de Josh de ^([^a]|(?=..b))*$esto, es equivalente a un DFSA de 7 estados con todos los estados aceptando:

A - (a) -> B - (a) -> C --- (a) --------> D 
Λ          |           \                  |
|          (not a)       \               (b)
|          |              \               | 
|          v                \             v
(b)        E - (a) -> F      \-(not(a)--> G  
|            <- (b) - /                   |
|          |                              |
|         (not a)                         |
|          |                              |
|          v                              |
\--------- H <-------------------(b)-----/

La expresión regular para el estado A solo se ve así:

^(a([^a](ab)*[^a]|a(ab|[^a])*b)b)*$

En otras palabras, cualquier expresión regular que vaya a obtener eliminando los cambios indirectos será, en general, mucho más larga y más complicada.

Para responder al comentario de Josh, sí, creo que la forma más directa de demostrar la equivalencia es a través de la FSA. Lo que hace que esto sea más complicado es que la forma habitual de construir una FSA es a través de una máquina no determinista: es mucho más fácil expresar u | v simplemente como la máquina construida a partir de máquinas para u y v con una transición épsilon a las dos. Por supuesto, esto es equivalente a una máquina determinista, pero con el riesgo de una explosión exponencial de estados. Mientras que la negación es mucho más fácil de hacer a través de una máquina determinista.

La prueba general implicará tomar el producto cartesiano de dos máquinas y seleccionar los estados que desea conservar en cada punto en el que desea insertar una búsqueda. El ejemplo anterior ilustra lo que quiero decir hasta cierto punto.

Mis disculpas por no suministrar una construcción.

EDICIÓN ADICIONAL: Encontré una publicación de blog que describe un algoritmo para generar un DFA a partir de una expresión regular aumentada con vistas. Es genial porque el autor extiende la idea de un NFA-e con "transiciones épsilon etiquetadas" de la manera obvia, y luego explica cómo convertir un autómata de este tipo en un DFA.

Pensé que algo así sería una forma de hacerlo, pero me alegra que alguien lo haya escrito. No se me ocurrió pensar en algo tan genial.

Estoy de acuerdo con las otras publicaciones en las que la búsqueda es regular (lo que significa que no agrega ninguna capacidad fundamental a las expresiones regulares), pero tengo un argumento que es más simple en mi opinión que los otros que he visto.

Demostraré que la revisión es regular proporcionando una construcción DFA. Un idioma es regular si y solo si tiene un DFA que lo reconoce. Tenga en cuenta que Perl no utiliza DFA internamente (consulte este documento para obtener más detalles: http://swtch.com/~rsc/regexp/regexp1.html ), pero construimos un DFA para fines de prueba.

La forma tradicional de construir un DFA para una expresión regular es construir primero un NFA usando el algoritmo de Thompson. Dados dos fragmentos de expresiones regulares r1y r2, el algoritmo de Thompson proporciona construcciones para la concatenación ( r1r2), alternancia ( r1|r2) y repetición ( r1*) de expresiones regulares. Esto le permite construir un NFA poco a poco que reconozca la expresión regular original. Consulte el documento anterior para obtener más detalles.

Para mostrar que la búsqueda anticipada positiva y negativa son regulares, proporcionaré una construcción para la concatenación de una expresión regular ucon una anticipación positiva o negativa: (?=v)o (?!v). Solo la concatenación requiere un tratamiento especial; las construcciones habituales de alternancia y repetición funcionan bien.

La construcción es para u (? = V) y u (?! V) es:

En otras palabras, conecte cada estado final del NFA existente para utanto con un estado de aceptación como con un NFA para v, pero modificado de la siguiente manera. La función f(v)se define como:

• Sea aa(v)una función en un NFA vque cambie cada estado de aceptación a un "estado anti-aceptación". Un estado anti-aceptación se define como un estado que hace que la coincidencia falle si cualquier ruta a través de la NFA termina en este estado para una cadena determinada s, incluso si una ruta diferente vpara stermina en un estado de aceptación.
• Sea loop(v)una función en un NFA vque agrega una auto-transición en cualquier estado de aceptación. En otras palabras, una vez que una ruta conduce a un estado de aceptación, esa ruta puede permanecer en el estado de aceptación para siempre sin importar qué entrada siga.
• Por búsqueda negativa hacia delante, f(v) = aa(loop(v)).
• Por búsqueda positiva hacia delante, f(v) = aa(neg(v)).

Para proporcionar un ejemplo intuitivo de por qué esto funciona, usaré la expresión regular (b|a(?:.b))+, que es una versión ligeramente simplificada de la expresión regular que propuse en los comentarios de la prueba de Francis. Si usamos mi construcción junto con las construcciones tradicionales de Thompson, terminamos con:

Los es son transiciones épsilon (transiciones que se pueden tomar sin consumir ninguna entrada) y los estados anti-aceptación están etiquetados con X. En la mitad izquierda del gráfico, puede ver la representación de (a|b)+: any ao bpone el gráfico en un estado de aceptación, pero también permite una transición de regreso al estado de inicio para que podamos hacerlo nuevamente. Pero tenga en cuenta que cada vez que hacemos coincidir un a, también ingresamos a la mitad derecha del gráfico, donde estamos en estados anti-aceptación hasta que hacemos coincidir "cualquiera" seguido de un b.

Esta no es una NFA tradicional porque las NFA tradicionales no tienen estados en contra de la aceptación. Sin embargo, podemos utilizar el algoritmo tradicional NFA-> DFA para convertirlo en un DFA tradicional. El algoritmo funciona como de costumbre, donde simulamos múltiples ejecuciones del NFA haciendo que nuestros estados de DFA correspondan a subconjuntos de los estados de NFA en los que podríamos estar. El único giro es que aumentamos ligeramente la regla para decidir si un estado de DFA es un aceptar estado (final) o no. En el algoritmo tradicional, un estado de DFA es un estado de aceptación si alguno de los estados de NFA era un estado de aceptación. Modificamos esto para decir que un estado de DFA es un estado de aceptación si y solo si:

• = 1 NFA states es un estado de aceptación, y

• 0 Los estados de la NFA son estados anti-aceptación.

Este algoritmo nos dará un DFA que reconoce la expresión regular con anticipación. Ergo, mirar hacia adelante es normal. Tenga en cuenta que mirar hacia atrás requiere una prueba separada.

Tengo la sensación de que aquí se hacen dos preguntas distintas:

• ¿Son los motores Regex que incorporan "lookaround" más potentes que los motores Regex que no lo hacen?
• ¿"Lookaround" habilita un motor Regex con la capacidad de analizar idiomas que son más complejos que los generados a partir de una gramática Chomsky Tipo 3 - Regular ?

La respuesta a la primera pregunta en un sentido práctico es sí. Lookaround le dará a un motor Regex que usa esta característica fundamentalmente más potencia que uno que no lo hace. Esto se debe a que proporciona un conjunto más rico de "anclajes" para el proceso de emparejamiento. Lookaround le permite definir una expresión regular completa como un posible punto de anclaje (afirmación de ancho cero). Puede obtener una descripción general bastante buena del poder de esta función aquí .

Lookaround, aunque potente, no eleva el motor Regex más allá de los límites teóricos que le impone una gramática de tipo 3. Por ejemplo, nunca podrá analizar de manera confiable un idioma basado en una gramática libre de contexto - Tipo 2 utilizando un motor Regex equipado con lookaround. Los motores de expresiones regulares están limitados al poder de una automatización de estado finito y esto restringe fundamentalmente la expresividad de cualquier idioma que puedan analizar al nivel de una gramática de tipo 3. No importa cuántos "trucos" se agreguen a su motor Regex, los idiomas generados a través de un gramática libre de contexto siempre permanecerá más allá de sus capacidades. Análisis libre de contexto: la gramática de tipo 2 requiere la automatización pushdown para "recordar" dónde está en una construcción de lenguaje recursivo. Todo lo que requiera una evaluación recursiva de las reglas gramaticales no se puede analizar con motores Regex.

Para resumir: Lookaround proporciona algunos beneficios prácticos a los motores Regex pero no "altera el juego" en un nivel teórico.

EDITAR

¿Existe alguna gramática con una complejidad en algún lugar entre el Tipo 3 (Regular) y el Tipo 2 (Libre de contexto)?

Creo que la respuesta es no. La razón es que no existe un límite teórico sobre el tamaño de la NFA / DFA necesaria para describir un idioma regular. Puede volverse arbitrariamente grande y, por lo tanto, poco práctico de usar (o especificar). Aquí es donde las evasiones como "mirar alrededor" son útiles. Proporcionan un mecanismo abreviado para especificar lo que de otro modo conduciría a especificaciones NFA / DFA muy grandes / complejas. No aumentan la expresividad de los lenguajes regulares, solo hacen que especificarlos sea más práctico. Una vez que entiendes este punto, queda claro que hay muchas "características" que podrían agregarse a los motores Regex para hacerlos más útiles en un sentido práctico, pero nada los hará capaces de ir más allá de los límites de un lenguaje regular. .

La diferencia básica entre un lenguaje normal y uno libre de contexto es que un lenguaje normal no contiene elementos recursivos. Para evaluar un lenguaje recursivo, necesita una Automatización Push Down para "recordar" dónde se encuentra en la recursividad. Un NFA / DFA no apila información de estado, por lo que no puede manejar la recursividad. Entonces, dada una definición de lenguaje no recursiva, habrá algo de NFA / DFA (pero no necesariamente una expresión Regex práctica) para describirlo.