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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .