Considere un lenguaje de expresiones regulares con el cuantificador codicioso , el cuantificador no codicioso ∗ ? , alternancia ordenada y clases de caracteres. (Esto es esencialmente un sublenguaje de PCRE sin referencias posteriores, afirmaciones de búsqueda o algunos de los otros bits más elegantes).
Un partido para una expresión regular para R en una cadena s = s 0 ... s n es un intervalo semiabierto sobre N de tal manera que es un 0 ... es un 1 - 1 es aceptada por R .
Damos una definición recursiva de lo que hace que una coincidencia sea mejor que otra. Una coincidencia para la expresión regular R en una cadena es mejor que otra coincidencia b = [ b 0 , b 1 ) si a 0 < b 0 o, si a 0 = b 0 y:
Si es una clase de personaje: las clases de personaje tienen coincidencias únicas, por lo que todas las coincidencias en la misma posición para R son iguales. Por lo tanto, este caso es imposible.
Si :
- La parte inicial de es una mejor coincidencia para S que la parte inicial de b , o
- Las partes iniciales de y b son igualmente buenas coincidencias para S , y la parte posterior de a es una mejor coincidencia para T que la parte posterior de b .
Si :
- es un partido para S y b no es, o
- y b son igualmente adecuadas para S y una es una mejor coincidencia para S que b es, o
- y b no son compatibles para S pero son partidos de T , y una es una mejor coincidencia para T que b es.
Todas las demás formas sintácticas se reducen a las tres anteriores para propósitos de prioridad de coincidencia:
- : R ≡ S 0 | S 1 | ...
- : R ≡ … | S 1 | S 0
Estos patrones infinitos se utilizan solo con fines de prioridad de coincidencia --- no son parte del lenguaje de coincidencia en consideración.
La relación "mejor" es un orden lineal débil sobre todas las coincidencias posibles para un patrón dado.
Llaman dos expresiones regulares partido equivalente si, para cada cadena de entrada finita, el conjunto de pares disjuntos mejores resultados para S es igual al conjunto de pares disjuntos mejores resultados para T .
P: ¿Es el caso que por cada expresión regular contiene el cuantificador no arbóreo ∗ ? Hay una expresión regular equivalente T que no contiene cuantificadores no apetos?
Editar: Esta es una reescritura completa de la pregunta para aclarar lo que se estaba preguntando.
fuente
\tt
no evita que LaTeX interprete caracteres especiales y secuencias de control!)a+?
) sigue siendo {a ^ n: n≥1}. Si realiza una coincidencia de expresión regular no anclado (como'aaaa' =~ /a+?/
en Perl), no obtendráaaaa
como resultado, pero eso es solo porque las ramas se prueban en un orden diferente ala+
. Si lo haces apropiadamente con los anclajes (como'aaaa' =~ /^a+?\z/
en Perl), obtienesaaaa
como resultado.//g
devolvería una coincidencia global de expresiones regulares ( en Perl)?Respuestas:
Esta respuesta se basa en el supuesto de que la equivalencia de dos expresiones regulares se define ya que reconocen el mismo lenguaje. No responde la pregunta actual.
Tiene un malentendido común de que los cuantificadores reacios cambian el conjunto de cadenas que coincide con una expresión regular. No lo hace, y solo cambia qué opciones se prueban primero.
Por ejemplo, si realiza una coincidencia de expresiones regulares
'aaaa' =~ /a+/
en Perl, encuentra la primera coincidencia en la cadenaaaaa
y recuerda qué subcadena coincide en una variable especial. Incluso si hay más de una subcadenaaaaa
que coincida con la expresión regular dada, se ignorarán las coincidencias que no sean la primera coincidencia.Si los cuantificadores son codiciosos o reacios afecta a cuál es la primera coincidencia entre muchas coincidencias, pero el conjunto de coincidencias no cambia. En este sentido, el conjunto de cadenas que coincide con una expresión regular no cambia sin importar si utiliza cuantificadores codiciosos habituales o cuantificadores reacios.
fuente
a+
ya+?
no son equivalentes en este sentido:aaaa
no es rival para este último.abbb
no está en L (a*(..)*
) porque la primera coincidencia en la cadenaabbb
con la expresión regulara*(..)*
esabb
. Esa no es la definición estándar del lenguaje reconocido por una expresión regular. Si eso es realmente lo que le interesa, debe nombrarlo de manera diferente.a+?
partidosaaaa
. Sé que Ruby regexpes sí."aaaa" =~ /a?/
volver verdadero en Ruby, pero eso es porque el patrón coincide con una subcadena deaaaa
, no porque coincidaaaaa
.+
(editado), y Ruby parece coincidir con la palabra completa (cf rubular.com).