Étant donné deux expressions régulières arbitraires, existe-t-il un algorithme "efficace" pour déterminer si elles correspondent au même ensemble de chaînes?
Plus généralement, peut-on calculer la taille de l'intersection des deux jeux de correspondance?
Quels algorithmes sont là pour le faire et dans quelle classe de complexité vivent-ils?
Si nous interdisons l'étoile Kleene, est-ce que cela modifie l'image?
algorithms
regular-expressions
MathematicalOrchid
la source
la source
Réponses:
Hendrik Jan donne une bonne réponse pour la classe de complexité, mais pas un algorithme lui-même.
L'algorithme le plus simple que je connaisse consiste à convertir l'expression régulière en DFA. Il existe des techniques connues pour convertir une expression régulière en NFA et un NFA en DFA.
Une fois que vous avez deux DFA, le test d'équivalence est efficace et décidable, car la forme minimale d'un DFA est unique jusqu'à l'isomorphisme.
Cependant, la construction de ces DFA à partir de NFA pourrait prendre beaucoup de temps et produire des DFAS extrêmement importants, exponentiellement importants dans le pire des cas.
la source
L'équivalence des expressions régulières est connue pour être PSPACE-complete, ce qui est plutôt mauvais. L'article «Complexité des problèmes de décision pour les expressions régulières simples» énumère plusieurs sous-classes d'expressions régulières avec leurs complexités respectives. ( lien )
la source