Show that minimal CFG is undecidable via mapping reduction

Question

Actually the problem below is an exercise in Sipser's textbook (Problem 5.36). However, from my perspective, it is not so trivial so that I post this question on this site instead of CS.SE.

The question itself was asked on Math.SE:

Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\textsf{CFG}}$ = $\{\, \langle G \rangle \ | \ G$ is a minimal CFG$\}$.
a) Show that $MIN_{\textsf{CFG}}$ is Turing-recognizable.
b) Show that $MIN_{\textsf{CFG}}$ is undecidable.

The OP figured out a), the relatively simple part, by himself. And I answered b) few days ago, by reducing to $ALL_{\textsf{minCFG}}$:

---

It suffices to focus on the case $\Sigma = \{0,1\}$. We argue that $ALL_{\textsf{minCFG}} \leq_T MIN_{\textsf{CFG}}$. That is, we can determine whether a minimal CFG can generate all possible strings, by using the oracle for $MIN_{\textsf{CFG}}$.

Let $G$ denote the minimal CFG we are interested. Since $G$ is minimal, there exists a length $p$ such that, for each rule $R$ in $G$ there exists a string $w_R$ with $|w_R|<p$ that can be generated by $G$, but not with $R$ deleted. Note here that $p$ is computable in a brute force manner. Construct $G^+_{a_1a_2\cdots a_p}$ where $a_i \in \Sigma$, by adding following rules in $G$: $$ S \to a_1 a_2 \cdots a_pT \\ T \to T0 \ | \ T1 \ | \ \epsilon $$ First, consider what will happen if $G^+_{a_1a_2\cdots a_p}$ is not minimal, thus, there exists a rule $R$ in $G^+$ being dispensable. By our construction it is clear that each rule $R$ in $G$ is indispensable.

• If $S \to a_1 a_2 \cdots a_pT$ or $T \to \epsilon$ is dispensable, then we have $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$.
• If $T \to T0$ is dispensable, then we have $(a_1 a_2 \cdots a_p \Sigma^* - a_1 a_2 \cdots a_p 1^*) \subseteq L(G)$. Because whether $a_1 a_2 \cdots a_p1^* \subseteq L(G)$ is easy to determine by some classical algorithm, we can also determine whether $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$.
• It is similar for $T \to T1$.

Therefore, if $G^+_{a_1a_2\cdots a_p}$ is not minimal, we can determine whether $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$. What if it is minimal? In this case we will immediately know $L(G) \neq \Sigma^*$. So we can suppose that all possible $G^+_{a_1a_2\cdots a_p}$ is not minimal. Then by checking whether $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$ one by one and checking those strings of less-than-$p$ length, we can still decide whether $L(G) = \Sigma^*$.

Update. (Oct 12, 2020) After a short discussion with @xdavidliu I realized that the argument above can directly prove what we want, without a justification of uncomputability of $ALL_{\textsf{minCFG}}$. Recall that the reduction we have established achieves the following: Given a minimal CFG $G$, determine whether $L(G) = \Sigma^*$. Now if we want to decide whether $L(G_0) = \Sigma^*$ for an arbitrary CFG $G_0$, just simply feed into the (reduction) algorithm all minimal sub-CFG (test each sub-CFG by the $MIN_{\mathsf{CFG}}$ oracle to determine whether it is minimal) of $G_0$ and see if there is one that generates all strings.

---

However, there are still two questions:

• Can we find a simple proof for undecidability of $ALL_{\textsf{minCFG}}$?

• Since this problem appears in Chapter 5, in which Turing reduction has not introduced. I personally believe that there is an elegant proof using only mapping reduction. Can we do it?

---

Update. (Nov 5th, 2017) We found that, roughly speaking, we could prove $A_{\textsf{TM}} \leq_T ALL_{\textsf{minCFG}}$ by the same way as one for $A_{\textsf{TM}} \leq_T ALL_{\textsf{CFG}}$, just adding some stuff to show that the grammar we used in proving $A_{\textsf{TM}} \leq_T ALL_{\textsf{CFG}}$ is already minimal. However, I could not assert that this way is quite simple.

Comment. @Sylvain gives an elegant proof below, by showing $$ PCP \leq_T FullPCP \leq_m MIN_{\textsf{CFG}}$$ in which I personally thought the key is that context-free language is closed under $h^{-1}$ he defined.

Answer 1

Here is a solution based on a reduction from Post Correspondence Problem. The general idea is similar to the ones used in reductions from PCP to the emptiness of intersection and ambiguity in context-free grammars. I am afraid I am using a Turing reduction for a preliminary claim---which I would consider fair game considering the number of variants of PCP `out there'.

Preliminaries. A PCP instance is a finite set of pairs $\Pi=(u_i,v_i)_{i<n}$ of finite words over a finite alphabet $\Sigma$. A solution is a sequence of indices $j_0,\dots,j_m$ with $u_{j_0}\cdots u_{j_m}=v_{j_0}\cdots v_{j_m}$. The set of indices $I(\Pi)$ of a PCP instance $\Pi$ is the set of indices $i<n$ that appear in some solution; formally $$I(\Pi)=\{ i < n\mid \exists i_0,\dots,i_m <n\mathbin.u_{j_0}\cdots u_{j_m}=v_{j_0}\cdots v_{j_m}\text{ and }\exists 0\leq k\leq m\mathbin.i=j_k\}\;.$$ Then the PCP instance has a solution iff $I(\Pi)\neq\emptyset$.

Claim. The following decision problem called full PCP is also undecidable:

• instance $\Pi$
• question $I(\Pi)=\{0,\dots,n-1\}$?

Proof. By a Turing reduction from PCP. Assume full PCP is decidable, and consider a PCP instance $\Pi$. For a subset $J\subseteq\{0,\dots,n-1\}$, let $\Pi_J=(u_i,v_i)_{i\in J}$. Then $\Pi$ has a solution iff $I(\Pi)\neq\emptyset$ iff there exists $J\subseteq\{0,\dots,n-1\}$ such that $\Pi_J$ is a positive instance of the full PCP. Thus it suffices to check all the subsets $J$ with the algorithm for the full PCP; if at least one succeeds, the original PCP instance was positive, otherwise it was negative. $\Box$

The first grammar $G_1$ is constructed from a full PCP instance $\Pi$ in order to recognise $$\begin{aligned}L_1&=\{ \$u_{j_0}\cdots \$u_{j_m}\#(\$v_{j_0}\cdots \$v_{j_m})^R\mid j_0,\dots,j_m < n\}\;,\\L'_1&=L_1\cup\{\#\}\end{aligned}$$ where $\cdot^R$ denotes the reversal operation, and $\$,\#$ are fresh symbols not in $\Sigma$. Indeed, we can define $G_1=(\{S_1\},\Sigma\uplus\{\$,\#\},P_1,S_1)$ with $$P_1=\{S_1\to \$u_j S_1 v_j^R\$\mid j<n\}\cup\{S_1\to\#\}.$$ Then $L'_1=L(G_1)$. Without loss of generality, we can assume $(u_i,v_i)\neq(u_j,v_j)$ for all $i\neq j<n$, and the grammar $G_1$ is minimal: the $\$$ symbols are indeed here to ensure minimality (as otherwise there might exist two different sequences of indices yielding the same words).

The second grammar generates `centered non-palindromes' $$L_2=\{w\#{w'}^R\mid w\neq w'\in\Sigma^*\}.$$ Note that a word $w\#{w'}^R$ in $L_2$ is such that $w$ and $w'$ share a longest common prefix $u$: $w=uv$ and $w'=uv'$ for some $v,v'\in\Sigma^*$ with

1. either $v=ax$ and $v'=bx'$ for some $a\neq b\in\Sigma$ and $x,x'\in\Sigma^\ast$,
2. or $v=ax$ and $v'=\varepsilon$ for some $a\in\Sigma$ and $x\in\Sigma^\ast$,
3. or $v=\varepsilon$ and $v'=ax'$ for some $a\in\Sigma$ and $x'\in\Sigma^\ast$.

Thus $L_2$ is generated by $G_2=(\{S_2,E,A\},\Sigma\uplus\{\#\},P_2,S_2)$ with $$\begin{aligned}P_2&=\{S_2\to aS_2a\mid a\in\Sigma\}\cup\{S_2\to E\}\\&\cup\{E\to aA\#Ab\mid a\neq b\in\Sigma\}\cup\{aA\#\mid a\in\Sigma\}\cup\{\#Aa\mid a\in\Sigma\}\\&\cup\{A\to aA\mid a\in\Sigma\}\cup\{A\to\varepsilon\}\end{aligned}$$ The idea is that $S_2$ generates $u E u^R$ for $u$ the longest common prefix of $w$ and $w'$, after which $E$ applies one of the three cases above. Thus $L(G_2)=L_2$, and the grammar is minimal.

Relating the two grammars. Let $h$ be the homomorphism from $(\Sigma\uplus\{\$,\#\})^*$ to $(\Sigma\uplus\{\#\})^*$ defined by $h(a)=a$ for all $a\in\Sigma$, $h(\#)=\#$, and $h(\$)=\varepsilon$; $h$ simply erases $\$$ symbols. Then $\Pi$ has a solution iff $h(L_1)\not\subseteq L_2$. We define $L'_2=h^{-1}(L_2)$ and construct the corresponding grammar $G'_2=(N'_2,\Sigma\cup\{\$,\#\},P'_2,S'_2)$ in the obvious way (add a nonterminal $D$ with productions $D\to \$D$ and $D\to\varepsilon$ and introduce $D$ symbols everywhere in the right hand sides of the productions in $P_2$); it is still minimal and $\Pi$ has a solution iff $L_1\not\subseteq L'_2$.

We are however interested in the full PCP on $\Pi$. Construct $$G=(N_1\uplus N'_2\uplus\{S\},\Sigma\uplus\{\$,\#\},P_1\cup P'_2\cup\{S\to S_1,S\to S'_2\},S) .$$

• If $\Pi$ is a positive instance of the full PCP, then it has solutions, which describe words $\$u_{j_0}\cdots \$u_{j_m}\#(\$v_{j_0}\cdots \$v_{j_m})^R\not\in L'_2$ and moreover require every production of $G_1$. Regarding $G'_2$, it suffices to consider words from $L_2\subseteq L'_2$ with no occurrence of $\$$, which do not belong to $L_1$ and therefore all the productions of $G'_2$ are needed. Therefore, $G$ is minimal.
• Otherwise, there exists $i<n$ such that $i\not\in I(\Pi)$, and the production $S_1\to \$u_i S_1 v_i^R\$$ can be removed, since it cannot be part of a solution of $\Pi$, and therefore any generated word that uses this production is in $L(G'_2)$; thus $G$ is not minimal. In particular, if $\Pi$ has no solution ($I(\Pi)=\emptyset$), then all the productions in $P_1$ except $S_1\to\#$ can be removed. $\Box$