patternMinor
What is the complexity of finding a regular expression equivalent to a given DFA?
Viewed 0 times
expressiondfatheequivalentwhatregularfindinggivencomplexity
Problem
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 ).
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 ).
Solution
"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.
There are polynomial-time algorithms that solve your computational problem, though, so it is in some flavor of P.
Context
StackExchange Computer Science Q#47274, answer score: 2
Revisions (0)
No revisions yet.