GATE CSE 2024 | Set 1 | Question: 40

Question

​Consider the $5$ -state $\text{DFA}$. $M$ accepting the language $L(M) \subset(0+1)^{*}$ shown below. For any string $w \in(0+1)^*$ let $n_0(w)$ be the number of $0^{\prime} s$ in $w$ and $n_1(w)$ be the number of 1 's in $w$.

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)$ 

Answer 1

Correct Answer - Option B,C

When we try to minimize the DFA given we can notice that states 3 and 4 have same inward and outward transitions and are indistinguishable, same for the states 2, 5. 

States 2 and 4 are distinguishable, because they have different transitions from state 1. 

In the final minimised DFA, we can clearly see that there are three states 1 , 2 , 4. For any given string with equal number of 1s and 0s, it will be accepted by the DFA

Comments

@phaniphani and @GO Classes  so why option D is NOT true ?

---

@Swarnava Bose Question asked to mark False statements