For this problem you may assume that the sets L and J are bo

For this problem you may assume that the sets L and J are both subsets of N.

i. Show that any infinite decidable language L has an infinite decidable subset.

ii. Show that any infinite decidable language L has an infinite decidable subset J with the property that L J is also infinite.

iii. Does the statement in part i of this problem still true if L is only recognizable. (That is, is it true that any infinite recognizable language L has an infinite decidable subset ?) If it is true, say why. If not true, find a counter example.

Solution

i) Let M be an infinite Turingrecognizable language. Then, there exists an enumerator
P that enumerates all strings in A. We
construct another enumerator P’ that prints a subset of M in lexicographic order:
“Ignore the input.
1. Simulate P. When P prints its first string w1, print w1 and let prev_w = w1.
2. Continue simulating P.
3. When P is ready to print a new string w, check to see if w is longer than
prev_w (this ensures w occurs after prev_w in lex. order). If so, then print w
and let prev_w = w, otherwise do not print w.
4. Go to 2.”
It is clear that P’ as constructed above only prints strings in M, therefore its
language is a subset of M. Since M is infinite, there will always be strings in M longer
than the current prev_w – P will eventually print one of these and so will P’ (and
update prev_w). Therefore, the language of P’ is also infinite. Finally, since P’ only
prints strings in lexicographic order, its language is decidable.
Thus, the language of P’ is an infinite decidable subset of M.

iii) Yes, it is true for onlyrecogizable language. Yes, any infinite recognizable language L has an infinite decidable subset. Every infinite decidable language is infinite union of Infinite decidable subsets