The GATE Grind

GATE 2024 CS (CS1) – Question 50

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

Consider the 5-state DFA $M$ accepting the language $L(M)\subset(0+1)^*$ shown in the figure (start/accepting state 1; 1-0->2, 2-0->3, 3-0->1, 2-1->1, 3-1->2, 1-1->4, 4-1->5, 5-1->1, 4-0->1, 5-0->4). For any string $w$ let $n_0(w)$ be the number of 0's and $n_1(w)$ the number of 1's. Which of the following statements is/are FALSE?

Diagram for GATE 2024 CS (CS1) question 50
  1. States 2 and 4 are distinguishable in $M$
  2. States 3 and 4 are distinguishable in $M$
  3. States 2 and 5 are distinguishable in $M$
  4. Any string $w$ with $n_0(w)=n_1(w)$ is in $L(M)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) States 2 and 4 are distinguishable in $M$; (B) States 3 and 4 are distinguishable in $M$

Explanation

The DFA tracks (n0 − n1) mod 3: states 1,2,3 count surplus 0s and states 1,4,5 count surplus 1s. States 2 and 4, and 3 and 5 are indistinguishable via symmetry with respect to acceptance behavior, so A and B are false; equal counts return to state 1 so D is true.