patternModerate
Algorithm to determine whether two regexes are equivalent
Viewed 0 times
regexesequivalentarealgorithmtwodeterminewhether
Problem
Given two arbitrary regular expressions, is there an "efficient" algorithm to determine whether they match the same set of strings?
More generally, can we compute the size of the intersection of the two match sets?
What algorithms are there to do this, and what complexity class do they live in?
If we disallow the Kleene star, does that alter the picture at all?
More generally, can we compute the size of the intersection of the two match sets?
What algorithms are there to do this, and what complexity class do they live in?
If we disallow the Kleene star, does that alter the picture at all?
Solution
Hendrik Jan gives a good answer for complexity class, but not an algorithm itself.
The simplest algorithm to do this that I know of is to convert the regular expression to a DFA. There are known techniques for converting a regular expression to an NFA, and an NFA to a DFA.
Once you have two DFAs, testing for equivalence is efficient and decidable, since the minimal form of a DFA is unique up to isomorphism.
However, constructing these DFAs from NFAs could take lots of time, and produce extremely large DFAS, exponentially large in the worst case.
The simplest algorithm to do this that I know of is to convert the regular expression to a DFA. There are known techniques for converting a regular expression to an NFA, and an NFA to a DFA.
Once you have two DFAs, testing for equivalence is efficient and decidable, since the minimal form of a DFA is unique up to isomorphism.
However, constructing these DFAs from NFAs could take lots of time, and produce extremely large DFAS, exponentially large in the worst case.
Context
StackExchange Computer Science Q#12267, answer score: 15
Revisions (0)
No revisions yet.