GATE 2024 CS1 Q.50: solution and answer

Official answer: B, CSource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

1. Read the transitions from the figure (start state 1, the only accepting state): $\delta (1,0)=2,\delta (1,1)=4$; $\delta (2,0)=3,\delta (2,1)=1$; $\delta (3,0)=1,\delta (3,1)=2$; $\delta (4,0)=1,\delta (4,1)=5$; $\delta (5,0)=4,\delta (5,1)=1$.

2. Let $d(w)=(n_0(w)-n_1(w))\mathrm{mod}3$. Assign states 1, 2, 3 to $d=0,1,2$ and states 4, 5 to $d=2,1$. Every transition then agrees: a 0 adds 1 to $d$ and a 1 subtracts 1. For example, $\delta (1,1)=4$ gives $0-1\equiv 2$; $\delta (4,1)=5$ gives $2-1=1$; $\delta (5,1)=1$ gives $1-1=0$; $\delta (4,0)=1$ gives $2+1\equiv 0$; $\delta (5,0)=4$ gives $1+1=2$; $\delta (3,1)=2$ gives $2-1=1$. So $L(M)=\{w:n_0(w)-n_1(w)\equiv 0(\mathrm{mod}3)\}$.

3. States with the same $d$ are equivalent. States 3 and 4 both have $d=2$: $\delta (3,\cdot )=(1,2)$ and $\delta (4,\cdot )=(1,5)$, and $2\equiv 5$ (both $d=1$). States 2 and 5 both have $d=1$: $\delta (2,\cdot )=(3,1)$ and $\delta (5,\cdot )=(4,1)$, and $3\equiv 4$. The minimal DFA has 3 states.

4. (A) States 2 ($d=1$) and 4 ($d=2$) differ: the string $1$ takes 2 to the accepting state 1, but takes 4 to the non-accepting state 5. They are distinguishable, so the statement is true.

5. (B) States 3 and 4 are equivalent, so they are not distinguishable. The statement is FALSE.

6. (C) States 2 and 5 are equivalent, so they are not distinguishable. The statement is FALSE.

7. (D) If $n_0(w)=n_1(w)$ then $d=0$, so $w$ ends in state 1 and is accepted. The statement is true.

8. The FALSE statements are (B) and (C).