Does the Kleene Star allow for n-time concatenation or infinite concatenation of a word with itself?

297 Views Asked by At

When describing the Kleene Star, is the following correct:

The Kleene Star applied to a word w allows for the word to be concatenated with itself 0 to n times, with n [element] N.

where N is the set of the natural numbers. Is this fine as is, or would a better way of writing this be to say "[...] itself 0 to infinite times." (though this lacks a closer description of what infinity exactly we're describing)?

2

There are 2 best solutions below

0
On BEST ANSWER

No, it would not be a good idea to say "[...] with itself $0$ to infinite times." The reason is that there is already a well-defined notion of infinite word${}^{(1)}$. An infinite word on an alphabet $A$ is an infinite sequence $$ u = a_0a_1 \dotsm a_n \dotsm $$ of elements of A. We can therefore see an infinite word as a sequence indexed by the natural numbers. Now, if $w=a_1 \dotsm a_n$ be a nonempty word, the infinite word $w^\omega$ is the word $$ a_1 \dotsm a_na_1 \dotsm a_na_1 \dotsm a_n \dotsm a_1 \dotsm a_n \dotsm $$ The set of all infinite words over $A$${}^{(2)}$ is denoted $A^\omega$. The set of all finite and infinite words over $A$ is sometimes written $A^\infty$. Thus allowing the word $w$ to be "concatenated with itself $0$ to infinite times" would rather define the set $w^\infty = w^* \cup \{w^\omega\}$.

Note that one can also define words indexed by ordinals or even by linear orders, and these definitions cover your wish to have a precise description of the term infinity.

$\scriptsize (1)\ \text{This French Wikipedia entry is still waiting for an English translation, sorry...}$

$\scriptsize (2)\ \text{But this page is in English.}$

0
On

The Kleene star $\ast$ of a word $w$ is the set \begin{align*} w^{\ast}=\{\varepsilon, w,w^2,w^3,\ldots,w^n,\ldots\} \end{align*} containing zero of more occurrences of the word $w$ by concatenation. Each element of $w^{\ast}$ has finite length.

See also the corresponding Wiki-entry Kleene star.