We have the $L\in R$, how can we prove that $L^*\in R$ only by enumerators?

I try to use induction, but as I understand I wrong...
I'd like to get any help!

  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Mar 27 '16 at 21:59
  • $\begingroup$ Also, the question sounds very familiar – I believe it has been asked before. $\endgroup$ – Yuval Filmus Mar 27 '16 at 22:02

I don't really see how to use induction here.

Let's take as an example $L = \{0,1\}$. Then $L^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\}$. You probably know how to enumerate $L^*$. Same thing works if $L = \{w_0,w_1\}$ for two arbitrary words.

The next step is to handle a language with infinitely many words. Following the earlier convention, I'll just indicate how to solve it for the special in which $L = \mathbb{N}$, and instead of $L^*$ I will use comma-separated sequences. Here is my enumeration: $$ \epsilon; 1; 2; 1,1; 3; 1,2; 2,1; 1,1,1; 4; \ldots $$ and so on. See if you can figure out a pattern (or if you don't like my pattern, come up with a different one).

| cite | improve this answer | |
  • $\begingroup$ It's great answer Yuval! Thank you!! But can you explain more about the enumeration (the order of the words)? I think I understand it (the idea), but I'd like to understand more of the order of your enumeration... Thank you!! $\endgroup$ – Yoar Mar 27 '16 at 22:37
  • 1
    $\begingroup$ That's your task. There's more than one possible answer. $\endgroup$ – Yuval Filmus Mar 27 '16 at 22:37

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.