3
$\begingroup$

Suppose $L$ is a computably enumerable language, can it be decompose into infinite CFLs with infinite words ? $$L=\bigcup_{L_i\in CFL }^{\infty}L_i$$

Second question: if it is possible that every $L$ , computably enumerable language with infinity words be decompose into finite/infinite CFLs with infinite words, can it be be decompose into finite/infinite unabiguous CFLs with infinite words?

UpDate: Third question, is it possible that every $L$ , computably enumerable language with infinity words be formed by union,complement,intersection,product (finite/infinite) of unabiguous CFLs with infinite words?

$\endgroup$
3
$\begingroup$

No, we get counterexamples by considering resource-bounded randomness. In fact the gap between c.e. and $\mathsf{CFL}$ is wide.

Let $R$ be exponential-time random. Then $R$ is $\mathsf{NP}$-immune, i.e., it has no infinite subset in $\mathsf{NP}$. In particular it has no infinite subset that is a context-free language.

$\endgroup$
  • 2
    $\begingroup$ so beautiful idea, why I have not thought about it? $\endgroup$ – XL _at_China Oct 12 '17 at 1:24
  • 1
    $\begingroup$ I might try to track down the exact reference to the literature but if not, yes the idea is anyway clear. $\endgroup$ – Bjørn Kjos-Hanssen Oct 12 '17 at 1:29

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.