Why are regular expressions defined with union, concatenation and star operations?

Question

A regular expresssion is defined recursively as

1. $a$ for some $a \in \Sigma$ is a regular expression,
2. $\varepsilon$ is a regular expression,
3. $\emptyset$ is a regular expression,
4. $(R_1 \cup R_2)$ where $R_1$ and $R_2$ are regular expressions is a regular expression,
5. $(R_1 \circ R_2)$ where $R_1$ and $R_2$ are regular expressions is a regular expression,
6. $(R_1)^*$ where $R_1$ is a regular expression is a regular expression.

This definition is taken from page 64 of

Sipser, Michael. Introduction to the Theory of Computation, 3rd edition. Cengage Learning, 2012.

Now, I have the following questions.

• Why do not the definition contain the intersection, complement or reverse operations?
• If we change the 4th item to $R_1 \cap R_2$, do we get an equivalent definition, i.e. for each regular language, there is a modified regular expression and vice versa?
• I know that this definition is complete and well-defined, but why is it preferred to other equivalent, well defined and complete definitions?

Answer 1

1) If we also allow intersection and complement, then the resulting expressions are sometimes called extended regular expressions; as the regular languages are closed under boolean operations nothing is gained by them. It is just syntactic sugar. A similar conclusion holds for the reverse operation. Part of the reason why on first instance all the other operations are not mentioned is the goal of keeping the definition as simple as possible, so that (inductive) proofs do not have to take care of to many cases. Another cause might be that if we allow certain operations, but others not, in some cases very distinct (subregular) language classes result, for example if we consider extended regular expression without the star operator, then we get a proper subclass of the regular ones, the so called star-free or aperiodic languages, see wikipedia:star-free language.

2) If we keep items 1. - 6. but just alter item 4. in using intersection instead of union, we get a proper subclass of the regular languages. For example we could no longer describe the language $L = \{a,b\}$ as it would involve the union of $\{a\}$ and $\{b\}$ (see proof below). If we allow complementation, things change as we have union back by DeMorgan's laws.

3) This was partly answered by me in 1), but what you mean when you say that this definition is preferred? I know definitions where 2. is omitted (as we have by 6. that $L(\emptyset^{\ast}) = \{\varepsilon\}$), or 3. is omitted (as we have $\emptyset = L(\overline{ X^{\ast} }$)), or both are omitted; so this one is not the minimal possible definition (it gives us also some syntactic sugar as we have extra symbols to describe $\{\varepsilon\}$ and $\emptyset$).

EDIT: My first mentioned comment in 2) was wrong, languages in the inductive closure under $\circ$, $^{\ast}$ and $\cap$ do not neccessarily are subsets of $x^{\ast}$ for some $x \in X$, for example consider $L(a\circ b) = \{ab\}$. Nevertheless we have that $L = \{a,b\}$ could not be describes by such an expression. I will give a proof, namely I proof that if $L = L(R)$ for some expression with the modified 4th item, then if $X = \{a,b\}$ (and hence $a\ne b$) $$ \{a,b\} \subseteq L \Rightarrow ab \in L. $$ The proof goes by induction on the expression $R$. For the base case it holds vacuously, now suppose it holds for $L(R_1), L(R_2)$. If $L = L(R_1 \cap R_2) = L(R_1) \cap L(R_2)$ and $\{a,b\} \subseteq L$, then $\{a,b\} \subseteq L(R_i), i = 1,2$ hence by induction hypothesis we have $ab \in L(R_1) \cap L(R_2)$. If $\{a,b\} \subseteq L(R_1\circ R_2) = L(R_1)L(R_2)$ then as $a = a\cdot \varepsilon = \varepsilon\cdot a$ we must have $a\in L(R_1)$ and $\varepsilon \in L(R_2)$ or vice versa. Suppose the first case. If $b \in L(R_1)$, then $ab \in L(R_1)$ by induction hypothesis, hence $ab = ab\cdot \varepsilon \in L(R_1)L(R_2)$. Now suppose $b \in L(R_2)$, then we have $a\cdot b \in L(R_2)L(R_2)$ by definition of $L(R_1)L(R_2)$. Lastly if $a,b \in L(R_1^{\ast})$, then $a \in L(R_1)^n$ and $b \in L(R_2)^m$ for some $n,m > 0$. If $n = m = 1$ we find $ab \in L(R_1)$ by induction hypothesis, so suppose $n > 1$, but this gives $a \in L(R_1)$, similar either $m = 1$ or $m > 1$ gives $b \in L(R_1)$ and the induction hypothesis gives $ab \in L(R_1) \subseteq L(R_1^{\ast})$. $\square$

Remark: One commonly used conclusion: If $a = uw$, then $u = a$ or $w = a$. This follows as $1 = |a| = |uw| = |u| + |w|$, hence $|u| = 0$ and $|w| = 1$ or $|u| = 1$ and $|w| = 0$. In the first case we have $u = \varepsilon$ and hence $a = w$.

Answer 2

The technical report that introduced regular languages, regular expressions, and finite automata asks your question on page 70:

The question may occur to the reader, why did we select the particular three operations $E\vee F$, $EF$, and $E*F$?

(Soon afterwards, it was noted that $E^*$ is a more convenient operator than $E*F$ and equivalent in power. So these days, we use $E^*$ instead.)

The answer occupies several pages. First, it is remarked that the answer must be sought in whether the resulting languages form an interesting class and how they compare with languages described by other means. On page 72, it is remarked that negation and conjunction are redundant: they do not add any expressive power. On page 80 and further, it is proved that the regular languages are exactly the languages recognized by finite state machines.

In other words: Stefan's answer can safely be considered conclusive, as it was already given in the report that first introduced these concepts.

Answer 3

From this selection of operators (union, concatenation, and star) one can construct an NFA with a size linear to the size of the expression. On the other hand, if you add intersection and complementation, the size of the equivalent automaton may explode non-elementarily, which is usually not desirable.