GATE CS 2012 Q.46 (CS Q.46): Regular Expressions, Finite Automata and Regular Languages

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

Partially completed DFA. States: ε (start), 0, 1, 00, 01, 10, 11 (all accepting) and q (non-accepting). Transitions: ε to 0 on 0, ε to 1 on 1, 0 to 00 on 0, 0 to 01 on 1, 1 to 10 on 0, 1 to 11 (arrow unlabelled in the paper), 01 to 10 on 0, 10 to 01 on 1, 11 to 11 on 1, q to q on 0 and 1. — Partially completed DFA

Table (A) where transition from 00 on 1 goes to 01; from 01 on 1 goes to 11; from 10 on 0 goes to 00; from 11 on 0 goes to 10

Table (B) where transition from 00 on 0 goes to q, on 1 goes to 01

Table (C)

Table (D) where from 00: 0 goes to q, 1 goes to 01; from 01: 1 goes to 11; from 10: 0 goes to 00; from 11: 0 goes to 10

Official answer and solution

Official answer: D
From: Official GATE 2012 answer key

Solution

Identify the state invariant of the DFA and determine the missing state transitions preventing three consecutive zeros (000).

Condition: Every substring of length 3 must contain at most two zeros. That is, the substring 000 is forbidden.
In the DFA, each state tracks the last two characters read:

State 00: last two characters were 00.
State 01: last two characters were 01.
State 10: last two characters were 10.
State 11: last two characters were 11.
State $q$ : trap/dead state entered when three consecutive zeros are detected.

Transition evaluation:

From state 00: if input is 0, three consecutive zeros 000 occur, transitioning to trap state $q$ (so $\delta(00, 0) = q$ ). If input is 1, the last two characters become 01 (so $\delta(00, 1) = 01$ ).
From state 01: on input 1, the last two characters become 11 (so $\delta(01, 1) = 11$ ).
From state 10: on input 0, the last two characters become 00 (so $\delta(10, 0) = 00$ ).
From state 11: on input 0, the last two characters become 10 (so $\delta(11, 0) = 10$ ).

Matching with candidate tables:
Table (D) specifies:

Row 00: column 01 has 1, column $q$ has 0
Row 01: column 11 has 1
Row 10: column 00 has 0
Row 11: column 10 has 0

This confirms option (D).

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 46 of 65, printed as CS Q.46
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source