14
$\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?

Improve this question
$\endgroup$
4
  • $\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
    Commented May 28, 2013 at 7:14
  • $\begingroup$ @Raphael My understanding is that eliminating the Kleene star forces the size of the set to be finite. $\endgroup$
    – MathematicalOrchid
    Commented May 28, 2013 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
    Commented May 28, 2013 at 17:43
  • $\begingroup$ See also cs.stackexchange.com/q/12624/755 $\endgroup$
    – D.W. ♦
    Commented Dec 18, 2015 at 4:04

2 Answers 2

Reset to default
15
$\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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I wish you had actually explained how to do it and what the process and result of converting a regex to a DFA/NFA looks like. $\endgroup$
    – user132026
    Commented Nov 17, 2021 at 9:53
  • $\begingroup$ @Boris Fair enough, but converting a regex to an NFA is a standard algorithm in automata theory, that an introductory text should explain, as is converting an NFA to a DFA. It seemed orthogonal to the question at hand. $\endgroup$
    – Joey Eremondi
    Commented Nov 17, 2021 at 17:35
14
$\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)

Improve this answer
$\endgroup$
6
  • 2
    $\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
    Commented May 26, 2013 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
    Commented May 28, 2013 at 20:23
  • $\begingroup$ Is there a reference for general regular expressions to be PSPACE-complete? $\endgroup$
    – Ryan Dougherty
    Commented Apr 24, 2015 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
    Commented Mar 19, 2019 at 13:27
  • $\begingroup$ @D.BenKnoble Link works fine for me. $\endgroup$
    – Hendrik Jan
    Commented Mar 20, 2019 at 16:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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