Question

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 complete DFA that accepts this language is shown below.

The missing arcs in the DFA are

• A.

  	00	01	10	11	q
  00	1	0
  01				1
  10	0
  11			0

• B.

  	00	01	10	11	q
  00		0			1
  01		1
  10				0
  11		0

• C.

  	00	01	10	11	q
  00		1			0
  01				1
  10	0
  11			0

  
  
• D.

  	00	01	10	11	q
  00		1			0
  01		1
  10			0
  11		0

Answer 1

The correct option is C

	00	01	10	11	q
00		1			0
01				1
10	0
11			0

Notice that the state names are given based on ending bits of the string, which has been processed.

The arc from 00 labeled "0" should go to trap state q (since at most 2 zeros are allowed in any substring).

Based on this fact, option (a) and (b) are incorrect. Between option (c) and (d), if you look at arc labeled "1" from state 01, this arc should go to state 11 since the string at this point is ending with 11. So option (c) is wrong and option (d) is correct.

The dfa corresponding to correct option (d) is shown below with missing arrows shown in dotted lines.