GATE CSE 2024 | Set 2 | Question: 12

Question

​​​​Which one of the following regular expressions is equivalent to the language accepted by the $\text{DFA}$ given below?

• A. $0^{*} 1\left(0+10^{*} 1\right)^{*}$
• B. $0^{*}\left(10^{*} 11\right)^{*} 0^{*}$
• C. $0^{*} 1\left(010^{*} 1\right)^{*} 0^{*}$
• D. $0\left(1+0^{*} 10^{*} 1\right)^{*} 0^{*}$

Answer 1

L(final state) = reach at final and stay at final

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

So, option A seems to be correct.

Answer 2

The given DFA accepts all & only binary strings containing Odd number of $1's.$

So, option A is correct regular expression.

Option B Counter-Example: Generates empty string.

Option C Counter-Example: Doesn't generate $10011.$

Option D Counter-Example: Doesn't generate $1.$

WHY Option A: Go to the final state by reading $0^*1$, then stay in the final state by making either loop $0$ or loop $10^*1$ in any order, any number of times. So, $0^*1(0 + 10^*1)^*$ is the correct regular expression.