Register

NFA DFA

1,986 views
0 0 votes
My doubt is it always true that the  number of state in NFA is always less than number of state required in DFA for all language which are regular?

1 Answer

0 0 votes
MAX NO. OF DFA STATES FOR N NFA STATES IS 2^n

IT MEANS AT MINIMUM LEVEL BOTH NFA AND DFA EQUAL

BUT AT MAX AROUND 2^n STATES
Voting & Accepting an answer helps improve the community
← Previous · masters theoremNext → · Functionally complet...
← Previous in category · Non deterministic au...Next in category → · Automaton
Position:
Show:

Related questions

2 2 votes
1 1 answer
162
162 views
GO Classes asked Oct 1
162 views
GO Classes DPP | GATE CS | Theory of Computation | NFA to DFA
Consider the NFA shown below, where $A$ is the initial state and $D$ is the only accepting state.Which DFA accepts the same language?Initial state: $A$Accepting states: $...
0 0 votes
1 1 answer
92
92 views
GO Classes asked Oct 1
92 views
GO Classes DPP | GATE CS | Theory of Computation | NFA to DFA
Let an NFA have $\mathbf{6}$ states.After applying the standard NFA-to-DFA conversion algorithm, what is the maximum possible number of states in the resulting DFA, inclu...
4 4 votes
2 2 answers
260
260 views
GO Classes asked Jul 10
260 views
GO Classes DPP | GATE CS | Theory of Computation | DFA-NFA Equivalence
Which of the following is true?A language $L$ is accepted by DFA iff it is accepted by some $\epsilon$-NFA. A language $L$ is accepted by $\epsilon$-NFA iff it is accepte...
6 6 votes
4 4 answers
328
328 views
GO Classes asked Jul 8
328 views
GO Classes DPP | GATE CS | Theory of Computation | NFA to DFA
Which of the following statements are correct?There is a $2^k$-state DFA for every $k$-state NFA. There is a $k$-state DFA for every $2^k$-state NFA. There is a $k$-state...