The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
33 views
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
asked in Theory of Computation by Junior (747 points) | 33 views
0
Thanks all of u!

3 Answers

0 votes
(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 "
answered by Loyal (7k points)
0 votes
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
answered by (183 points)
0 votes

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.

answered by Boss (16.6k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,994 questions
44,570 answers
126,774 comments
43,636 users