I know that,

0* generates, NULL, 0, 00, 000, 0000, ... and so on.

But how does (0*)* actually work? Does it generate even length 0's?

Like this, NULL, 00, 0000, 000000...

or it generates strings same as first expression? What I thought is that if it has 2 star means, that it will multiply any string inside, regardless of odd or even length and the output will be even eventually? Am I going correct?


They generate the same set of strings. In fact, for any set of strings $A$:

$${A^*}^* = A^*$$

I am going to use lower-case lambda $\lambda$ to denote the zero-length string; some textbooks use epsilon: $\epsilon$ or $\varepsilon$. This is what you called NULL, but it is more common to reserve that word for the null set or empty set, usually denoted $\emptyset$.

Intuitively, $A^*$ means $\lambda \cup A \cup AA \cup AAA \cup \cdots$.


$${A^*}^* = \lambda \cup A^* \cup A^*A^* \cup A^*A^*A^* \cup \cdots$$

We could expand this, but don't have to. What I want you to notice is that there is a set of strings $B$ such that:

$${A^*}^* = A^* \cup B$$

Or, to put it another way, $A^*$ is a subset of ${A^*}^*$. Every string in $A^*$ must also be in ${A^*}^*$.

To show that ${A^*}^* = A^*$ would also require showing that ${A^*}^*$ is a subset of $A^*$, and I'll leave that as an exercise if you're interested. But this is enough to show that every string in $\mathbf{0}^*$ is also in ${\mathbf{0}^*}^*$, including those with odd length.

The Kleene star operator is sometimes easier reason about if you use subsets rather than equalities. See Kleene algebra for more on this.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.