The Gateway to Computer Science Excellence
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^{*}.$
in Theory of Computation by Veteran (60.5k points)
edited by | 11 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,832 questions
57,686 answers
107,200 users