1
$\begingroup$

I came across following problem:

Which of the following problems is/are P-problems?
(I) Equivalence of DFA's
(II) Equivalence of NFA
(III) Equivalence of regular expressions

Now I know I there exist neat algorithm to find whether given two DFAs are equivalent or not. So (I) must be P-problem. I am doubtful about (II) and (III). There is a procedure to convert every NFA to DFA. So to check whether equivalence of two NFAs, we can first covert them into DFAs and then check their equivalence in P-time. But seems that we cannot convert NFA to DFA in P-time, hence equivalence of NFA seems not a P-problem. Same for (III). Am I correct with this?

$\endgroup$
3
$\begingroup$

The short answer to your question is that 1 is in P, and for 2 and 3 we don't know, but we strongly suspect that they are not in P.

In more detail, as you point out, checking whether two DFAs are equivalent can be done in P (by observing that DFAs are closed under complementation and intersection, and that $A\subseteq B$ is equivalent to $A\cap \overline{B}=\emptyset$).

As for checking equivalence of NFAs, we know that the equivalence problem is PSPACE-complete (by a simple reduction from universality of NFAs). This means that if the problem was in P, we would get P=PSPACE, which would be a huge and unlikely surprise.

Same goes for checking equivalence of regular expressions - the problem is PSPACE-complete. This post has more details on this

$\endgroup$

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.