Suppose $G$ is a finitely generated group, $A$ is a finite set of generators of $G$. Define $\pi: (A \cup A^{-1})^* \to G$ using the following recurrence:
$$\pi(\Lambda) = e$$ $$\pi(a \alpha) = a\pi(\alpha)$$
Now define the language $L(G, A) := \{w \in (A \cup A^{-1})^*| \pi(w) = e\}$.
Note that the position of $L(G, A)$ (as well as of $(A \cup A^{-1})^* \setminus L(G, A)$) in Chomsky hierarchy is uniquely determined by the properties of $G$.
It i a well known fact, proved by Adyan and Novikov, that there exist such groups $G$, that $L(G, A)$ is recursively enumerable, but $(A \cup A^{-1})^* \setminus L(G, A)$ isn't. Such groups can be even finitely generated (the smallest known having $12$ generators).
My question is:
Do there exist such groups $G$, such that $L(G, A)$ is context-free, but $(A \cup A^{-1})^* \setminus L(G, A)$ isn't?
All I currently know about that is that $L(G, A)$ is context-free iff $G$ is virtually free. Do not know how can it help, however...
No, if $L(G,A)$ is context-free then it is virtually free, in which case it is deterministic context-free (i.e. the language is accepted by a determinstic pushdown automaton). In that case, its complement $(A \setminus A^{-1})^* \setminus L(G,A)$ is also deterministic context-free (its language is accepted by (essentially) the same automaton with accept and fail states interchanged).
But the converse is not true. The class of so-called co-context free groups, for which $(A \setminus A^{-1})^* \setminus L(G,A)$ is context-free, is closed under taking direct products and so there are examples such as direct products of free groups, for which $L(G,A)$ is not context-free. There are other interesting examples, such as the Higman-Thompson groups. It is an open problem whether the class of co-context free groups is closed under taking free products, but this is generally thought not to be true.