The Gateway to Computer Science Excellence

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,492 answers

195,469 comments

100,766 users