Timeline for is it decidable whether a grammar in Chomsky normal form has useless rules?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 12, 2020 at 21:57 | comment | added | D.W.♦ | 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? | |
| Oct 12, 2020 at 19:23 | comment | added | xdavidliu | apologies, I misread your original comment as "disjoint sets of terminals". Let me take a closer look... | |
| Oct 12, 2020 at 19:21 | comment | added | user114966 | 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)$) | |
| Oct 12, 2020 at 18:27 | comment | added | user114966 |
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?
|
|
| Oct 12, 2020 at 18:13 | history | edited | xdavidliu |
edited tags
|
|
| Oct 12, 2020 at 17:55 | history | asked | xdavidliu | CC BY-SA 4.0 |