10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you mean by the "size of the intersection"? In most interesting cases, it will be infinitely large; are you interested in sizes w.r.t. $\Sigma^n$? $\endgroup$ – Raphael May 28 '13 at 7:14
  • $\begingroup$ @Raphael My understanding is that eliminating the Kleene star forces the size of the set to be finite. $\endgroup$ – MathematicalOrchid May 28 '13 at 17:22
  • $\begingroup$ Depends. What other operators are allowed? If you allow complementation, what you say is not true. Also, you ask for the situation with Kleene star, too, so you need to clarify anyway. $\endgroup$ – Raphael May 28 '13 at 17:43
  • $\begingroup$ See also cs.stackexchange.com/q/12624/755 $\endgroup$ – D.W. Dec 18 '15 at 4:04
11
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

Equivalence of regular expressions is known to be PSPACE-complete, which is rather bad. The paper "Complexity of Decision Problems for Simple Regular Expressions" lists several subclasses of regular expressions with their respective complexities. (link)

$\endgroup$
  • 1
    $\begingroup$ it is even EXPSPACE-complete if you allow the square operator (i.e. writing $e^2$ instead of $ee$). It becomes NEXPTIME-complete without the Kleene star. $\endgroup$ – Denis May 26 '13 at 10:11
  • $\begingroup$ @dkuper Thanks for the additional explanation. Feel free to edit the answer to add this or suitable references. (Or even start your own answer.) $\endgroup$ – Hendrik Jan May 28 '13 at 20:23
  • $\begingroup$ Is there a reference for general regular expressions to be PSPACE-complete? $\endgroup$ – Ryan Apr 24 '15 at 2:38
  • $\begingroup$ Your link is dead. Can you either provide a fresh one or at least some of the relevant info from the paper? $\endgroup$ – D. Ben Knoble Mar 19 at 13:27
  • $\begingroup$ @D.BenKnoble Link works fine for me. $\endgroup$ – Hendrik Jan Mar 20 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.