3
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

6
$\begingroup$

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

$\endgroup$
2

You must log in to answer this question.

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