edited by
147 views
0 votes
0 votes
Suppose that $L$ is any language not necessarily regular whose alphabet is $\{0\};$i.e. the strings of $L$ consist of $0's$ only. Prove that $L^{*}$ is regular. Hint$:$ At first this theorem sounds preposterous. However, an example will help you see why it is true. Consider the language  $\text{L=\{0^{i}| i   is prime \},}$ which we know is not regular.Strings $00$ and $000$ are  in $L,$ since $2$ and $3$ are both primes. Thus if $j\geq 2,$ we can show $0^{j}$ is in $L^{*}.$If $j$  is even ,use $j/2$ copies of $00,$ and if $j$ is odd ,use copy of $000$ and $(j-3)/2$ copies of $00.$ Thus ,$L^{*}=$ $\in + 000^{*}.$
edited by

Please log in or register to answer this question.

Related questions