HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why do we need Kleene Star when there is concatenation?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whystarconcatenationneedwhentherekleene

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#135078, answer score: 6

Revisions (0)

No revisions yet.