Could the following statement be correct?
"Every infinite recursive language has as a subset an infinite regular language."
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ I don't think there is an infinite regular subset of the set of strings of prime length. $\endgroup$– Thomas AndrewsMay 10, 2016 at 20:32
-
$\begingroup$ Let $(A_i : i \in \omega)$ be a uniformly computable sequence infinite sets that is, so that the predicate $P(n,i) \equiv n \in A_i$ is computable. Then it is easy to construct an infinite recursive set $X$ that does not have any of the sets $A_i$ as a subset. In fact, we can ensure that $X \Delta A_i$ is infinite for each set $A_i$ in the sequence. $\endgroup$– Carl MummertMay 10, 2016 at 20:57
-
$\begingroup$ @Thomas: yes, this follows from the pumping lemma. $\endgroup$– Qiaochu YuanMay 10, 2016 at 21:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
No. Call a language lacunary if it is infinite and the gaps between the distinct lengths of words goes to infinity; for example, the language of words whose length is square.
By the pumping lemma, no lacunary language is regular (or context-free), and every infinite subset of a lacunary language is lacunary.
answered May 10, 2016 at 21:00
-
$\begingroup$ Someone care to explain the downvote? $\endgroup$ May 10, 2016 at 21:02