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.


1 Answer 1


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".


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.