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

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 -> nothing 排除在外。

我已经成功处理了数十个应用程序，但这是我的语法自我崩溃的第一个案例。

这怎么可能？我做错了什么吗？有没有只有无用符号的CFG？

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

Answer 1

definition of a context-free grammar does not require its symbols to be reachable or productive, although every context-free grammar can be transformed into a ~~weakly~~ strongly equivalent (thanks, rici) grammar with no useless symbols. However, since the language of your grammar 是非空的，您可能应用了不正确的转换。例如，您的语法生成字符串 aab:

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

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

Can a Context-free grammar exist, where all of its symbols are useless?

context-free-grammar