#NFA and DFA

Question

Which of the following statement(s) are true about NFA & DFA?
(i) NFA is more powerful than DFA but DFA is more efficient than NFA.
(ii) NFA will respond for only valid inputs and no need to respond for invalid inputs.
(iii) There is no concept of dead states and complement in NFA.
(iv) NFA is a parallel computing system where we can run multiple threads concurrently.
(a) only (i) & (ii) are true (b) only (ii) & (iii) are true

(c) only (iii), (iv) & (i) are true (d) All statements are true

Comments

Thanks all of u!

Answer 1

(i) NFA is more powerful than DFA but DFA is more efficient than NFA.

      This is False, Power of NFA and DFA is same.

(ii) NFA will respond for only valid inputs and no need to respond for invalid inputs.

    This is true, NFA go final states only for valid i/p's.

(iii) There is no concept of dead states and complement in NFA.

       This is true, There is no concept of Dead State, because NFA nothing says about invalid i/p's, and complement also not valid for NFA

(iv) NFA is a parallel computing system where we can run multiple threads concurrently.

     This is true, NFA uses parallel Computing System, while accepting a string, if any path lead to termination in Final State, then it stops all other computing, simply says " String is Valid "

Answer 2

1)power of nfa= power of the dfa coz for every nfa there is a dfa.therefore its wrong

2)nfa and dfa both responds to only valid inputs bcoz they are finite. therefore true

3)there is no dead states in nfa due to non determinstic in nature and no complement concept.therefore true

4)In nfa,for every state  there is could one or more than one input alphabet at a time.not necesserily always every state have all the input alphabet concurrently..

therefore ans is b

Answer 3

Option A :

Power in Automata Theory is defined by the "Acceptance of the language family".

Both DFAs and NFAs accept the Regular languages family. Hence, Power is Same.

But NFAs are more efficient than DFAs in the terms of Time and Space. 

Option B :

NFAs are allowed to have Dead configurations, Hence, they (NFA) will respond for only valid inputs and no need to respond for invalid inputs.

Option C :

 "There is no concept of dead states and complement in NFA." ..  Technically, It is False as Every DFA is also an NFA. 

Option D :

"NFA is a parallel computing system where we can run multiple threads concurrently." . Yes. True as NFA is Non-deterministic and at each step, It can split into multiple ways and run simultaneously.