Question

Consider the 5-state DFA \( M \) accepting the language \( L(M) \subseteq (0+1)^* \) shown below. For any string \( w \in (0+1)^* \), let \( n_0(w) \) be the number of \( 0 \)'s in \( w \) and \( n_1(w) \) be the number of \( 1 \)'s in \( w \). \begin{center} \includegraphics[width = 6cm]{50.png} \end{center} Which of the following statements is/are FALSE?

• A. States 2 and 4 are distinguishable in \( M \)
• B. States 3 and 4 are distinguishable in \( M \)
• C. States 2 and 5 are distinguishable in \( M \)
• D. Any string \( w \) with \( n_0(w) = n_1(w) \) is in \( L(M) \)

Hint:

To check distinguishability in a DFA, consider input strings that lead to different acceptance behaviors. Indistinguishable states behave identically for all input strings.

Answer 1

The Correct Option is B

Step 1: Analyze the DFA and its language.
The DFA \( M \) accepts strings based on a condition related to the counts of \( 0 \)'s and \( 1 \)'s. Transitions lead to different states depending on the parity (even or odd) of \( n_0(w) \) and \( n_1(w) \). Distinguishability of states is determined by whether they lead to different acceptance behavior for any input string. Step 2: Verify each statement.
Option (1): States 2 and 4 are distinguishable because they behave differently for certain strings. For example, adding more \( 1 \)'s or \( 0 \)'s leads to different final states. This is true.
Option (2): States 3 and 4 are indistinguishable because they behave identically for all input strings. This is false.
Option (3): States 2 and 5 are indistinguishable because they represent equivalent conditions for \( n_0(w) \) and \( n_1(w) \). This is false.
Option (4): Any string \( w \) with \( n_0(w) = n_1(w) \) is accepted by \( M \) because the DFA ensures balance between the counts of \( 0 \)'s and \( 1 \)'s. This is true. Final Answer: \[ \boxed{(2), (3)} \]