The GATE Grind

GATE 2024 CS (CS2) – Question 22

Theory of Computation · Regular Expressions and Finite Automata · 1 mark · Multiple choice

Which one of the following regular expressions is equivalent to the language accepted by the DFA given below? (Two states: start state q0 (non-accepting) with self-loop on 0 and transition on 1 to q1; accepting state q1 with self-loop on 0 and transition on 1 back to q0.)

  1. $0^*1(0+10^*1)^*$
  2. $0^*(10^*11)^*0^*$
  3. $0^*1(010^*1)^*0^*$
  4. $0(1+0^*10^*1)^*0^*$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $0^*1(0+10^*1)^*$

Explanation

The DFA accepts strings with an odd number of 1s. From q0: 0*1 reaches q1; then any loop returning to q1 is either 0 or 1 0* 1. So 0*1(0+10*1)*.