3 votes

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 ??

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

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 2^{n} 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(n^{2}) or O(nlogn) time...Shai sir has explained O(n^{2}) time algorithm to minimize finite automata in his video but not O(nlogn)..

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).