3
$\begingroup$

Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without changing the language.

Note this is not the same as asking whether the grammar has the minimum possible number of rules to generate the language, since we can imagine two grammars with different number of rules, none of which are useless, generating the same language.

For the general case of an arbitrary context-free grammar (i.e. not necessarily in Chomsky normal form), it is definitely undecidable whether any of the rules are useless (proving this is given as problem 5.36b in Sipser 3rd edition). Of course, we cannot just use the general result as a "subroutine" here, since converting to Chomsky normal form drastically changes the rules (even if not the language).

A related question asks if grammars in Chomsky normal form can have useless rules, and the answer is clearly yes.

Improve this question
$\endgroup$
4
  • $\begingroup$ You can have a rule of form S -> A C | B C, C -> c, and $A$ and $B$ have disjoint sets of nonterminals in their derivations. Now you need to check if $L(A) \subseteq L(B)$ or $L(B) \subseteq L(A)$, which is undecidable. Am I missing something? $\endgroup$
    – user114966
    Commented Oct 12, 2020 at 18:27
  • $\begingroup$ I don't understand your comment. By $L(A)$ I mean the set of all strings which can be derived from $A$. You can make two sets of nonterminals disjoint by simply renaming them (the whole point of disjointness is to remove any interaction between $L(A)$ and $L(B)$) $\endgroup$
    – user114966
    Commented Oct 12, 2020 at 19:21
  • $\begingroup$ apologies, I misread your original comment as "disjoint sets of terminals". Let me take a closer look... $\endgroup$
    – xdavidliu
    Commented Oct 12, 2020 at 19:23
  • $\begingroup$ I wonder if we can reduce from testing whether a CFG generates all possible strings. Let $G$ be a grammar over alphabet $a,b$ with start symbol $S$; perhaps we can remove useless rules from $G$, then add $S \to T$, $T \to \varepsilon | aT | bT$, where $T$ is a new nonterminal, and test whether the resulting grammar has any useless rules (if not, then the original grammar doesn't generate all possible strings). This doesn't quite work, for multiple reasons, but perhaps there's some way to fix it up? $\endgroup$
    – D.W. ♦
    Commented Oct 12, 2020 at 21:57

0

Reset to default