edited by
1,481 views
3 votes
3 votes

According to  this Hopcroft's algorithm , we can efficiently minimize a Finite automata in $O(nlogn)$  time (polynomial time algo) then why it is said that Minimizing Finite Automata is computationally hard according to this link ?

edited by

1 Answer

Best answer
4 votes
4 votes

Hopcroft's algorithm, which You are talking about,  which can efficiently minimize a Finite automata in $O(nlogn)$ time (polynomial time algo), is for "Minimization of a Deterministic FA".

And the other link is about "Minimizing a Non-deterministic FA Which is computationally hard (Even if there is slight Non-determinism).

selected by

Related questions

0 votes
0 votes
1 answer
1
dutta18 asked Sep 21, 2022
418 views
What is the Finite Automata( NFA, epsilon-NFA or DFA) for the regular expression (a*ba)* ?
2 votes
2 votes
2 answers
2
1 votes
1 votes
1 answer
4
Parshu gate asked Aug 5, 2017
969 views
Can I write the 1st one as 2nd one ? are both equivalent ? If yes then why cant we use the 2nd ? The 1st is given as a standard in many notes which looks more complicat...