4
$\begingroup$

I had taken a course long ago on complexity theory. I only remember basic things, so I am reading "Introduction to the Theory of Computation by Michael Sipser". The book in its first chapter introduces DFA and NFA.

If we are given a DFA $D$ where $\sum=\{0,1\}$ ( the alphabets ), then how difficult is the problem of finding a regular expression of the language that $D$ recognises?

By difficulty I mean to which class does this problem belong like NP,PSPACE etc ( sorry for vague definition of difficulty, I only have a broad understanding of what classes NP,PSPACE etc are as of now ).

$\endgroup$
  • $\begingroup$ What do you mean, "identify"? Given a regular expression and a DFA, decide if they describe the same language? Or given a DFA, compute an equivalent regular expression? $\endgroup$ – Raphael Sep 17 '15 at 16:14
  • $\begingroup$ @Raphael The second one. Given a DFA compute equivalent regular expression. $\endgroup$ – sashas Sep 17 '15 at 16:15
2
$\begingroup$

"Find an equivalent regular expression" is not a decision problem, so it can not be in any of these classes. See also our reference questions on complexity theory.

There are polynomial-time algorithms that solve your computational problem, though, so it is in some flavor of P.

$\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.