The Gateway to Computer Science Excellence
+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 ?

in Theory of Computation by Boss (16.4k points)
edited by | 288 views
First link is of 2009. Second is of 2004. This might be the reason!
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 ??
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:'s_algorithm

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

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

by Boss (26.3k points)
selected by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
100,766 users