Linked Questions
12 questions linked to/from NFA with exponential number of states when determinized
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$?
- 163
2
votes
2
answers
2k
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? ...
0
votes
0
answers
43
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 ...
0
votes
0
answers
33
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 ...
- 155
1
vote
0
answers
19
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, \...
- 279
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. ...
- 397
3
votes
3
answers
14k
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 ...
- 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?
- 123
5
votes
1
answer
168
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 ...
- 911
2
votes
2
answers
174
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?
- 23
1
vote
1
answer
156
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 ...
- 156
0
votes
0
answers
24
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 ...
- 301