Equivalence des expressions régulières

Question

Y at-il un moyen de savoir si deux expressions régulières arbitraires sont équivalentes? On dirait un problème complexe à moi, mais il pourrait y avoir un mécanisme de simplification DFA ou quelque chose?

Answer 1

Pour tester l'équivalence, vous pouvez calculer le DFA minimale pour les expressions et de les comparer.

Answer 2

testabilité de l'égalité est l'une des propriétés classiques des expressions régulières. (N.B. Cela ne tient pas si vous parlez vraiment des expressions régulières Perl ou une autre technique non régulier superlanguage.)

Transformez vos REs à Automates finis A généralisé et B, puis construire un nouvel automate A-B tels que les Etats qui acceptent de A ont des transitions nulles aux états de début de B, et que les Etats qui acceptent de B sont inversées. Cela vous donne un automate qui accepte toutes les chaînes acceptées par A, à l'exception de tous ceux qui sont acceptés par B.

Faites la même chose pour B-A, et réduire à la fois pour les autorités fédérales pure. Si une FA n'a pas d'états d'accepter accessibles à partir d'un état de départ il accepte la langue vide. Si vous pouvez montrer que les deux A-B et B-A sont vides, vous avez montré que A = B.

Edit Heh, je ne peux pas croire que personne ne remarque l'erreur gigantesque il - un intentionnel, bien sûr :-p

Les automates A-B comme décrit acceptera les chaînes dont la première moitié est acceptée par A et dont la seconde moitié est pas acceptée par B. Construction désiré A-B est un processus un peu plus délicat. Je ne peux pas penser du haut de ma tête, mais je ne sais que c'est bien défini (et implique probablement la création d'états à représenter les produits de l'acceptation des états dans A et les États non accepter en B).

Answer 3

Cela dépend vraiment de ce que vous entendez par des expressions régulières. Comme les autres affiches ont souligné, ce qui réduit les expressions à leur DFA minimal devrait fonctionner, mais il ne fonctionne que pour les pures expressions régulières.

Certains des constructions utilisées dans le monde réel regex libs (en particulier des backreferences) leur donner le pouvoir d'exprimer des langues qui ne sont pas régulières, de sorte que l'algorithme DFA ne fonctionnera pas pour eux. Par exemple, le regex: ([a-z]*) \1 correspond à une occurence deux du même mot séparés par un espace (a a et b b mais pas b a ni a b). Cela ne peut pas être reconnu par un automate fini du tout.

Answer 4

Ces deux fils de PerlMonks discuter de cette question (en particulier, lire les réponses de blokhead):

• satisfiability comparative des regexps
• test d'équivalence regex