Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Is there a way to directly form a new regular expression when given two regular expressions and the desired operation (Union or Intersection).
$$ (a+b)^*aa(a+b)^*\cup (a+b)^*aa(a+b)^* $$
$$ (a+b)^*aa(a+b)^*\cap (a+b)^*aa(a+b)^* $$
Without building NFAs and doing the operation through them?
Thank you.
You may be interested in this article: http://fox7.eu/wp-content/uploads/a4-gelade.pdf
It is shown there that: "when constructing a regular expression defining the intersection of a fixed and an arbitrary number of regular expressions, an exponential and double exponential size increase, respectively, cannot be avoided".
