Kleene Star over a formal Language containing Unions

255 Views Asked by At

I am a little bit confused, how the following language should be understood or further more, how the Kleenestar is interpreted in some ways:
$ ( \{0\} \cup \{1\}^*)^*$
I think the language looks like $\{0,1,11,111,1111....\}$.
So does the Outer-Kleene Star nothing? Or do I understand something wrong here?
Thanks in Advance

1

There are 1 best solutions below

0
On BEST ANSWER

$\{0\}\cup\{1\}^*=\{\epsilon,0,1,11,111,1111,\ldots\}$: it contains $0$, the empty string (since that is in $\{1\}^*$), and all non-empty finite strings of ones. When you take the star of this, you get all finite concatenations of these words. Many of those concatenations are just strings of ones, so they’re already present, as is the empty string. However, you also get all possible concatenations of $0$ and $1$, which means that you get the entire set $\{0,1\}^*$ of all possible finite sequences of zeroes and ones.

$$\begin{align*} \big\{\{0\}\cup\{1\}^*\big\}^*&=\{0,1\}^*\\ &=\{\epsilon,0,1,00,01,10,11,000,001,\ldots\} \end{align*}$$