Register

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

• retagged by
679 views
1 1 vote

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.

1 Answer

Best answer
2 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
Voting & Accepting an answer helps improve the community
Answer:
← Previous · Test by Bikram | Moc...Next → · Test by Bikram | Moc...
← Previous in category · Test by Bikram | Moc...Next in category → · Test by Bikram | Moc...
Position:
Show:

Related questions

2 2 votes
1 answers 1 answer
1.2k
1.2k views
Bikram asked Feb 9, 2017
1,183 views
Test by Bikram | Mock GATE | Test 3 | Question: 36
Consider the following regular languages given below: L1 : Languages that accept strings over $\sum \left (a,b \right )$ , such that length of string is greater than $1$,...
2 2 votes
1 answers 1 answer
1.0k
1.0k views
Bikram asked Feb 9, 2017
1,048 views
Test by Bikram | Mock GATE | Test 3 | Question: 33
Consider the following deterministic finite state automaton $M$:Let $S$ denote the set of $seven$ $bit$ binary strings in which the first, the fourth, and the last bits a...
0 0 votes
1 answers 1 answer
737
737 views
Bikram asked Feb 9, 2017
737 views
Test by Bikram | Mock GATE | Test 3 | Question: 11
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...
2 2 votes
1 answers 1 answer
839
839 views
Bikram asked Feb 9, 2017
839 views
Test by Bikram | Mock GATE | Test 3 | Question: 65
Read the following statements carefully:“Studies show that there is hardly any difference between human beings and apes in their psychological capacities. The studies are...