# Computing $(a+b)^*c^*(a+b)^* \cap (b+c)^*a^*(b+c)^*$

how can I find the regular expression for this intersection ? I've tried to find words but it did not help too much..

$$[\; (a+b)^* c^* (a+b)^* \;] \cap [\; (c+b)^* a^* (c+b)^*\;]$$

• A mechanical way is to construct a DFA $D_1$ (resp. $D_2$) for the first (resp. second) expression, intersect them (by taking the Cartesian product of their states) and then convert the resulting DFA $D_1 \cap D_2$ back to a regular expression. – Steven Feb 1 at 16:26
• What is the meaning of the expression $(a+b)^* c^* (a+b)^*$? – Hendrik Jan Feb 1 at 21:32

## 1 Answer

Any word can be written as a concatenation of runs. For example, $$aaabbabaccbbbc = a^3b^2a^1b^1a^1c^2b^3c^1.$$ Each run is a positive power of a symbol, and the constraint is that two adjacent runs are powers of different symbols. Each word can be decomposed into runs in a unique way.

The regular expression $$(a+b)^*c^*(a+b)^*$$ captures all words with at most one $$c$$-run. Similarly, the regular expression $$(b+c)^*a^*(b+c)^*$$ captures all words with at most one $$a$$-run. Therefore the intersection consists of all words with at most one $$c$$-run and at most one $$a$$-run.

Since the only other possible run is a $$b$$-run, we get that the intersection is $$b^*a^*b^*c^*b^* + b^*c^*b^*a^*b^*.$$