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)^*\;]$$
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ 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. $\endgroup$ – Steven Feb 1 at 16:26
-
3$\begingroup$ What is the meaning of the expression $(a+b)^* c^* (a+b)^*$? $\endgroup$ – Hendrik Jan Feb 1 at 21:32
Add a comment
|
$\begingroup$
$\endgroup$
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^*. $$
answered Feb 2 at 9:13
