483 views
0 votes
0 votes

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 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

1 Answer

Best answer
1 votes
1 votes

" every substring of 3 symbols has at most two zeros "
Here one this is clear, if we are at state 00, we wont accept another 0, i.e we move onto dead state whenever we see 0 i.e q, only option c and d satisfy it,  so a and b are eliminated.
Now at state 10 we have already seen one 0, so if we see another 0, we move onto 00, in option c we remain at 10, which is wrong since in that case we can accept 10001, where substing has more than 2 zero.
So option D is correct.

selected by

Related questions