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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.