Grammar with fewest variables

Question

I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints.

1. The Myhill-Nerode Theorem provides the minimum number of states of a DFA to recognize a regular language. Argue that an analogue for context-free languages is unlikely to be discovered.

2. Prove that the grammar with fewest variables equivalent to a grammar G is uncomputable.

Answer 1

Let $L \neq \emptyset$ be a language over some alphabet $\Sigma$, let $|$ be a symbol not in $\Sigma$, and consider the language $|L = \{ |w : w \in L \}$. Suppose that $L$ could be generated using a context-free grammar with a single nonterminal $S$.

Since $L \neq \emptyset$, $S \Rightarrow^* |w$ for some word $w$. Therefore:

• Every rule contains at most one $S$ on the right-hand side. Indeed, otherwise you could generate a word with more than one $|$.
• Every rule containing exactly one $S$ must be of the form $S \to Sw$, where $w \in \Sigma^*$. Indeed, the rule cannot contain $|$, since otherwise $S$ would generate a word with more than one $|$; and the rule cannot contain anything to the left of $S$ since then $S$ would generate a word not beginning in $|$.
• Every rule not containing any $S$ must be of the form $S \to |w$, where $w \in \Sigma^*$ (in fact, $w \in L$).

Let $A$ be the collection of words $w \in \Sigma^*$ for which there is a rule $S \to |w$, and let $B$ be the collection of words $w \in \Sigma^*$ for which there is a rule $S \to Sw$. Thus $$ L = |AB^*. $$ Conversely, it is easy to check that every language of this form (with $A,B$ finite) has a context-free grammar with a single nonterminal. Considering also the empty language, we have shown:

The language $|L$ can be generated using a context-free grammar with a single nonterminal iff $L = AB^*$ for some finite (possibly empty) $A,B$.

The collection of languages of the form $AB^*$ is closed under quotient from the left, which is the following operation: $\sigma^{-1}S = \{ w : \sigma w \in S \}$. Indeed, if $\epsilon \notin A$ then $\sigma^{-1}(AB^*) = (\sigma^{-1}A)B^*$, and if $\epsilon \in A$ then $\sigma^{-1}(AB^*) = (\sigma^{-1}A)B^* \cup (\sigma^{-1}B)B^*$. Therefore, Greibach's theorem shows that determining whether a context-free grammar generates a language of the form $AB^*$ is undecidable.

Given a context-free grammar $G$, we easily construct a context-free grammar for $|L(G)$. The language of this context-free grammar can be generated by a single nonterminal iff $L(G)$ is of the form $AB^*$, and so the following problem is undecidable: Given a context-free grammar, determine whether its language can be generated by a context-free grammar with a single nonterminal.

Answer 2

Suppose we can find $G’$ - a grammar with the fewest variables and equivalent to $G$ - with the help of a Turing machine $T$. Thus there exists $T$ taking input $G$ and giving output $G’$. Suppose that $G’$ is unique up to relabeling of variables.

Then we can use this $T$ to decide ${EQ_{CFG}}^1$ ; i.e. by applying $T$ on $G_1$ and on $G_2$ and deciding if the descriptions are equivalent (using exhaustive search is possible since we have a finite number of rules and variables). This is a contradiction because $EQ_{CFG}$ is undecidable.

$ ^1 $- whether two CFGs are equivalent or not