The closure of two languages

814 Views Asked by At

From Introduction to Automata Theory, Languages, and Computation (2nd Edition):

"For a final example, the closure of the empty set = { epsilon } where epsilon is the empty string. Empty set is one of only two languages whose closure is not infinite." What is the other language?

1

There are 1 best solutions below

2
On

The Kleene closure is an idempotent operator: given a language $L$, it holds $(L^*)^*=L^*$. So another such language is...

For the converse, suppose $\sigma\in L$ and $\sigma\ne\epsilon$. Then $\{\sigma,\sigma\sigma,\sigma\sigma\sigma,\cdots\}\subseteq L^*$ and all those strings are distinct, because they have strictly increasing length.