and what about the no of NFAs?

The Gateway to Computer Science Excellence

+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.

0

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!

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!

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,688 answers

199,285 comments

107,246 users