# CMI2020-A: 2

37 views

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$?

1. $(a+b)^+a(a+b)^*b(a+b)^+$
2. $(a+b)^*a\;b(a+b)^*$
3. $(a+b)^*b(a+b)^*a(a+b)^*$
4. $(a+b)^*a(a+b)^*b(a+b)^*$
in Others
edited

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}$.

edited

## Related questions

1
67 views
Which of the following languages over the alphabet $\{0,1\}$ are $not$ recognized by deterministic finite state automata $(DFA)$ with $three$ states? Words which do not have $11$ as a contiguous subword Binary representations of multiples of three Words that have $11$ as a suffix Words that do not contain $101$ as a contiguous subword
A boolean function on $n$ variables is a function $f$ that takes an n-tuple of boolean values $x \in \{0,1\}^n$ as input and produces a boolean value $f(x)\in \{0,1\}$ as output. We say that a boolean function $f$ ... of symmetric boolean functions on $n$ variables? $n+1$ $n!$ $\displaystyle \sum^n_{i=0} \begin{pmatrix} n\\i \end{pmatrix}$ $2^{n+1}$