# Acceptance problem for CFGs is not regular

Let $$ACFG$$ be the language of all encodings $$(C,x)$$ where $$C$$ is a context free grammar that generates a language containing $$x$$, i.e. $$ACFG$$ is the acceptance problem for context free grammars.

It is easy to show that $$ACFG$$ is decidable. Parsing algorithms like CKY are proofs of this fact.

Is $$ACFG$$ also regular? Is it also context-free? I would guess nay to both, but how would one formally show these facts?

• To prove it is not regular, use the pumping lemma. To prove it is not context-free, see here. – dkaeae May 21 '19 at 12:48

Let $$\phi\colon \{0,1\}^* \to 2^{\{0,1\}^*}$$ be an arbitrary function mapping binary strings to languages over the binary alphabet. Suppose that the range of $$\phi$$ is infinite. Then the language $$L_\phi = \{(x,y) : y \in \phi(x)\}$$ is not regular.
(The language is over the alphabet consisting of $$0,1$$ as well as parentheses and comma.)
For the proof, we use Myhill—Nerode theory. Let $$(x_n)_{n \in \mathbb{N}}$$ be encodings of languages such that $$\phi(x_i) \neq \phi(x_j)$$ for $$i \neq j$$. Then the words $$(x_i,$$ and $$(x_j,$$ are inequivalent modulo $$L_\phi$$: taking any word $$y \in \phi(x_i) \Delta \phi(x_j)$$, the word $$y)$$ separates the words $$(x_i,$$ and $$(x_j,$$.
Interestingly, $$L_\phi$$ could be context-free. Let $$\phi(0^n) = \{1^n\}$$ and $$\phi(w) = \emptyset$$ if $$w$$ contains $$1$$. Then $$L_\phi = \{(0^n,1^n) : n \in \mathbb{N}\}$$, which is context-free.