2
$\begingroup$

As union is part of regular expression in form of positive closure, similarly intersection is also a part of regular expression? in which form it can be used?

$\endgroup$
5
$\begingroup$

Regular expressions over an alphabet $\Sigma$, and their denotations (denoted by $L[r]$), are defined as follows:

  1. $\emptyset$ is a regular expression, and $L[\emptyset] = \emptyset$ (empty language).
  2. $\epsilon$ is a regular expression, and $L[\epsilon] = \{\epsilon\}$ (the empty word).
  3. For each $\sigma \in \Sigma$, $\sigma$ is a regular expression, and $L[\sigma] = \{\sigma\}$ (single letter).
  4. If $r_1,r_2$ are regular expressions over $\Sigma$ then so is $r_1r_2$, and $L[r_1r_2] = L[r_1]L[r_2]$ (concatenation).
  5. If $r_1,r_2$ are regular expressions over $\Sigma$ then so is $r_1+r_2$, and $L[r_1+r_2] = L[r_1] \cup L[r_2]$ (union).
  6. If $r$ is a regular expression over $\Sigma$ then so is $r^*$, and $L[r^*] = L[r]^*$ (iteration).

The definition of concatenation of languages is $$ L_1L_2 = \{w_1w_2 : w_1 \in L_1, w_2 \in L_2\}. $$ The definition of iteration is $$ L^* = \bigcup_{n=0}^\infty L^n, \text{ where } L^0 = \{\epsilon\} \text{ and } L^{n+1} = L^nL. $$

As you can see, union is built into regular expressions, whereas intersection isn't. However, the set of regular languages (which is the set of languages of the form $L[r]$) is closed under intersection, and so given any two regular expressions $r_1,r_2$, we can find a regular expression $r$ such that $L[r] = L[r_1] \cap L[r_2]$.

It turns out that sometimes $r$ will be much larger than $r_1,r_2$, see for example Gelade and Neven, Succinctness of the Complement and Intersection of Regular Expressions, Theorem 17(2). A similar phenomenon is exhibited by complementation, see for example Theorem 12(2) in the aforementioned paper. For this reason, sometimes extended or generalized regular expressions are considered, in which operations such as intersection and complementation are allowed. While this does not increase the expressivity of regular expressions – every language expressible using an extended regular expression can also be expressed as a standard regular expression – it does increase their economy (i.e., length or size).

$\endgroup$
4
$\begingroup$

Intersection is not a part of standard regular expressions. However, if $R_1$ and $R_2$ are regular expressions, then there is always some regular expression $R_3$ such that $L(R_3)=L(R_1)\cap L(R_2)$.

This means that adding intersection to regular languages (i.e., making $R_1\cap R_2$ an actual regular expression) wouldn't change what you can do with regular expressions. It would make writing regular expressions easier but make proving things about them harder, because there would be more cases to prove.

$\endgroup$

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.