11
$\begingroup$

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?
$\endgroup$

migrated from cstheory.stackexchange.com May 27 '16 at 13:09

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 2
    $\begingroup$ Please restrict yourself to one question per post. $\endgroup$ – Raphael May 27 '16 at 14:08
16
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Indeed $\{a,b\}$ is not in the set of "subregular" languages, but $\{a,b\}^{\ast}$ is because $\{a,b\}^{\ast} = (a^{\ast}\circ b^{\ast})^{\ast}$. $\endgroup$ – rici May 27 '16 at 16:35
  • $\begingroup$ Yes, sometimes it is a little bit tricky to see what could be expressed and what not as with a clever combination of star and others you can get quite far. $\endgroup$ – StefanH May 27 '16 at 16:47
8
$\begingroup$

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$?

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.

$\endgroup$
  • $\begingroup$ Thanks for the link. I always explain to my students that the operations are natural abstractions from choice (like if-then-else) sequence (instructions following one another) and iteration (like while-do). But apparently that is not mentioned by Kleene? $\endgroup$ – Hendrik Jan Dec 17 '16 at 20:41
  • $\begingroup$ I'm just a guy who looked up Kleene's article and was surprised that everything in my answer was already in there. I don't know anything else. So I suppose the answer is to read the article and perhaps look for anything that Kleene wrote on this before. $\endgroup$ – reinierpost Dec 18 '16 at 17:44
4
$\begingroup$

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.

$\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.