I came across the fact that

The number of DFAs that can be constructed for $n$ number of states and alphabet containing $m$ symbols is $n\times (\color{red}{n}^m)^n \times 2^n$

So I was wondering whats about NFA? I mean how many NFA can be constructed for for $n$ number of states and alphabet containing $m$ symbols. Surprisingly quick google reveals that this is not discussed anywhere online except at this post, which is somewhat unanswered. So I tried to answer it myself as follows:

  • (Same as for DFA) Number of possible start states $=n$ (assuming NFA can have only one start state)
  • (Same as for DFA) Number of final states $=2^n$, since any subset of states can be set of final states
  • (Same as for DFA, except that $n$ is replaced with $2^n$) For each of $m$ symbols, transition can happen to any number states. That is, number of subsets of $n$ states is $2^n$. So, for $m$ symbols, it will be $(2^n)^m$. This happens for each of $n$ states, that is their are $n$ source states. So total number of transitions will be $((\color{red}{2^n})^m)^n$.

So the final count turns out to be $n\times ((\color{red}{2^n})^m)^n \times 2^n$.

Am I correct with this?

  • $\begingroup$ Yes, this seems correct. $\endgroup$ – Yuval Filmus Jun 24 '18 at 19:08
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jun 24 '18 at 19:16
  • $\begingroup$ I know that yes-no answer questions are really discouraged, but I was unable to understand how can I get this confirmed. I was anxious if the question will be downvoted and closed. But no one discussed this online. So I put my own thoughts / calculations instead of just asking one liner, thinking at least that will prevent question from getting ill received. $\endgroup$ – anir Jun 24 '18 at 19:30
  • $\begingroup$ @YuvalFilmus just to confirm again, does the same for non deterministic pushdown automata is $n\times ((2^n)^{\color{red}{l}m})^n\times 2^n$, where $l$ is the number of symbols in stack alphabet? $\endgroup$ – anir Jun 24 '18 at 20:00
  • $\begingroup$ I think you can answer these questions on your own. $\endgroup$ – Yuval Filmus Jun 24 '18 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.