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)^*\;]$$
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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^*. $$