# If DFA is constructed from NFA using lazy subset construction method , is it guaranteed to be the minimized DFA ?

1 vote
610 views

## 1 Answer

2 votes
No, it is not in general minimal. The standard determinization procedure, the subset construction, always converts an NFA with n states to a DFA with 2^n states and there is no reason that this should be minimal.

In practical terms, if you convert an NFA, you'll often find that there are unreachable states in the resulting DFA, which immediately shows that the result is not minimal. For a more extreme example, take any DFA with n states, call it an NFA and determinize it. You now have a DFA with 2^n>n states that accepts the same language as it did before, so it's certainly not minimal.

## Related questions

2 votes
2 answers
1
329 views
0 votes
1 answer
2
259 views
given a sorted array of distinct integers A[1........n], you want to find out whether there is an index i for which A[i]=i.if this problem is solved using divide and conquer method ,then the algorithm run in  a) O(n)               a) O(nlogn)            a) O(logn)         a) O(n2)
2 votes
1 answer
3
124 views
...
1 vote
1 answer
4
4.5k views
How the count to infinity problem is solved using Split Horizontal method please tell ?? what are limitations in this ?