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

Kleene star operation on the empty language

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

Problem

In my text book it is mentioned that: $\emptyset^*=\{\epsilon\}$ where $\emptyset$ is an empty language.

However, we know that $L \cdot \emptyset = \emptyset$, where $L$ is any Language.

I am not able to intuitively grasp this concept because the Kleene star operation points towards the fact that $\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots$ .

So why is $\emptyset^*$ not equal to $\emptyset$?

Solution

If you consider now the powers of a language $W$ you have
$W^xW^y=W^{x+y}$ If you want this to be consistent over $\mathbb N_0$,
i.e. the non-negative integers, you have to define
$W^0=\{\epsilon\}$. If you took it to be $\emptyset$ you would have
$W^x=W^{x+0}=W^xW^0=W^x\emptyset=\emptyset$ including, among others,
for $x=1$. Thus we would have $W^1=W=\emptyset$ for any $W$.
Thus this would clearly be inconsistent. A similar inconsistency arises for any other choice than $\{\epsilon\}$, which is the identity for language concatenation.

Hence, the only consistent consistent definition of $W^0$ for a non empty set $W$ is
$W^0=\{\epsilon\}$.

It is then convenient to extend the definition to the case when
$W=\emptyset$ as $\emptyset^0=\{\epsilon\}$.

This is just a consistent and convenient definition, often adopted in semi-rings but
it cannot be proved, unlike thw case when $W\neq\emptyset$ where there is no other consistent definition.

However, other definitions have then to be given in a consistent way, which
implies that

$$\begin{align}
\emptyset^*&=\emptyset^0\cup\emptyset^1\cup\emptyset^2\cup\ldots \\
&=\{\epsilon\}\cup\emptyset\cup\emptyset\cup\ldots\\
&=\{\epsilon\}
\end{align}$$

The topic is discussed on many web pages. In the case of the semi-ring
of numbers (the lack of precision is intentional) this is discussed at
length on this page: Zero to the zero power - Is $0^0=1$?.

The semi-ring of languages is described in this answer.

Context

StackExchange Computer Science Q#44907, answer score: 16

Revisions (0)

No revisions yet.