patternMinor
Cartesian product of regular expressions?
Viewed 0 times
expressionsregularcartesianproduct
Problem
My textbook has a problem to find the regular expression that describes the set of all strings of
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)?
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)?
Solution
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.
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.
Context
StackExchange Computer Science Q#88938, answer score: 4
Revisions (0)
No revisions yet.