GATE CS 2024 Set 2 Q.22: Regular Expressions, Finite Automata and Regular Languages

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^*$

Official answer and solution

Solution

Convert the 2-state DFA (which accepts strings with an odd number of 1s) into a regular expression using Arden's theorem or state elimination.

Let the initial (left) state be $q_0$ and the accepting (right) state be $q_1$ .

From $q_0$ , the DFA reads any number of 0s ( $0^*$ ) and transitions to $q_1$ on reading the first 1 ( $0^*1$ ).
Once in the accepting state $q_1$ , the DFA can return to $q_1$ any number of times either by reading 0 directly (self-loop on $q_1$ ) or by reading 1 (moving to $q_0$ ), any number of 0s ( $0^*$ ), and another 1 (returning to $q_1$ ), which corresponds to $(0 + 10^*1)^*$ .

Hence the regular expression for the language accepted by the DFA is $0^*1(0 + 10^*1)^*$ .

Final answer

Option (A)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.