2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Dec 13 '19 at 18:57
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How do you decide whether $G_1$ and $G_2$ are equivalent? $\endgroup$ – Yuval Filmus Dec 26 '19 at 13:05

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.