时间戳

首页 > 解决方案 > 是否存在上下文无关文法，其中所有符号都无用？

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

问题描述

令 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）删除不可到达的符号（如果 X 是可达的，如果S -> αXβ)

标签： context-free-grammar

解决方案

上下文无关文法的定义并不要求其符号是可到达的或有效的，尽管每个上下文无关文法都可以转换为没有无用符号的弱强等价（谢谢，rici ）文法。但是，由于您的语法语言是非空的，您可能错误地应用了转换。例如，您的语法生成字符串aab：

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

推荐阅读