Déterminer si une regex est un sous-ensemble d'une autre

Question

J'ai une grande collection d'expressions régulières qui, lorsqu'elles correspondent, appellent un gestionnaire http particulier. Certaines des anciennes expressions régulières sont inaccessibles (par ex. a.c* abc* ) et j'aimerais les tailler.

Existe-t-il une bibliothèque qui, à partir de deux expressions rationnelles, me dise si la seconde est un sous-ensemble de la première ?

Au début, je n'étais pas sûr que cela soit décidable (cela ressemblait au problème de la halte sous un autre nom). Mais il s'avère que c'est décidable .

Answer 1

Essayer de trouver la complexité de ce problème m'a conduit à ce document.

La définition formelle du problème se trouve à l'intérieur : elle est généralement appelée le problème de l'inclusion

Le problème d'inclusion pour R, consiste à tester pour deux expressions données r, r′ ∈ R, si r ⊆ r′.

Cet article contient d'excellentes informations (résumé : toutes les expressions, sauf les plus simples, sont assez complexes), mais la recherche d'informations sur le problème de l'inclusion nous ramène directement à l'adresse suivante StackOverflow . Cette réponse contenait déjà un lien vers un article décrivant un algorithme en temps polynomial passable ce qui devrait couvrir un grand nombre de cas courants.

Answer 2

Il y a une réponse dans la section des mathématiques : https://math.stackexchange.com/questions/283838/is-one-regular-language-subset-of-another .

L'idée de base :

• Calculer la valeur minimale DFAE pour les deux langues.
• Calculez le produit croisé des deux automates M1 et M2, ce qui signifie que chaque état consiste en une paire [m1, m2] où m1 provient de M1 et m2 de M2 pour toutes les combinaisons possibles.
• La nouvelle transition F12 est : F12([m1, m2], x) => [F1(m1, x), F2(m2, x)]. Cela signifie que s'il y avait une transition dans M1 de l'état m1 à m1' pendant la lecture de x et dans M2 de l'état m2 à m2' pendant la lecture de x, alors il y a une transition dans M12 de [m1, m2] à [m1', m2'] pendant la lecture de x.
• A la fin, vous regardez les états atteignables :
  • S'il existe une paire [accepter, rejeter], alors M2 n'est pas un sous-ensemble de M1.
  • S'il existe une paire [rejeter, accepter], alors M1 n'est pas un sous-ensemble de M2.

Il serait bénéfique que vous calculiez simplement la nouvelle transition et les états résultants, en omettant tous les états non atteignables depuis le début.

Answer 3

Si les expressions régulières utilisent des "fonctionnalités avancées" de matchers procéduraux typiques (comme ceux de Perl, Java, Python, Ruby, etc.) qui permettent d'accepter des langages qui ne sont pas réguliers, alors vous n'avez pas de chance. Le problème est en général indécidable. Par exemple, le problème de savoir si un automate pushdown reconnaît le même langage sans contexte (CF) qu'un autre est indécidable. Les expressions régulières étendues peuvent décrire les langages CF.

D'un autre côté, si les expressions régulières sont "vraies" au sens théorique du terme, c'est-à-dire qu'elles consistent uniquement en une concaténation, une alternance et une étoile de Kleene sur des chaînes de caractères à alphabet fini, plus le sucre syntaxique habituel (classes de caractères, +, ?, etc.), alors il existe un algorithme simple en temps polynomial.

Je ne peux pas vous donner des bibliothèques, mais ceci :

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 conversion d'une regex en un DFA utilise généralement la construction de Thompson pour obtenir un automate non-déterministe. Celui-ci est converti en un TFD en utilisant la construction de sous-ensembles. La machine à produits croisés est un autre algorithme standard.

Tout cela a été mis au point dans les années 1960 et fait désormais partie de tout bon cours théorique d'informatique de premier cycle. La référence en la matière est Hopcroft et Ullman, Théorie des automates .

Answer 4

J'ai trouvé une bibliothèque python de regex qui fournit des opérations d'ensemble.

http://github.com/ferno/greenery

La preuve dit Sub ⊆ Sup ⇔ Sub ∩ ¬Sup is {} . Je peux le mettre en œuvre avec la bibliothèque 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)

exemples :

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*

La bibliothèque peut ne pas être robuste car, comme mentionné dans les autres réponses, vous devez utiliser le DFA minimal pour que cela fonctionne. Je ne suis pas sûr ferno's n'offre (ou ne peut offrir) cette garantie.

En passant : Il est très amusant de jouer avec la bibliothèque pour calculer l'inverse ou simplifier les regex.
a(b|.).* se simplifie en a.+ . Ce qui est plutôt minime.
L'inverse de abf* es ([^a]|a([^b]|bf*[^f])).*|a? . Essayez de trouver ça tout seul !