The regular expression 10*(0*10*10*)* always generate string begin with 1 and thus does not generate string “01110” hence wrong option.
The regular expression ((0+1)*1(0+1)*1)*10* generate string “11110” which is not having odd number of 1’s , hence wrong option.
The regular expression (0*10*10*)10* is not a generating string “01”. Hence this is also wrong . It seems none of them is correct.
NOTE: Option 3 is most appropriate option as it generates the max number of strings with odd 1’s.
But option 3 is not generating odd strings. So, still it is not completely correct.
The regular expression (0*10*10*)*0*1 always generates all string ends with “1” and thus does not generate string “01110” hence wrong option.

Transition table

 

	0	1
->*q0	q0	q1
q1	q2	q0
q2	q1	q2

 

DFA of divisible by 3

The regular expression will be

Three paths to reach to final state from initial state

Path 1: self loop of 0 on q0

Path 2: q0->q1->q0  hence 11

Path 3: q0->q1->q2->q1->q0 hence 10(1+00)*01

So finally the regular expression will be

(0+11+10(1+00)*01)*

Other regular expression is (if we consider two paths)

Path 1: Path 1: self loop of 0 on q0

Path 2: q0->q1->q2*->q1->q0 

Hence regular expression

(0+1 (01*0)*1)*

 

Another regular expression is (if we consider only one path and remaining part is present inside this path as cycles)

q0->q1->q2->q1->q0

Another regular expression is

(0*(1(01*0)*1)*)*

 

So A,B, C are correct.

Option D generates string 11100 which is not accepted by FA hence wrong.

Regular expression ab*bab* +ba*aba* does not generate the string “abb” which is accepted by FA hence this is not true.
(ab*b)*ab*+(ba*a)*ba* does not generate the string “abbaa” hence this is also wrong.
(ab*b+ba*a)*(a*+b*) generates epsilon hence this is also wrong.
(ab*b+ba*a)*(ab*+ba*) is the correct regular expression.
GATE 2022 Computer Science and Information Technology (CS)

From the given DFA diagram, it clearly shows that there is no outgoing edge from node “r” so Regular expression won’t start with “0” , Option -B eliminated.
Starting state is "s" and Final state is "p".
There are two outgoing edges from the state "p".
one edge from state "p" to itself with alphabet “0” and another from State "p" to "q” and "q" to "p" with alphabet “1”
So most suitable answer is option C

→From the given question, w=a^r b^s c^t where r,s,t>0 which means that the minimum value is r=s=t=1,
→Substitute in r=s=t=1 in w then L= abc
→So option D gives the regular expression abc

Option A do not contain xy which is generated by the grammar.
Option B do not contain xy which is generated by the grammar.
Option C do not contain xy which is generated by the grammar.

The given regular expression is not equal to option D.

L = { 1, 01, 11, 111, 001, ............}
Option(A) is not correct because it can generate “10” which is not ending with “1”.
Option(B): It can’t generate “1” which is a string belongs to given language L. So it is not a correct option.
Option(C) : It is the correct option because it can generate all the strings generated by a given language.
Option(D): It is not the correct answer because it can’t generate strings like 1,11,........

r={a,aa,ab,aaa,aab,aba,aaab,......}
s={aa,ab,aaa,aab,aba,aaab,......}
t={ab,aab,aaab,....}
If you notice then r⊇s⊇t

(a+b)* is a universal set which can generate all the strings possible over the alphabet “a” and “b”.
(a+b)* = (a* +b)*= (a+b*)=(a*b*)*= (a* +b*)*= a*(ba*)*=b*(ab*)*