If you want to make money online : Register now

How to prove that the decidable languages are closed against iteration only by enumerators?

, , No Comments
Problem Detail: 

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!

Asked By : Yoar
Answered By : Yuval Filmus

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).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55024

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback