GATE CS 2024 Set 2 | Question 22

MCQ · 1 mark · −0.33

Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?

A two-state DFA: the start state on the left, which is not accepting, has a self-loop on 0 and an arc on 1 to the accepting state (double circle) on the right. The accepting state has a self-loop on 0 and an arc on 1 back to the start state.
  1. Option A: \(0^{*}1(0 + 10^{*}1)^{*}\) (correct)
  2. Option B: \(0^{*}(10^{*}11)^{*}0^{*}\)
  3. Option C: \(0^{*}1(010^{*}1)^{*}0^{*}\)
  4. Option D: \(0(1 + 0^{*}10^{*}1)^{*}0^{*}\)

Answer

(A)

Explanation

Call the start state \(q_0\) and the accepting state \(q_1\). A 0 never changes the state and a 1 always switches it, so the DFA accepts exactly the strings with an odd number of 1s.

Option A follows the DFA directly. \(0^{*}1\) stays in \(q_0\) on 0s and moves to \(q_1\) on the first 1. From then on, every way of leaving \(q_1\) and coming back is either the self-loop 0 or a trip \(10^{*}1\) through \(q_0\), so \((0 + 10^{*}1)^{*}\) covers every continuation that ends in \(q_1\).

  • B accepts the empty string, which has no 1s, and cannot produce 1.
  • C cannot produce 111, which has three 1s.
  • D forces a leading 0, so it misses 1, and it accepts 0.

Answer: A