3
$\begingroup$

For an alphabet $A = \{ a_1, a_2..., a_n \}$, the set of regular langages $L_r$ on $A$ are recursively defined by closed union, concatenation, and Kleene star's operator. I understood that languages ($A^*$) and regular languages (a subset of $A^*$) are different. Why do we need Kleene star, isn't concatenation enough for this definition?

Very simple "proof" that should be obviously wrong:

If $X \in L_r$ a regular language on $A$, and $E \in X^*$ (if i'm right also $X^* \in L_r$) a word then we could write $E$ as $e_1e_2\dots e_n = e_1 . e_2 \ldots e_{n-1} . e_n$, with each $e_i \in X$. Then $E$ is explicitly constructible by concatenation.

I forgot $\epsilon$ but so just add a simple rule that allow $\epsilon$. My intuition says that it has something to do with infinity, that Kleene Star allows infinite-lengh chains whereas concatenation doesn't. Is it that?

$\endgroup$
3
  • 2
    $\begingroup$ For the same reason we need while-loops in programming languages. If we can't iterate all programs will stop within a fixed number of steps. $\endgroup$ – Hendrik Jan Feb 3 at 17:50
  • 1
    $\begingroup$ @HendrikJan Something something recursion :) Which actually has an analogue in this context as well - CFGs allow recursion, regular expressions do not. $\endgroup$ – orlp Feb 3 at 19:13
  • $\begingroup$ @orlp Agreed. I was comparing regular expressions to "sequence, selection, iteration" programs. $\endgroup$ – Hendrik Jan Feb 4 at 13:27
6
$\begingroup$

Regular expressions without Kleene star define finite languages. You can prove this by induction on the structure of the regular expression. In contrast, $a^*$ is a regular expression which defines an infinite language.

We could try to define $a^*$ using concatenation and union: $$ a^* = \epsilon + a + a^2 + a^3 + \cdots $$ Unfortunately, the required regular expression is infinite, which we do not allow (infinite expressions do make sense in some contexts, for example in infinitary logic, but not here).

$\endgroup$
2
  • 1
    $\begingroup$ +1. And not only don't we allow infinite unions in the definition of regular expressions, we actually can't do so -- or at least, that definition wouldn't be equivalent to the standard one -- because that would also allow languages such as $a^n b^n = \epsilon + ab + aabb + aaabbb + aaaabbbb + \cdots$ that are known to be non-regular according to the standard definition. $\endgroup$ – ruakh Feb 4 at 4:53
  • 2
    $\begingroup$ In fact, infinite unions could represent all languages. $\endgroup$ – Yuval Filmus Feb 4 at 6:20

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.