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

Improve this question
$\endgroup$
2
  • $\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, 2015 at 16:14
  • $\begingroup$ @Raphael The second one. Given a DFA compute equivalent regular expression. $\endgroup$
    – advocateofnone
    Sep 17, 2015 at 16:15

1 Answer 1

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

Improve this answer
$\endgroup$

Your Answer

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

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