The GATE Grind

GATE 2012 CS (CS1) – Question 56

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Multiple choice

Over {0,1}, every three-symbol substring must contain at most two zeros; all words shorter than three are included. The partial DFA is shown. Which option supplies its missing arcs?

Diagram for GATE 2012 CS (CS1) question 56
  1. 00→00 on 1; 00→01 on 0; 01→11 on 1; 10→00 on 0; 11→10 on 0
  2. 00→01 on 0; 00→q on 1; 01→01 on 1; 10→11 on 0; 11→01 on 0
  3. 00→01 on 1; 00→q on 0; 01→01 on 1; 10→10 on 0; 11→01 on 0
  4. 00→01 on 1; 00→q on 0; 01→11 on 1; 10→00 on 0; 11→10 on 0

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) 00→01 on 1; 00→q on 0; 01→11 on 1; 10→00 on 0; 11→10 on 0

Explanation

The forbidden substring is 000. States labelled two bits remember the most recent two-symbol suffix; appending a bit shifts that suffix. Thus 00 on 0 enters dead q and on 1 goes to 01. Also 01 on 1→11, 10 on 0→00, and 11 on 0→10. These missing arcs are D.

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →