4
$\begingroup$

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}}$:


Surely without loss of generality we can force $\Sigma = \{0,1\}$. It seems like 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. 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 $$ Now consider what will happen if $G^+_{a_1a_2\cdots a_p}$ is not minimal, thus, there exists a rule $R$ in $G^+$ is 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)$.

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^*$.


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.

$\endgroup$
  • 1
    $\begingroup$ Please define $ALL_{\textsf{minCFG}}$. $\endgroup$ – Aryeh Oct 30 '17 at 7:20
  • $\begingroup$ @Aryeh I have defined it informally in my answer. Does informality cause some serious problem? $\endgroup$ – Lwins Oct 30 '17 at 7:23
  • $\begingroup$ No but I'd like to see your formal definition before I comment intelligently. $\endgroup$ – Aryeh Oct 30 '17 at 8:14
  • $\begingroup$ @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? $\endgroup$ – Lwins Oct 30 '17 at 12:03
  • 2
    $\begingroup$ @Aryeh My classmate found a short formal definition: $ALL_{\textsf{minCFG}} = ALL_{\textsf{CFG}} \cap MIN_{\textsf{CFG}}$. Does it help? $\endgroup$ – Lwins Nov 2 '17 at 16:30
3
$\begingroup$

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$
$\endgroup$

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.