For example, if I have a non-context free language of B, is there such a context free language A such that A is a subset of B? I have been thinking of examples but am unable to think of any valid ones. I thought I got it when I said that A = {A = {w | w is of even length and w ∈ {a, b, c}}, which is context-free, and B = {ww | w ∈ {a,b,c}}, which is not context free. However, I realized that there are some strings A can produce that B cannot, and therefore, A is not a subset of B. Does anyone know of any examples that could be valid in my situation? Thank you!
$\endgroup$1 Answer
$\begingroup$It certainly is possible. One perhaps trivial example: any finite subset of a language is regular, hence context-free.
A less trivial example: let $\Sigma$ be a one-symbol alphabet, so we can identify $\Sigma^*$ with $\Bbb N$; let $O \subset \Bbb N$ be an undecidable set of odd numbers, and let $A \subset \Bbb N$ be a context-free set of even numbers. Then $B = U\cup A$ is not context-free (it's not decidable), but $A\subset B$ is context free.
$\endgroup$
