0

我有以下 CFG 规则：

  • S -> BSA | ε
  • A -> abC | 一个 | C
  • B -> baC | 乙 | ε
  • C -> 抄送 | AB | ε

我处于算法的 epsilon 消除阶段，我已经消除了以下 epsilon C -> epsiolon，B -> epsilon，这是我到目前为止得到的：

  • S_0 -> S
  • S -> BSA | 南非 | ε
  • A -> abC | 一个 | c| 抗体
  • B -> baC | 乙 | 巴
  • C -> 抄送 | AB | 交流| A 由于 S 是原始起始变量，我是否还应该消除 S-> epsilon（以粗体显示）？

我还应该在算法的单元规则阶段将 epsilon 复制到 S_0 吗？

4

1 回答 1

1

我是你的第一个语法，你可以epsilon从S. 所以空词属于被描述的语言。因此，您必须epsilon在第二个等效语法中具有a。现在在正常形式的语法中，当有推导时S -> epsilon，S就不能出现在推导的右侧。所以规则

S -> BSA | SA | epsilon

不允许是乔姆斯基范式。所以你可能想要一些东西

S_0 -> S | epsilon      // initial
S -> BA | A | BSA | SA
[...]
于 2014-03-09T17:28:18.493 回答