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

How is $\emptyset^* = \{\epsilon\}$?

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

Problem

I know that $\emptyset$ is a an empty language, i.e. language containing no string.

A law involving empty language is:


$\emptyset L = L\emptyset = \emptyset$

It correctly states that we cannot concatenate non empty language $L$ with a language $\emptyset$ containing no string (as their is no string to concatenate in $\emptyset$), it yields empty language.

Then how concatenating a language containing no string with itself any number of times can yield even empty string? That is, how following law exist:


$\emptyset^* = \{\epsilon\}$

Solution

For any language $L$, by definition
$$ L^* = \bigcup_{i=0}^\infty L^i, $$
where a word in $L^i$ is the concatenation of $i$ words from $L$. In particular, $L^0 = \{ \epsilon \}$ since $\epsilon$ is the concatenation of zero words from $L$. It doesn't matter if $L$ is empty or not, since we are choosing zero words from $L$.

Context

StackExchange Computer Science Q#51096, answer score: 10

Revisions (0)

No revisions yet.