# 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?

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.