search
Log In
3 votes
615 views

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 ?

in Theory of Computation
edited by
615 views
1
First link is of 2009. Second is of 2004. This might be the reason!
0
if we minimized a dfa the we need to construct a other dfa which have minimum number of state .and in worst case dfa have atmost 2^n states then time complexity become exponentially.

i am right ankit?? i m not sure ??
1
No, in worst case it is O(ns log n), where n is the number of states and s is the size of the alphabet. See this:
https://en.wikipedia.org/wiki/DFA_minimization#Hopcroft's_algorithm
1

@Abhishek , I think ,This exponential time is for changing non-deterministic machine model to deterministic machine model..If our NFA has n states then number of states in its equivalent minimal DFA should be atmost 2n states..so , this conversion procedure from non-deterministic machine to deterministic machine takes exponential time...But in case of minimization of DFA , we make equivalence classes which represent different states in the minimal DFA...This procedure can take O(n2) or O(nlogn) time...Shai sir has explained O(n2)   time algorithm to minimize finite automata in his video but not O(nlogn)..

0
0k ankit

1 Answer

4 votes
 
Best answer

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
1 answer
2
310 views
When we convert a (minimal) NFA to DFA by subset construction method, is the DFA obtained always a minimal DFA? Please elaborate.
asked Nov 15, 2018 in Theory of Computation Mizuki 310 views
0 votes
1 answer
3
0 votes
1 answer
4
1.1k views
Every DFA is NFA but not vice versa Can you please explain how this statement is true? Reference:- https://www.geeksforgeeks.org/toc-finite-automata-introduction/
asked Aug 28, 2018 in Theory of Computation dan31 1.1k views
...