<p>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'.</p>

<p><strong>Preliminaries. </strong>
A PCP instance is a finite set of pairs $\Pi=(u_i,v_i)_{i&lt;n}$ of finite words over a finite alphabet $\Sigma$.  A <em>solution</em> 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 <em>indices</em> $I(\Pi)$ of a PCP instance $\Pi$ is the set of indices $i&lt;n$ that appear in some solution; formally $$I(\Pi)=\{ i &lt; n\mid \exists i_0,\dots,i_m &lt;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$.</p>

<p><strong>Claim. </strong> The following decision problem called <em>full PCP</em> is also undecidable:</p>

<ul>
<li><em>instance</em> $\Pi$</li>
<li><em>question</em> $I(\Pi)=\{0,\dots,n-1\}$?</li>
</ul>

<p><em>Proof. </em> 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$</p>

<p><strong>The first grammar</strong> $G_1$ is constructed from a full PCP instance $\Pi$ in order to recognise
$$\begin{aligned}L_1&amp;=\{ \$u_{j_0}\cdots \$u_{j_m}\#(\$v_{j_0}\cdots \$v_{j_m})^R\mid j_0,\dots,j_m &lt; n\}\;,\\L'_1&amp;=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&lt;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&lt;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).</p>

<p><strong>The second grammar</strong> 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</p>

<ol>
<li>either $v=ax$ and $v'=bx'$ for some $a\neq b\in\Sigma$ and $x,x'\in\Sigma^\ast$,</li>
<li>or $v=ax$ and $v'=\varepsilon$ for some $a\in\Sigma$ and $x\in\Sigma^\ast$,</li>
<li>or $v=\varepsilon$ and $v'=ax'$ for some $a\in\Sigma$ and $x'\in\Sigma^\ast$.</li>
</ol>

<p>Thus $L_2$ is generated by $G_2=(\{S_2,E,A\},\Sigma\uplus\{\#\},P_2,S_2)$ with $$\begin{aligned}P_2&amp;=\{S_2\to aS_2a\mid a\in\Sigma\}\cup\{S_2\to E\}\\&amp;\cup\{E\to aA\#Ab\mid a\neq b\in\Sigma\}\cup\{aA\#\mid a\in\Sigma\}\cup\{\#Aa\mid a\in\Sigma\}\\&amp;\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.</p>

<p><strong>Relating the two grammars. </strong> 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$.</p>

<p>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) .$$</p>

<ul><li>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.</li>
<li>Otherwise, there exists $i&lt;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$</li></ul>

CC BY-SA 3.0
2017-11-05T18:28:44.157Z
2017-11-06T10:00:46.387Z
2017-11-06T10:00:46.387Z
Sylvain
<p>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.</p>
<p>The question itself was asked on <a href="https://math.stackexchange.com/q/1105117/134950">Math.SE</a>:</p>
<blockquote>
<p>Say that a CFG (context-free grammar) is <em>minimal</em> if none of its rules can be removed without changing the language generated. Let <span class="math-container">$MIN_{\textsf{CFG}}$</span> = <span class="math-container">$\{\, \langle G \rangle \ | \ G$</span> is a minimal CFG<span class="math-container">$\}$</span>.<br />
a) Show that <span class="math-container">$MIN_{\textsf{CFG}}$</span> is Turing-recognizable.<br />
b) Show that <span class="math-container">$MIN_{\textsf{CFG}}$</span> is undecidable.</p>
</blockquote>
<p>The OP figured out a), the relatively simple part, by himself. And I answered b) few days ago, by reducing to <span class="math-container">$ALL_{\textsf{minCFG}}$</span>:</p>
<hr />
<p>It suffices to focus on the case <span class="math-container">$\Sigma = \{0,1\}$</span>. We argue that <span class="math-container">$ALL_{\textsf{minCFG}} \leq_T MIN_{\textsf{CFG}}$</span>. That is, we can determine whether a <strong>minimal</strong> CFG can generate all possible strings, by using the oracle for <span class="math-container">$MIN_{\textsf{CFG}}$</span>.</p>
<p>Let <span class="math-container">$G$</span> denote the minimal CFG we are interested. Since <span class="math-container">$G$</span> is minimal, there exists a length <span class="math-container">$p$</span> such that, for each rule <span class="math-container">$R$</span> in <span class="math-container">$G$</span> there exists a string <span class="math-container">$w_R$</span> with <span class="math-container">$|w_R|&lt;p$</span> that can be generated by <span class="math-container">$G$</span>, but not with <span class="math-container">$R$</span> deleted.
Note here that <span class="math-container">$p$</span> is computable in a brute force manner.
Construct <span class="math-container">$G^+_{a_1a_2\cdots a_p}$</span> where <span class="math-container">$a_i \in \Sigma$</span>, by adding following rules in <span class="math-container">$G$</span>:
<span class="math-container">$$
S \to a_1 a_2 \cdots a_pT \\
T \to T0 \ | \ T1 \ | \ \epsilon
$$</span>
First, consider what will happen if <span class="math-container">$G^+_{a_1a_2\cdots a_p}$</span> is <em>not</em> minimal, thus, there exists a rule <span class="math-container">$R$</span> in <span class="math-container">$G^+$</span> being dispensable. By our construction it is clear that each rule <span class="math-container">$R$</span> in <span class="math-container">$G$</span> is indispensable.</p>
<ul>
<li>If <span class="math-container">$S \to a_1 a_2 \cdots a_pT$</span> or <span class="math-container">$T \to \epsilon$</span> is dispensable, then we have <span class="math-container">$a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$</span>.</li>
<li>If <span class="math-container">$T \to T0$</span> is dispensable, then we have <span class="math-container">$(a_1 a_2 \cdots a_p \Sigma^* - a_1 a_2 \cdots a_p 1^*) \subseteq L(G)$</span>. Because whether <span class="math-container">$a_1 a_2 \cdots a_p1^* \subseteq L(G)$</span> is easy to determine by some classical algorithm, we can also determine whether <span class="math-container">$a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$</span>.</li>
<li>It is similar for <span class="math-container">$T \to T1$</span>.</li>
</ul>
<p>Therefore, if <span class="math-container">$G^+_{a_1a_2\cdots a_p}$</span> is not minimal, we can determine whether <span class="math-container">$a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$</span>. What if it is minimal? In this case we will immediately know <span class="math-container">$L(G) \neq \Sigma^*$</span>. So we can suppose that all possible <span class="math-container">$G^+_{a_1a_2\cdots a_p}$</span> is not minimal. Then by checking whether <span class="math-container">$a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$</span> one by one and checking those strings of less-than-<span class="math-container">$p$</span> length, we can still decide whether <span class="math-container">$L(G) = \Sigma^*$</span>.</p>
<p><strong>Update.</strong> (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 <span class="math-container">$ALL_{\textsf{minCFG}}$</span>. Recall that the reduction we have established achieves the following: Given a minimal CFG <span class="math-container">$G$</span>, determine whether <span class="math-container">$L(G) = \Sigma^*$</span>. Now if we want to decide whether <span class="math-container">$L(G_0) = \Sigma^*$</span> for an arbitrary CFG <span class="math-container">$G_0$</span>, just simply feed into the (reduction) algorithm all minimal sub-CFG (test each sub-CFG by the <span class="math-container">$MIN_{\mathsf{CFG}}$</span> oracle to determine whether it is minimal) of <span class="math-container">$G_0$</span> and see if there is one that generates all strings.</p>
<hr />
<p>However, there are still two questions:</p>
<ul>
<li><p><strike>Can we find a simple proof for undecidability of <span class="math-container">$ALL_{\textsf{minCFG}}$</span>?</strike></p>
</li>
<li><p>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?</p>
</li>
</ul>
<hr />
<p><strong>Update.</strong> (Nov 5th, 2017) We found that, roughly speaking, we could prove <span class="math-container">$A_{\textsf{TM}} \leq_T ALL_{\textsf{minCFG}}$</span> by the same way as one for <span class="math-container">$A_{\textsf{TM}} \leq_T ALL_{\textsf{CFG}}$</span>, just adding some stuff to show that the grammar we used in proving <span class="math-container">$A_{\textsf{TM}} \leq_T ALL_{\textsf{CFG}}$</span> is already minimal. However, I could not assert that this way is quite simple.</p>
<p><strong>Comment.</strong> @Sylvain gives an elegant proof below, by showing
<span class="math-container">$$ PCP \leq_T FullPCP \leq_m MIN_{\textsf{CFG}}$$</span>
in which I personally thought the key is that context-free language is closed under <span class="math-container">$h^{-1}$</span> he defined.</p>

CC BY-SA 3.0
2017-10-30T07:20:27.827Z
Please define $ALL_{\textsf{minCFG}}$.
Aryeh
CC BY-SA 3.0
2017-10-30T07:23:01.333Z
@Aryeh I have defined it informally in my answer. Does informality cause some serious problem?
Lwins
CC BY-SA 3.0
2017-10-30T08:14:36.467Z
No but I'd like to see your formal definition before I comment intelligently.
Aryeh
CC BY-SA 3.0
2017-10-30T12:03:14.707Z
@Aryeh OK. Since there is an enumerator $E$ for $MIN_{\textsf{CFG}}$, we can use $E$ to encode all minimal CFGs to binary string, can't we?
Lwins
CC BY-SA 3.0
2017-10-30T17:25:56.217Z
Before I can comment on your arguments or offer mine, I need to understand your definitions. Can you please define $ALLminCFG$?
Aryeh
CC BY-SA 3.0
2017-11-02T16:30:29.937Z
@Aryeh My classmate found a short formal definition: $ALL_{\textsf{minCFG}} = ALL_{\textsf{CFG}} \cap MIN_{\textsf{CFG}}$. Does it help?
Lwins
CC BY-SA 3.0
2017-11-02T17:18:59.557Z
Yes it does. Will think...
Aryeh
CC BY-SA 3.0
2017-11-03T08:39:05.130Z
Modify the usual proof of undecidability of ambiguity, which is from a reduction from the Post Correspondence Problem.
Sylvain
CC BY-SA 3.0
2017-11-04T17:34:30.400Z
@Sylvain Would you please point out where we should make a change to the original grammar for proving undecidability of ambiguity?
Lwins
CC BY-SA 4.0
2020-10-12T18:34:57.927Z
@xdavidliu I have updated the post. Thank you for letting me rethink of this problem!
Lwins
CC BY-SA 4.0
2020-10-12T18:39:09.633Z
@Lwins Thanks; also what about the comment that chapter 5 doesn't use Turing reductions? It uses them _extensively_ before even introducing mapping reductions, right?
xdavidliu
CC BY-SA 4.0
2020-10-12T18:41:31.243Z
@xdavidliu I have no much memory on this. Maybe they are informal? You can edit my question if you are sure since I have no means to check currently.
Lwins
CC BY-SA 4.0
2020-10-13T15:46:06.910Z
[See here for an alternative explanation for this proof](https://math.stackexchange.com/a/3864146/185635)
xdavidliu
<computability><context-free><decidability>
Show that minimal CFG is undecidable via mapping reduction
Lwins
# Show that minimal CFG is undecidable via mapping reduction

(Asked by: username_0 on 2017-10-30)

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](https://math.stackexchange.com/q/1105117/134950):

> 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| 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.

**Tags:** computability, context-free, decidability
> **Comments:**
> **username_1**: Please define $ALL_{\textsf{minCFG}}$.  
> **username_0**: @Aryeh I have defined it informally in my answer. Does informality cause some serious problem?  
> **username_1**: No but I'd like to see your formal definition before I comment intelligently.  
> **username_0**: @Aryeh OK. Since there is an enumerator $E$ for $MIN_{\textsf{CFG}}$, we can use $E$ to encode all minimal CFGs to binary string, can't we?  
> **username_1**: Before I can comment on your arguments or offer mine, I need to understand your definitions. Can you please define $ALLminCFG$?  
> **username_0**: @Aryeh My classmate found a short formal definition: $ALL_{\textsf{minCFG}} = ALL_{\textsf{CFG}} \cap MIN_{\textsf{CFG}}$. Does it help?  
> **username_1**: Yes it does. Will think...  
> **username_2**: Modify the usual proof of undecidability of ambiguity, which is from a reduction from the Post Correspondence Problem.  
> **username_0**: @Sylvain Would you please point out where we should make a change to the original grammar for proving undecidability of ambiguity?  
> **username_0**: @xdavidliu I have updated the post. Thank you for letting me rethink of this problem!  
> **username_3**: @Lwins Thanks; also what about the comment that chapter 5 doesn't use Turing reductions? It uses them _extensively_ before even introducing mapping reductions, right?  
> **username_0**: @xdavidliu I have no much memory on this. Maybe they are informal? You can edit my question if you are sure since I have no means to check currently.  
> **username_3**: [See here for an alternative explanation for this proof](https://math.stackexchange.com/a/3864146/185635)  

---

## 1 answers

### Answer by username_2 on 2017-11-05. Score: 4 | Accepted answer

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)\_{isolution 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

**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

**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


---

