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


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.


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.