Re: how to prove: let L be any subset of 0*. is L regular?

Thanks for the example.
Now it makes sense.


Rick Decker wrote:
yanlu06@xxxxxxxxx wrote:
let L be any subset of 0*. is L regular?
How to prove?

You can't. The regular subsets of 0* are
{0^k | k is in a semilinear set A}, where "semilinear" means
the finite union of sets of the form {a*i + b | i = 0, 1, 2, ...}.

An example of a non-regular set would be {0^{n^2} | n >= 0}. The
pumping lemma shows almost immediately that this isn't regular.



Regards,

Rick

.