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?

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

Let's prove a more general result:

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.


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.