CMI2020-A: 2

Question

Consider the following regular expressions over alphabet$\{a,b\}$, where the notation $(a+b)^+$ means $(a+b)(a+b)^*$:

$$r_1=(a+b)^+a(a+b)^*$$

$$r_2=(a+b)^*b(a+b)^+$$

Let $L_1$ and $L_2$ be the languages defined by $r_1$ and $r_2$, respectively. Which of the following regular expressions define $L_1\cap L_2$?

• A. $(a+b)^+a(a+b)^*b(a+b)^+$
• B. $(a+b)^*a\;b(a+b)^*$
• C. $(a+b)^*b(a+b)^*a(a+b)^*$
• D. $(a+b)^*a(a+b)^*b(a+b)^*$

Answer 1

C)The easiest way here is to check the minimum length string that is accepted by both $L_{1}$ & $L_{2}$, in this case it is “ba”, the only option which matches with that is C.

 

Long Method:

1. Construct minimal DFA $D_{1}$ & $D_{2}$ for $L_{1}$ & $L_{2}$ respectively.
2. Use product construction to combine 2 DFA’s and construct intersection of 2 DFA’s. Let Resultant DFA  $D_{1}\cap D_{2}=D_{r}$.
3. Now, derive regular expression from DFA $D_{r}$.

Answer 2