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

edited | 311 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

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

by Boss (27.4k points)
selected