# 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)?

## 1 Answer

Gelade and Neven prove the following theorem in their paper Succinctness of the Complement and Intersection of Regular Expressions:

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)$.

This suggests that there is no analog of the product construction for regular expressions.