retagged by
239 views
1 votes
1 votes

Which of the following statements is NOT true?

  1. $DFA$ makes precisely one transition for an input.
  2. $NFA$ can make more than one transition for an input.
  3. On a given string ‘w’, $DFA$ terminates exactly in one state.
  4. 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.
retagged by

1 Answer

Best answer
2 votes
2 votes
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.
selected by
Answer:

Related questions

2 votes
2 votes
1 answer
2
0 votes
0 votes
1 answer
3
Bikram asked Feb 9, 2017
308 views
Consider the grammar:$S\rightarrow$ $PQ | SQ | PS$$P\rightarrow k$$Q\rightarrow m$To get a set of $n$ terminals, the number of productions to be used are ______. $n^{2...