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: (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.

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →