GATE CS 2024 Set 1 — Question 50

To identify the FALSE statement(s), we analyze the given DFA $M$:1. DFA Components:

• States $Q = \{1, 2, 3, 4, 5\}$
• Start state $q_0 = 1$
• Final states $F = \{1\}$ (indicated by the double circle)
• Transitions $\delta$:
• $\delta(1, 0) = 2, \delta(1, 1) = 4$
• $\delta(2, 0) = 3, \delta(2, 1) = 1$
• $\delta(3, 0) = 2, \delta(3, 1) = 3$
• $\delta(4, 0) = 1, \delta(4, 1) = 5$
• $\delta(5, 0) = 5, \delta(5, 1) = 4$

2. Evaluate Distinguishability:
Two states $p, q$ are distinguishable if there exists a string $x$ such that exactly one of $\delta(p, x), \delta(q, x)$ is in $F$.

• (A) States 2 and 4: $\delta(2, 1) = 1 \in F$ and $\delta(4, 1) = 5 \notin F$. Thus, 2 and 4 are distinguishable. Statement (A) is TRUE.
• (B) States 3 and 4: $\delta(3, 0) = 2 \notin F$ and $\delta(4, 0) = 1 \in F$. Thus, 3 and 4 are distinguishable. Statement (B) is TRUE.
• (C) States 2 and 5: $\delta(2, 1) = 1 \in F$ and $\delta(5, 1) = 4 \notin F$. Thus, 2 and 5 are distinguishable. Statement (C) is TRUE.

3. Evaluate Language Property (D):

• Statement (D) claims that any string with an equal number of 0s and 1s is accepted.
• Consider the string $w = 0011$. Here $n_0(w) = 2$ and $n_1(w) = 2$.
• Trace $w$ in the DFA: $1 \xrightarrow{0} 2 \xrightarrow{0} 3 \xrightarrow{1} 3 \xrightarrow{1} 3$.
• The final state reached is 3, which is not a final state ($3 \notin F$).
• Since $0011 \notin L(M)$, statement (D) is FALSE.

Conclusion: Only statement (D) is false.