消除epsilon产生

Question

我在这类问题上遇到了麻烦。有人能帮我吗？

删除以下CFG中的epsilon-productions。

S -> 0X0 | 1Y1 |欧元

X -> Z|0

Y -> ZYU |10欧元

Z -> 0Z1 | XZWZ |欧元

W -> X|Y| 01

Answer 1

规则是这样的:如果X -> epsilon，那么您可以在任何有像Y -> rXs这样的结果的地方添加形式为Y -> rs的结果，然后消除X -> epsilon。唯一的例外是，如果不从生成的语言中删除空字符串，就无法消除生产S -> epsilon。如果一些非终结符被证明是等价的，则应该将它们压缩为单个符号，以避免循环。

S -> 0X0 | 1Y1 |€
X -> Z | 0
Y -> ZYU | €
Z -> 0Z1 | XZWZ | €
W -> X | Y | 01

我们可以从Y开始：

S -> 0X0 | 1Y1 | 11 | epsilon
X -> Z | 0
Y -> ZYU | ZU
Z -> 0Z1 | XZWZ | epsilon
W -> X | Y | 01 | epsilon

接下来让我们转到W：

S -> 0X0 | 1Y1 | 11 | epsilon
X -> Z | 0
Y -> ZYU | ZU
Z -> 0Z1 | XZWZ | XZZ | epsilon
W -> X | Y | 01

接下来让我们做Z：

S -> 0X0 | 1Y1 | 11 | epsilon
X -> Z | 0 | epsilon
Y -> ZYU | ZU | YU | U
Z -> 0Z1 | XZWZ | XZZ | 01 | XWZ | XZW | XW | XZ | X
W -> X | Y | 01

我们看到乘积X，->，Z和Z，->，X，所以这两个符号是等价的。组合：

S -> 0X0 | 1Y1 | 11 | epsilon
X -> 0 | epsilon | 0X1 | 01 | XW | XX
Y -> XYU | XU | YU | U
W -> X | Y | 01

现在让我们做X：

S -> 0X0 | 1Y1 | 11 | 00 | epsilon
X -> 0 | 0X1 | 01 | W | XX
Y -> XYU | XU | YU | U
W -> X | Y | 01 | epsilon

我们看到乘积X，->，W，->，X，所以这两个符号是等价的。组合：

S -> 0X0 | 1Y1 | 11 | 00 | epsilon
X -> 0 | 0X1 | 01 | XX | Y | epsilon
Y -> XYU | XU | YU | U

我们再做一次X：

S -> 0X0 | 1Y1 | 11 | 00 | epsilon
X -> 0 | 0X1 | 01 | XX | Y
Y -> XYU | XU | YU | U

这应该是正确的，除非我使用的规则之一是错误的(等价符号可以组合，消除epsilon的规则)，我所做的简化之一是错误的，或者我做了一个错误的假设(U是一个终端，因为它不在产品的LHS上)。