20k 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$?
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? ...
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 ...
25 views

Worst case of subset construction (NFA to DFA) [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 ...
22 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 ...
6k 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. ...
13k 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 ...
1k 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?
88 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 ...
111 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?
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 ...