GATE CS 2024 (Forenoon) — Question 50

Theory of Computation (TOC)Regular Expressions & Finite Automata (DFA/NFA Min)MSQ2 marksMedium

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 \).
Question image
Which of the following statements is/are FALSE?
  1. A
    States 2 and 4 are distinguishable in \( M \)
  2. B
    States 3 and 4 are distinguishable in \( M \)
  3. C
    States 2 and 5 are distinguishable in \( M \)
  4. D
    Any string \( w \) with \( n_0(w) = n_1(w) \) is in \( L(M) \)
Practise the full 2024-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Automata Theory (Hopcroft & Ullman)Regular languages, CFGs, pushdown automata and Turing machines.
Practise more on Regular Expressions & Finite Automata (DFA/NFA Min)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group