GATE CS 2024 Set 2 — Question 22

MCQ+1 / -0.33MediumDFA to REFinite Automata & Regular LanguagesTheory of Computation

Theory of Computation → Finite Automata & Regular Languages → DFA to RE

Last updated 20 August 2026

Question

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

0^*1(0 + 10^*1)^*

0^*(10^*11)^*0^*

0^*1(010^*1)^*0^*

0(1 + 0^*10^*1)^*0^*

(A) 0^ 1(0 + 10^ 1)^

The DFA has two states. Let the start state be

q_0

and the accepting state be

q_1

.
Transitions:

We want to find the regular expression for strings accepted by this DFA (ending in

q_1

Path analysis:

1.To reach

q_1

from

q_0

for the first time, we must read any number of 0s followed by a 1:

0^*1

2.Once in

q_1

, we can stay in

q_1

by reading 0s (

0^*

) or by going back to

q_0

and returning to

q_1

. The path

q_1 \to q_0 \to q_1

corresponds to reading a 1, then any number of 0s (loop at

q_0

), then a 1. So, the cycle is

10^*1

3.Therefore, from

q_1

, we can loop any number of times using either

0

10^*1

. This corresponds to

(0 + 10^*1)^*

Combining these, the total regular expression is the concatenation of the initial path and the loop:

L = 0^*1(0 + 10^*1)^*

This matches option (A).