# Cartesian product of regular expressions?

My textbook has a problem to find the regular expression that describes the set of all strings of 0's and 1's whose number of 0's is divisible by 5 and whose number of 1's is even.

I can write a regular expression for each condition

a. $0^*(10^*1)^*$

b. $1^*(01^*01^*01^*01^*01^*)^*$

I am having trouble understanding how to combine these two regular expressions. If they were DFAs, I could combine them by taking their cartesian product. Is is possible to take the cartesian product of two regular expressions (without translating each to a DFA first)?

• math.stackexchange.com/questions/1665392/… Commented Mar 5, 2018 at 22:17
• Converting to a DFA first is the most natural way to take their intersection (product).
– D.W.
Commented Mar 5, 2018 at 22:25
• The first regular expression is wrong. Commented Mar 6, 2018 at 0:13
• This is answered on Mathematics: math.stackexchange.com/a/913165/1277. Commented Mar 6, 2018 at 0:15

For every $n$ there exist two regular expressions $r_1,r_2$ of size $O(n^2)$ such that the smallest regular expression representing $L[r_1] \cap L[r_2]$ has size $\Omega(2^n)$.