# Regular expression vs rational expression

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?

• What's the difference between $\mid$ and $\cup$? – rici Mar 18 at 14:38
• Your definition of regular expressions is missing concatenation. But anyway, rici is right. – Emil Jeřábek Mar 18 at 14:51
• Hmm, ok thank you :) But if they are equal, why do we need two names for the same thing? – Algebruh Mar 18 at 14:54
• 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. – plop Mar 18 at 15:31
• 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. – plop Mar 18 at 16:20