intersection of two regular expressions

Question

If we have two regular expressions $L_1 = aba^*b^*c^*$ and $L_2 = a^*b^*c^*ab$, how do we get $L_1 \cap L_2$ get? I found the answer to be $L_1 \cap L_2 = ab + abab$ But I don't know how it was arrived at.

Answer 1

In this particular example, you know that a word in $L_1$ is of the form $aba^{n_1}b^{n_2}c^{n_3}$, and you know that a word in $L_2$ is of the form $a^{m_1}b^{m_2}c^{m_3}ab$. Thus $w\in L_1\cap L_2$ must be such that $$w=aba^{n_1}b^{n_2}c^{n_3}=a^{m_1}b^{m_2}c^{m_3}ab$$ for some nonnegative integers $n_i,m_i\ge0$. Because the word starts with $ab$ this enforces $m_1\in\{0,1\}$. So we have two cases:

• If $m_1=0$, then $m_2=m_3=0$ necessarily and so $\fbox{$w=ab$}$ (we have $n_1=n_2=n_3=0$ as well).
• Otherwise $m_1=1$, and since the word cannot end with $c$'s we get $n_3=0$, then $m_3=0$ (no $c$ at all in the word). The equality then reduces to $$ba^{n_1}b^{n_2}=b^{m_2}ab.$$ Since there is only one $a$ in the right-hand side, it follows that $n_1=1$, then $n_2=1$ (there can only be one $b$ after $a$) and finally $m_2=1$. So $\fbox{$w=abab$}$.

The above analysis shows that $L_1\cap L_2\subseteq\{ab,abab\}$ and it is clear that these two words match both regular expressions.

---

A general (naive) algorithm: convert $L_1$ and $L_2$ into finite automatas $\cal A_1$ and $\cal A_2$ recognizing these languages, then construct the automaton $\cal A$ recognizing the intersection $L_1\cap L_2$, and then convert back $\cal A$ into a regular expression.