GATE 2024 CS (CS1) – Question 50
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?

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) States 3 and 4 are distinguishable in $M$; (C) States 2 and 5 are distinguishable in $M$
Explanation
Look at what each state remembers. With $v=(n_0-n_1)\bmod 3$:
- state 1: $v=0$ (start and accepting); state 2: $v=1$; state 3: $v=2$ (via 0's, with 1 going back one step: $3\xrightarrow{1}2$, $2\xrightarrow{1}1$);
- state 4: $v=2$ ($1\xrightarrow{1}4$ means $-1\equiv2$); state 5: $v=1$ ($4\xrightarrow{1}5$, $5\xrightarrow{1}1$; and $4\xrightarrow{0}1$, $5\xrightarrow{0}4$).
So the DFA accepts exactly the strings with $n_0-n_1\equiv0\pmod3$. States 3 and 4 are equivalent (both $v=2$), and states 2 and 5 are equivalent (both $v=1$).
Check each statement (we want the **false** ones):
- (A) 2 and 4: the string `1` takes 2 to the accepting state 1 but takes 4 to state 5. Distinguishable, so the statement is **true**.
- (B) 3 and 4 distinguishable: they are equivalent, so the statement is **false**.
- (C) 2 and 5 distinguishable: they are equivalent, so the statement is **false**.
- (D) $n_0=n_1$ gives $v=0$, so $w\in L(M)$. **True**.
False statements: B, C.