2
$\begingroup$

Let $M$ be a monoid (e.g. $M = \Sigma^*$) and $L \subseteq M$.

Then $\mathsf{RAT}(M)$ is the set of rational sets of $M$ and the elements of $\mathsf{RAT}(M)$ are inductively defined as follows:

  • $|L| < \infty \implies L \in \mathsf{RAT}(M)$
  • $L_1, L_2 \in \mathsf{RAT}(M) \implies L_1 \cup L_2 \in \mathsf{RAT}(M)$
  • $L_1, L_2 \in \mathsf{RAT}(M) \implies L_1 \cdot L_2 \in \mathsf{RAT}(M)$
  • $L \in \mathsf{RAT}(M) \implies L^\ast = \bigcup_{i \geq 0} L^i \in \mathsf{RAT}(M)$ with $L^0=\{1_m\}$ and $L^{i+1} = L^iL$

And in my understanding, a rational expression is then an expression using only the operations in this definition, i.e. $$L_1 \cup L_2 \cup L_3L_4 \cup L_3^*$$.

On the other hand we have the definition of regular languages where $\mathsf{REG(M)}$ is the set of regular sets inductivly defined as follows:

  • $\emptyset$ is a regular expression
  • $\epsilon $ is a regular expression
  • $a \in \Sigma$ is a regular expression
  • if $\alpha$ and $\beta$ are regular expressions, then $\alpha\mid\beta$ is a regular expression
  • $\alpha^*$ and $\alpha\beta$ are regular expressions

Futhermore we know that regular languages are closed under complement unlike rational languages.

Question: It is often stated that regular expressions are the same as rational expressions. But hence this defintion of a rational expression doesn't allow for example "the decision"-operator, ($a \mid b$), it seems that regular expressions cover more than rational ones. What am I missing out? Are they really the same and if not, where are they distinct?

$\endgroup$
7
  • 2
    $\begingroup$ What's the difference between $\mid$ and $\cup$? $\endgroup$ – rici Mar 18 at 14:38
  • $\begingroup$ Your definition of regular expressions is missing concatenation. But anyway, rici is right. $\endgroup$ – Emil Jeřábek Mar 18 at 14:51
  • $\begingroup$ Hmm, ok thank you :) But if they are equal, why do we need two names for the same thing? $\endgroup$ – Algebruh Mar 18 at 14:54
  • 2
    $\begingroup$ The set of regular languages over an alphabet $\Sigma$ is the same as the set of rational sets of the free monoid $\Sigma^*$. However, the concept of rational sets is defined for any monoid, it doesn't need to be free, for example. $\endgroup$ – plop Mar 18 at 15:31
  • 1
    $\begingroup$ Well, those are just names and not content. I suppose you could find authors using the name regular sets for any monoid, or using the two words interchangeably. $\endgroup$ – plop Mar 18 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.