# Is $\{\langle G,x\rangle \mid x\in L(G)\}$ context-free?

Our problem is:

Given a context-free grammar $$G$$ and a string $$x$$, decide whether $$x\in L(G)$$.

Is this language itself context-free?

• Isn't it trivially context-free? $"<G,"$ and $">"$ can be considered constant. Since the remaining part $x$ is context-free, the language in the title is context-free.On the other hand, if $G$ is meant to be any context-free grammar, then there is no upper bound of the number of terminal symbols in $G$. So the language in the title has infinitely many terminal symbols, which is certainly not a context-free language. – John L. Oct 17 '18 at 5:07
• Do you mean that $G$ is a context-free grammar over a fixed alphabet? – John L. Oct 17 '18 at 5:56

## 1 Answer

If your language were context-free, then by intersecting it with a regular language, we would deduce that the following language would be context-free: $$\{ \langle G,x \rangle \mid \text{x \in L(G) and G contains a single production S \to w} \}$$ However, this is just the celebrated language $$\{ ww : w \in \Sigma^* \}$$ in disguise, which is known not to be context-free. It follows that your language (using any reasonable encoding) is also not context-free.

• It is true that you believe that the $G$ in the question is meant for the context-free grammar over a fixed alphabet? – John L. Oct 17 '18 at 5:54
• Not necessarily. You can encode general context-free grammars over an arbitrary alphabet as binary strings, for example. – Yuval Filmus Oct 17 '18 at 6:11
• Excellent answer! – Thinh D. Nguyen Oct 17 '18 at 12:17
• While the answer might be excellent, the question is ambiguous. If $G$ is not required to be over a fixed alphabet, then the question (implicitly) requires we encode isomorphic $G$ the same way. However, if I (or you) think about it, can it really be done? Even if it can be done and it is done, then $\{ \langle G,x \rangle \mid x \in L(G\}$ cannot be the right description of it, since you have to say something like $\{ \langle G,x \rangle \mid s \in L(G), G \text{ is an equivalent class of context-free grammars} \}$ and probably a lot more explanations. – John L. Oct 17 '18 at 19:26
• It is a good question in the sense that it is sort of a trailblazer. However, it might be far from a proper question. – John L. Oct 17 '18 at 19:28