regex - regulares - Determinar si una expresión regular es un subconjunto de otra

negacion expresion regular

Question

Tengo una gran colección de expresiones regulares que cuando coinciden llaman a un manejador de http en particular. Algunas de las expresiones regex más antiguas son inalcanzables (por ejemplo, ac* ⊃ abc* ) y me gustaría podarlas.

¿Hay una biblioteca que con dos expresiones regulares me dirá si el segundo es un subconjunto del primero?

No estaba seguro de que esto fuera decidible al principio (olía como el problema de detención con un nombre diferente). Pero resulta que es decidible .

Answer 1

Encontré una biblioteca de expresiones regulares de python que proporciona operaciones de conjunto.

http://github.com/ferno/greenery

La prueba dice que Sub ⊆ Sup ⇔ Sub ∩ ¬Sup is {} . Puedo implementar esto con la biblioteca de Python:

import sys
from greenery.lego import parse

subregex = parse(sys.argv[1])
supregex = parse(sys.argv[2])

s = subregex&(supregex.everythingbut())
if s.empty():
  print("%s is a subset of %s"%(subregex,supregex))
else:
  print("%s is not a subset of %s, it also matches %s"%(subregex,supregex,s)

ejemplos:

subset.py abcd.* ab.*
abcd.* is a subset of ab.*

subset.py a[bcd]f* a[cde]f*
a[bcd]f* is not a subset of a[cde]f*, it also matches abf*

Es posible que la biblioteca no sea sólida porque, como se menciona en las demás respuestas, debe usar el DFA mínimo para que esto funcione. No estoy seguro de que ferno''s biblioteca ferno''s haga (o pueda hacer) esa garantía.

Por otro lado: jugar con la biblioteca para calcular expresiones regemáticas inversas o simplificar es muy divertido.
a(b|.).* simplifica a a.+ . Lo cual es bastante mínimo.
La inversa de abf* es ([^a]|a([^b]|bf*[^f])).*|a? . Trata de inventarlo por tu cuenta!

Answer 2

Hay una respuesta en la sección de matemáticas: https://math.stackexchange.com/questions/283838/is-one-regular-language-subset-of-another .

Idea básica:

• Calcule el DFA mínimo para ambos idiomas.
• Calcule el producto cruzado de ambos automatiza M1 y M2, lo que significa que cada estado consiste en un par [m1, m2] donde m1 es de M1 y m2 de M2 ​​para todas las combinaciones posibles.
• La nueva transición F12 es: F12 ([m1, m2], x) => [F1 (m1, x), F2 (m2, x)]. Esto significa que si hubo una transición en M1 desde el estado m1 a m1 ''mientras se lee x y en M2 desde el estado m2 a m2'' mientras se lee x, entonces hay una transición en M12 de [m1, m2] a [m1 '', m2'' ] mientras lees x.
• Al final, observa los estados alcanzables:
  • Si hay un par [aceptando, rechazando], entonces el M2 no es un subconjunto de M1
  • Si hay un par [rechazando, accaptando], entonces M1 no es un subconjunto de M2

Sería beneficioso si simplemente calculase la nueva transición y los estados resultantes, omitiendo todos los estados no alcanzables desde el principio.

Answer 3

Si las expresiones regulares utilizan "características avanzadas" de los típicos matchers procedurales (como los de Perl, Java, Python, Ruby, etc.) que permiten aceptar idiomas que no son regulares, entonces no tiene suerte. El problema es, en general, indecidible. Por ejemplo, el problema de si un autómata pushdown reconoce el mismo lenguaje libre de contexto (CF) como otro es indecidible. Las expresiones regulares extendidas pueden describir los lenguajes CF.

Por otro lado, si las expresiones regulares son "verdaderas" en el sentido teórico, que consisten únicamente en concatenación, alternancia y estrella Kleene sobre cadenas con un alfabeto finito, más el azúcar sintáctico habitual en estas (clases de caracteres, +,?, etc.), entonces hay un algoritmo de tiempo polinomial simple.

No puedo darte bibliotecas, pero esto:

For each pair of regexes r and s for languages L(r) and L(s)
  Find the corresponding Deterministic Finite Automata M(r) and M(s)
    Compute the cross-product machine M(r x s) and assign accepting states
       so that it computes L(r) - L(s)
    Use a DFS or BFS of the the M(r x s) transition table to see if any
       accepting state can be reached from the start state
    If no, you can eliminate s because L(s) is a subset of L(r).
    Reassign accepting states so that M(r x s) computes L(s) - L(r)
    Repeat the steps above to see if it''s possible to eliminate r

La conversión de una expresión regular a DFA generalmente usa la construcción de Thompson para obtener un autómata no determinista. Esto se convierte en un DFA utilizando la construcción de subconjuntos. La máquina de productos cruzados es otro algoritmo estándar.

Todo esto se resolvió en la década de 1960 y ahora forma parte de cualquier curso de buena teoría de ciencias de la computación. El estándar de oro para el tema es Hopcroft y Ullman, Automata Theory .

Answer 4

Tratar de encontrar la complejidad de este problema me llevó a este artículo.

La definición formal del problema se puede encontrar en: esto generalmente se llama el problema de inclusión

El problema de inclusión para R es probar para dos expresiones dadas r, r ''∈ R, si r ⊆ r''.

Ese documento tiene una gran información (resumen: todas las expresiones menos simples son bastante complejas), sin embargo, la búsqueda de información sobre el problema de inclusión lleva directamente a . Esa respuesta ya tenía un enlace a un documento que describe un algoritmo de tiempo polinomial aceptable que debería abarcar una gran cantidad de casos comunes.