How can one tell number of states in NFA from states of an arbitrary DFA

The Gateway to Computer Science Excellence

0 votes

0

@vikas @dharmendra @mk Utkarsh

Im not able to understand this concept.

Please explain.

As per my understanding in DFA, For N states there can be N transition so N states should be there and for NFA for N states there can be 2 ^N transition so 2^N states.

Please suggest

Im not able to understand this concept.

Please explain.

As per my understanding in DFA, For N states there can be N transition so N states should be there and for NFA for N states there can be 2 ^N transition so 2^N states.

Please suggest

0

Mayankprakash ignore this question because they are not talking about minimal DFA

if they would have been talking about minimal DFA with $2^N$ states then states in the corresponding NFA can range between $N$ and $2^N$

from this information we can eliminate A and D

but then read the first line of this comment :p

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

50,644 questions

56,505 answers

195,555 comments

101,042 users