Test by Bikram | Mock GATE | Test 3 | Question: 16

Question

Which of the following statements is NOT true?

• A. $DFA$ makes precisely one transition for an input.
• B. $NFA$ can make more than one transition for an input.
• C. On a given string ‘w’, $DFA$ terminates exactly in one state.
• D. To check if the input is accepted by an $NFA$, it does not make more than one transition for an input symbol from each state.

Answer 1

A. DFA makes precisely one transition for an input symbol from each state. The statement is correct. The statement is implied from DFA definition

B. NFA makes more than one transition for an input symbol from each state. To check if the string is accepted by NFA we need to check more than one path labeled w and select one which terminates at a final state. The statement is correct.

C.  The statement is true. DFA has a unique transition for a give input symbol w and state q to other state. This suggests that on a given string w, DFA terminates in one and only state.

D.  The statement is false. Read explanation about statement 2.

Comments

D statement is not complete

---

now corrected, Thanks.