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

<p>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.</p>

CC BY-SA 3.0
2017-10-12T01:24:32.230Z
so beautiful idea, why I have not thought about it?
XL _At_Here_There
CC BY-SA 3.0
2017-10-12T01:29:40.260Z
I might try to track down the exact reference to the literature but if not, yes the idea is anyway clear.
Bjørn Kjos-Hanssen
CC BY-SA 3.0
2017-10-12T01:11:16.817Z
2017-10-12T01:11:16.817Z
Bjørn Kjos-Hanssen
<p>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$$</p>

<p>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?</p>

<p>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?</p>

<cc.complexity-theory><computability><automata-theory><combinatorics>
Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?
XL _At_Here_There
# Can any c.e. language with infinite words be decomposed into infinite CFLs with infinite words?

(Asked by: username_0 on 2017-10-12)

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?

**Tags:** cc.complexity-theory, computability, automata-theory, combinatorics

---

## 1 answers

### Answer by username_1 on 2017-10-12. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: so beautiful idea, why I have not thought about it?  
> **username_1**: I might try to track down the exact reference to the literature but if not, yes the idea is anyway clear.  

---

