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?

  • $\begingroup$ 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. $\endgroup$ – John L. Oct 17 '18 at 5:07
  • $\begingroup$ Do you mean that $G$ is a context-free grammar over a fixed alphabet? $\endgroup$ – John L. Oct 17 '18 at 5:56

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.

  • $\begingroup$ It is true that you believe that the $G$ in the question is meant for the context-free grammar over a fixed alphabet? $\endgroup$ – John L. Oct 17 '18 at 5:54
  • $\begingroup$ Not necessarily. You can encode general context-free grammars over an arbitrary alphabet as binary strings, for example. $\endgroup$ – Yuval Filmus Oct 17 '18 at 6:11
  • $\begingroup$ Excellent answer! $\endgroup$ – Thinh D. Nguyen Oct 17 '18 at 12:17
  • $\begingroup$ 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. $\endgroup$ – John L. Oct 17 '18 at 19:26
  • $\begingroup$ It is a good question in the sense that it is sort of a trailblazer. However, it might be far from a proper question. $\endgroup$ – John L. Oct 17 '18 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.