in Theory of Computation
453 views
1 vote
1 vote

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 ?

in Theory of Computation
453 views

2 Comments

Prasanna , is it $(a+b)^+$ in option a and $(a+b)^*$ in option 2
0
0
Yes sir
0
0

1 Answer

2 votes
2 votes
Best answer

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

1 comment

mind = blown sir
0
0