Bissoy.com
Doctors Medicines MCQs Q&A

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are Correct Answer <table border="1" cellpadding="0" cellspacing="0" style="width:258px;" width="258"> <tbody> <tr> <td style="height:24px;"> <p align="center"> </p> </td> <td style="height:24px;"> <p align="center">00</p> </td> <td style="height:24px;"> <p align="center">01</p> </td> <td style="height:24px;"> <p align="center">10</p> </td> <td style="height:24px;"> <p align="center">11</p> </td> <td style="height:24px;"> <p align="center">Q</p> </td> </tr> <tr> <td style="height:23px;"> <p align="center">00</p> </td> <td style="height:23px;"> <p align="center"> </p> </td> <td style="height:23px;"> <p align="center">1</p> </td> <td style="height:23px;"> <p align="center"> </p> </td> <td style="height:23px;"> <p align="center"> </p> </td> <td style="height:23px;"> <p align="center">0</p> </td> </tr> <tr> <td style="height:24px;"> <p align="center">01</p> </td> <td style="height:24px;"> <p align="center"> </p> </td> <td style="height:24px;"> <p align="center"> </p> </td> <td style="height:24px;"> <p align="center"> </p> </td> <td style="height:24px;"> <p align="center">1</p> </td> <td style="height:24px;"> <p align="center"> </p> </td> </tr> <tr> <td style="height:23px;"> <p align="center">10</p> </td> <td style="height:23px;"> <p align="center">0</p> </td> <td style="height:23px;"> <p align="center"> </p> </td> <td style="height:23px;"> <p align="center"> </p> </td> <td style="height:23px;"> <p align="center"> </p> </td> <td style="height:23px;"> <p align="center"> </p> </td> </tr> <tr> <td style="height:24px;"> <p align="center">11</p> </td> <td style="height:24px;"> <p align="center"> </p> </td> <td style="height:24px;"> <p align="center"> </p> </td> <td style="height:24px;"> <p align="center">0</p> </td> <td style="height:24px;"> <p align="center"> </p> </td> <td style="height:24px;"> <p align="center"> </p> </td> </tr> </tbody> </table>

The correct answer is option 4.

Key Points

 L={All the strings of 0's and 1's where every substring of 3 symbols has at most 2 zero's }

Case 1: If we go with option 1.

[ alt="toc1" src="//storage.googleapis.com/tb-img/production/21/07/toc1.png" style="width: 314px; height: 269px;">

If we take the substring 0000, it has a substring 000 containing more than 2 zero's so it is an invalid string but it is accepted by DFA. Hence this option is not possible.

Case 2: If we go with option 2.

[ alt="toc2" src="//storage.googleapis.com/tb-img/production/21/07/toc2.png" style="width: 321px; height: 277px;">

W=000 is a string and has a substring 000 having more than 2 zeros. Not in a language but it is accepted. So option 2 is not possible.

Case 3: If we go with option 3.

[ alt="toc3" src="//storage.googleapis.com/tb-img/production/21/07/toc3.png" style="width: 339px; height: 259px;">

W=001000 has a substring 000 having more than 2 zeros and accepted but it is not in the given language.

Case 4: If we go with option4.

[ alt="toc4" src="//storage.googleapis.com/tb-img/production/21/07/toc4.png" style="width: 326px; height: 245px;">

This machine accepts all the strings that were every substring of 3 symbols has at most 2 zeros.

So the correct answer is option 4.

Related Questions

Consider a network with nodes 1, 2, 3, 4, 5 and 6. The nodes are connected with directed arcs as shown in the table below. The respective costs (in INR) incurred while traversing the directed arcs are also mentioned. Directed arcs  1 → 2 1 → 3 2 → 4 2 → 5 3 → 2 3 → 4 3 → 5 4 → 5 4 → 6 5 → 6 Cost (in INR) 3 9 3 2 2 4 8 7 2 2 The second shortest path from node 1 to node 6 (i.e. the path that has the second least total cost and does not use any part of the shortest path) has a total cost (in INR) of
From the given table, what is the percentage of students scoring 40 or more, but less than 70. Scores Less than 20 Less than 30 Less than 40 Less than 50 Less than 60 Less than 70 Less than 80 No. of Students 12 19 22 31 38 46 50
Consider the DFA A given below Which of the following are FALSE? 1. Complement of L(A) is context-free. 2. L(A) = L((11*0 + 0)(0 + 1)*0*1*) 3. For the language accepted by A, A is the minimal DFA. 4. A accepts all strings over {0, 1} of length at least 2.
Given are the steps to draw a perpendicular to a line from a point outside the line, when the point is nearer the centre of line. Arrange the steps. Let AB be the line and P be the point outside the line i. Take P as centre and take some convenient radius draw arcs which cut AB at C, D. ii. Join E, F and extend it, which is perpendicular to AB. iii. From C, D with radius R1 (more than half of CD), draw arcs which cut each other at E. iv. Again from C, D with radius R2 (more than R1), draw arcs which cut each other at F.
In the following passage, some of the words have been left out. Read the passage carefully and select the correct answer for the given blank out of thefour alternatives.
That is why publicly invoking these symbols has to be an act of responsible citizenship and not self­____________ demagoguery, but thedifference can be hard to _______________. The problem with emotive symbols is that _________________ they can multiply the force ofarguments, they cannot replace the arguments__________________. All persuasion harnesses symbols but principled persuasion must alsoprovide arguments that can be _____________ debated. The problem with emotive symbols is that _________________ they can multiply the force of arguments,
J, K, L, M, N and O are six colleagues working in an NGO. J earns more than L but less than M. K earns more than J but less than N. N earns less than O but more than M. K earns less than M. Who among the six earns the most?
From the following table, how many patients were in the age group 40 – 60? Age (years) Less than 10 Less than 20 Less than 30 Less than 40 Less than 50 Less than 60 Less than 70 No. of patients 11 15 22 29 35 45 50
Read the passage carefully and choose thebest answer to each question out of the four alternativesand click the button corresponding to it. To know language is to be able to speak it; even a childwho does not yet attend school can speak his or herlanguage. In order to speak a language it is important tolisten to it and to read a few pages in it everyday. A childpicks up language and learns to talk just as (s)he learnsto walk. Walking and talking comes naturally to a child asit grows. In our country, a child may grow up speakingmore than one language, if these languages are spoken inthe home and in the neighbourhood. we call this multilingualism. A child speaks a language or languagesmuch before (s)he starts going to school. To know alanguage then is first of all to be able to speak it as easilyand naturally as a tree year old child does. Later on thechild will learn to read and write in that language. In orderto read and write in a language, one has to speak it. But itis possible to speak a language but not able to read orwrite in it. A baby does not speak until it is nine monthsold but it understands a few words at six months of age.It has been listening ever since it was born, and even alittle before that. So the first strategy in speaking alanguage is to listen. It is necessary for one to __________ the language before(s)he writes in that language.
Consider the following grammar G: P → Q + R | Q – R | Q | R Q → q | r R → r | s where P, Q, and R are non-terminal symbols, and q, r, and s are terminal symbols. Which of the following statement(s) is/are correct? S1. LL(1) can parse all strings that are generated using grammar G S2. LR(1) can parse all strings that are generated using grammar G
During a medical check-up, the heights of 40 students in a class were recorded as shown in the following table. Height (in cm) Less than 175 Less than 170 Less than 165 Less than 160 Less than 155 Less than 150 Number of students 40 35 25 16 8 4   How many students have a height of 165 cm or more?