The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes
If we are having n states and m many DFAs and NFAs are possible?
in Theory of Computation by Junior (771 points) | 89 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?

Related questions

0 votes
1 answer
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,092 questions
55,276 answers
86,086 users