Problem Detail: We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in worst case gives us $2^S$ states, if our NFA had $S$ states. My question is: what is determining the worst case scenario? Here’s a transcription of an algorithm in case of ambiguity: Let $A = (Q,Sigma,delta,q_0,F)$ be a NFA. We construct a DFA $A' = (Q',Sigma,delta',q'_0,F')$ where
- $Q' = mathcal{P}(Q)$,
- $F' = {S in Q' | F cap S neq emptyset }$,
- $delta'(S,a) =bigcup_{s in S} (delta(s,a) cup hat delta(s,varepsilon))$, and
- $q'_0 = {q_0} cup hat delta(q_0, varepsilon)$,
where $hatdelta$ is the extended transition function of $A$.
Asked By : Daniil
Answered By : Janoma
The algorithm you refer to is called the Powerset Construction, and was first published by Michael Rabin and Dana Scott in 1959. To answer your question as stated in the title, there is no maximal DFA for a regular language, since you can always take a DFA and add as many states as you want with transitions between them, but with no transitions between one of the original states and one of the new ones. Thus, the new states will not be reachable from the initial state $q_0$, so the language accepted by the automaton will not change (since $hatdelta(q_0,w)$ will remain the same for all $winSigma^*$). That said, it is clear that there can be no conditions on a NFA for its equivalent DFA to be maximal, since there is no unique equivalent DFA. In contrast, the minimal DFA is unique up to isomorphism. A canonical example of a language accepted by a NFA with $n+1$ states with equivalent DFA of $2^n$ states is $$L={win{0,1}^*:|w|geq ntext{ and the (n)-th symbol from the last one is 1}}.$$ A NFA for $L$ is $A=langle Q,{0,1},delta,q_0,{q_{n+1}}rangle$, with $delta(q_0,0)={q_0}$, $delta(q_0,1)={q_0,q_1}$ and $delta(q_i,0)=delta(q_i,1)={q_{i+1}}$ for $iin{1,ldots,n}$. The DFA resulting of applying the powerset construction to this NFA will have $2^n$ states, because you need to represent all $2^n$ words of length $n$ as suffixes of a word in $L$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/130
