The Gateway to Computer Science Excellence
+2 votes
If we are having n states and m many DFAs and NFAs are possible?
in Theory of Computation by Junior (787 points) | 96 views

1 Answer

+2 votes

there are totally 'n' states, 'm' alphabets.

  • Each state can be final or non-final state (2 choices). So, there are 2^n variations.
  • for each state, there is 'm' out edges (alphabets) having 'n' destination nodes to choose from. So, each state will add 'n * m' variations which gives us n^n*m variations.

In total, we will have 2^n * n^n*m DFA's.

by Active (2.3k points)
and what about the no of NFAs?
In the above case, there should be a factor of 'n' for the number of possible initial states.(Starting state can be chosen from n states in the dfa)

Now for nfa case:

each alphabet at each state has 2^n choices to chose from(total number of subsets of states possible).So total 2^mn at each state.Thus a total of 2^(n*n*m) combining all states together.

n choices for initial state

and 2^n choices for final states as well.

This is what I think should happen!
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,688 answers
107,246 users