Consider the 5-state DFA M accepting the language L(M) (0 + 1)^* shown below. For any string w ∈ (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.

States 3 and 4 are distinguishable in M

States 2 and 5 are distinguishable in M

States 2 and 4 are distinguishable in M

States 3 and 4 are distinguishable in M

States 2 and 5 are distinguishable in M

Any string w with n_0(w) = n_1(w) is in L(M)

GATE CSE 2024 Session 1 Q50: Distinguishable states in a 5-state DFA

Theory of Computation
2 marks
MSQ
No negative marking

Consider the 5-state 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$ 's in $w$ and $n_1(w)$ be the number of $1$ 's in $w$ .

DFA with start and accepting state 1. From 1: on 0 to 2, on 1 to 4. From 2: on 0 to 3, on 1 to 1. From 3: on 0 to 1, on 1 to 2. From 4: on 0 to 1, on 1 to 5. From 5: on 0 to 4, on 1 to 1 — Tap the figure to enlarge

Which of the following statements is/are FALSE?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: B, C (official GATE 2024 final answer key)

Concept used: Two states are distinguishable if some string leads one to acceptance and the other not.

First step: Check single-symbol suffixes first: from 2, input 1 reaches the accepting state; see what 1 does from 4.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2024 Session 1 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2024 Session 1 questions →

GATE CSE 2024 Session 1 Q50: Distinguishable states in a 5-state DFA

Question

Full step-by-step solution

More Theory of Computation PYQs