上下文无关文法是否存在，其所有符号都无用？

Question

让G是上下文无关的语法，从终端（a，b）定义，从S开始并具有变量（A，B，C，D，E，F，G）

具有这些生产规则：

S -> aA | BD
A -> aA | aAB | aD
B -> aB | aC | BF
C -> Bb | aAC | E
D -> bD | bC | b
E -> aB | bC
F -> aF | aG | a
G -> a | b

我试图先减少非生成符号，删除A，B，C和E。然后，在跟踪了无法到达的符号之后，我被S->什么都不留了。

我已经成功处理了数十种应用程序，但这是我的语法自爆的第一种情况。

这怎么可能？我做错了什么吗？是否有仅带有无用符号的CFG？

编辑：我提醒算法的步骤：1）删除非生成符号（生成X具有至少一个导数X-> w，其中w是一串终端）2）删除不可访问的符号（如果S->αXβ，则X可以访问）

Answer 1

无上下文语法的definition不需要其符号为reachable or productive，尽管每个无上下文语法都可以转换为weakly strongly equivalent（谢谢，）语法而没有用处符号。但是，由于language of your grammar是非空的，因此您可能错误地应用了转换。例如，您的语法生成字符串aab：

S ⇒ aA  (S → aA)
  ⇒ aaD (A → aD)
  ⇒ aab (D → b)