1
$\begingroup$

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)^*\;]$$

$\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
1
$\begingroup$

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^*. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.