Question 8850 – Theory-of-Computation

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: D

Question 27 Explanation:

All states are final states except “q” which is trap state. The strings in language are such that every substring of 3 symbol has at most two zeros. It means that we cannot have 3 consecutive zeros anywhere in string. In the given DFA total four transition is missing, so we have to create the missing transition keeping the criteria in mind that “three consecutive zeros” will lead to trap state “q” as after 3 consecutive zeros whatever comes after that in the string, the string is going to be rejected by DFA.
From the state “00” it is clear that if another “0” comes then the string is going to be rejected, so from state “00” the transition with input “0” will lead to state “q”. So option A and B are eliminated.
Now option C has the self loop of “0” on state “10” which will accept any number of zeros (including greater than three zeros), hence the C option is also wrong. We left with only option D which is correct option.