Linked Questions

2 votes
1 answer
23k views

Maximum number of states in minimized DFA from NFA with $n$ states [duplicate]

If an NFA with $n$ states is converted to an equivalent minimized DFA then what will be the maximum number of states in the DFA? Will it be $2^n$ or $2n$?
Kapes's user avatar
  • 163
2 votes
2 answers
3k views

Size comparison of NFA and minimal DFA [duplicate]

Except for isomorphisms, the minimal DFA of a regular language is unique. However, is it possible that an equivalent NFA has less states than the minimal DFA? If so, what is the reasoning behind this? ...
Sebastian Stoelen's user avatar
0 votes
0 answers
44 views

Can there exist a smaller NFA then a minimal DFA [duplicate]

So every NFA can be transformed to a DFA and every DFA can be transformed to a minimal DFA. But every NFA can also be transformed to a GNFA (generalized NFA) with 2 states. This is just the start and ...
FOKDIEKUL's user avatar
0 votes
0 answers
40 views

NFA -> DFA powerset construction worst case [duplicate]

I am wondering what generic example there is so that an NFA with n states results into a DFA with $2^n$ states after the conversion by the subset construction. I know there is the example by Hopcroft ...
sorry's user avatar
  • 155
1 vote
0 answers
20 views

an NFA whose corresponding DFA has at least $2^n - \alpha$ reachable states [duplicate]

Is there an NFA with n states so that the DFA resulting from the standard conversion of the NFA to a DFA has at least $2^n - \alpha$ reachable states for some integer $\alpha \ge 1$? Let $N= (Q, \...
Fred Jefferson's user avatar
23 votes
3 answers
7k views

How to prove that DFAs from NFAs can have exponential number of states?

All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. ...
John Hoffman's user avatar
3 votes
3 answers
15k views

does a DFA converted from NFA always contain 2^Q states?

when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states? or if some sub-sets are unreachable then they are not ...
Tom's user avatar
  • 657
2 votes
2 answers
2k views

Does NFA to DFA conversion give the minimal DFA as result?

When converting NFA to DFA, do I always get the minimal DFA or not?
Sepfins's user avatar
  • 123
5 votes
1 answer
197 views

Maximal minimal DFA for some language of n-bit strings

Notation: $M$ is a DFA; $L(M)$ is the language accepted by $M$; $\min(M)$ is the minimal automaton equivalent to $M$ derived from a minimization algorithm such as the Hopcroft algorithm; and $|M|$ is ...
ShyPerson's user avatar
  • 925
2 votes
2 answers
186 views

Given an non-deterministic finite automaton, will its determinization always have unreachable states?

Given an NFA that accepts the regular language L, will its equivalent DFA which accepts the same language L always have unreachable states. If it does, why?
GuilhermeLib's user avatar
1 vote
1 answer
227 views

Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states?

Given an alphabet $\Sigma$, let $c=|\Sigma|$. Can a set of languages $\{L_k\}$ be created, such that any DFA for $L_k$ has $\Omega(c^k)$ states and a NFA for $L_k$ exists with $O(k)$ states? I'm ...
lsparki's user avatar
  • 156
0 votes
0 answers
25 views

Are there more succint algorithm for translating NFA's to DFA's?

When translating an NFA to its deterministic equivalent, we get an exponential blowup due to the powerset construction method. I tried to search but couldn't find an appropriate question regarding ...
Algebruh's user avatar
  • 321