patternModerate
How is $\emptyset^* = \{\epsilon\}$?
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\}$
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$.
$$ 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.