Which statement is true?

Question

Consider dfa , nfa & ∈-nfa accepting the same language,

choose the correct statement?

a) All three models always have the same number of states. 

b) The minimal dfa for all three machines is unique.

c) The nfa model always has more number of states than the dfa.

d) The ∈-nfa always has the maximum number of states.

Answer 1

Minimal DFA always unique.

Rest of three option may or may not true. No relation between no of states in DFA,NFA and epsilon NFA. (Max no of states in DFA of n state NFA is 2^n. But that is maximum)

Comments

"No relation" is not correct. We have $2^n$ as upper bound for the no. of states in DFA. Also, minimal DFA is unique assuming states are not labelled- usually we count them as separate while counting the no. of different DFAs possible.

Answer 2

1) false.
beacuse no of states in DFA always >=no of states in NFA(max no of states in DFA is 2^n for a NFA with n states)
so it might be true for some cases,but not always.

2) true. for same language minimal DFA is always unique.

3) false. no of states in NFA can be less or equal to no of states in DFA
4) false. you convert e-NFA to NFA and NFA to DFA. and we know that DFA always has maximum or equal no of states compared to NFA.

Answer 3

1- all the dfa are equal in power.

2- if the dfa contain n states then nfa contain from n to 2^n.

  why n ? every dfa is a nfa so  take an dfa and say it is an nfa . so minimum states n.

2^n because i can go to any number of states from ( 0,1,2,3,4,5...n) like ( $\phi$, A, B, AB...) which is basically power set of n. so 2^n.

3- $\null$ in null nfa also has same number of states as nfa.

4- One dfa can accept more than one languages but a minimal dfa can only accept a unique language .

5- the minimal dfa of a nfa , dfa , $\null$is unique .

6- number of states in dfa <= nfa = $\null$ nfa .

Answer 4

The minimal dfa for all three machines is unique