630 views
1 votes
1 votes

Consider the regular expression $R=(a+b)^*(aa+bb)(a+b)^*$. Which one of the following regular expressions describes the same language as described by $R$?

$R_1 = (a(ba)^*(a+bb)+b(ab)^*(b+aa))(a+b)^+$

$R_2= (a(ba)^*(a+bb)+b(ab)^*(b+aa))(a+b)^*$

$R_3= (a(ba)^*+b(ab)^*)+(a+b)^*$

$R_4= (a(ba)^*+b(ab)^*)(a+b)^+$

How to approach this ?

1 Answer

Best answer
2 votes
2 votes

Regular expression given is $(a+b)^*(aa+bb)(a+b)^*$ , means all strings having double letter 

DFA 

Option B,

$R_2=\\ \left\{\underbrace{\underbrace{a}_{reach \;to\;q_1}\underbrace{(ba)^*}_{still\; at\;q_1}\underbrace{(a+bb)}_{reach\;to\;q_3}+\underbrace{b}_{reach \;to\;q_2}\underbrace{(ab)^*}_{still\; at\;q_2}\underbrace{(b+aa)}_{reach\;to\;q_3}}_{we\; are\; at \;state\; q_3}\right \} \underbrace{(a+b)^*}_{at\; q_3\; with\; anything\;including\;\epsilon}$

is correct as per DFA .

Another way is to do is using state elimination 

Remove Edges in between $q_1$ and $q_2$ and then states, we will get the exact option 

Note :

1. In option A, it is wrong because of $(a+b)^+$ , once we are at state $q_3$, then we need minimum $\epsilon$ to reach $q_3$ , that is missing in option A

2. In option C, $R_3$ can generate $\epsilon, a $ and $b$, but we need minimum $aa$ or $bb$ to reach final and as per given regular expression.

3. In option D, $R_4$ can generate $ab$ or $ba$, that should not be .

selected by

Related questions

1 votes
1 votes
2 answers
1
pC asked Jul 21, 2016
2,452 views
How to simplify a regular expression ? Please share a useful resource .Show that a+aa+b+bb* equal to $\phi$* (a+b*)
1 votes
1 votes
2 answers
2
1 votes
1 votes
2 answers
3
Ashish Roy 1 asked Sep 27, 2018
2,070 views
Given two Regular expressions are equal or not ?1) (1+01*0)* 2) 1*(01*0)* 1*Give proper explanation also.
0 votes
0 votes
1 answer
4
Himanshu Goyal asked Jan 28, 2017
622 views
Can someone give me dfa of these Regular Expressions?$0^*(1+0)^*$$0^*(1^++0)^*$Actually i am getting confused between both of them Thanks