设 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 -> 什么都没有。
我已经成功处理了数十个申请，但这是我的语法 self 崩溃的第一个案例。
这怎么可能？难道我做错了什么吗？有没有只有无用符号的CFG？
编辑:我提醒算法的步骤:
1)删除非生成符号(生成X有一个至少一个推导X -> w，其中w是一串终结符)
2)删除不可到达的符号(如果S -> αXβ，则X是可达的)
最佳答案
definition上下文无关语法不要求其符号为 reachable or productive ，尽管每个上下文无关语法都可以转化为 weakly strongly equivalent (谢谢，rici)没有无用符号的语法。然而，自从language of your grammar是非空的，您可能错误地应用了转换。例如，您的语法生成字符串 aab:
S ⇒ aA (S → aA)
⇒ aaD (A → aD)
⇒ aab (D → b)
关于context-free-grammar - 是否存在所有符号都无用的上下文无关语法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59800629/