parsing - 转换为乔姆斯基范式

Question

我确实需要你的帮助。我有这些作品：

1) A--> aAb
2) A--> bAa
3) A--> ε

我应该应用乔姆斯基范式（CNF）。

为了应用上述规则，我应该：

1. 消除ε产生
2. 消除酉产生
3. 删除无用的符号

我马上就卡住了。原因是 A 是可以为空的符号（ε 是其主体的一部分）

当然，我不能删除 A 符号。

谁能帮我得到最终的解决方案？

Answer 1

正如维基百科所指出的，乔姆斯基范式有两种定义，它们在 ε 产生式的处理上有所不同。您必须选择允许这些的语法，否则您将永远不会得到等效的语法：您的语法产生空字符串，而遵循其他定义的 CNF 语法则无法做到这一点。

Answer 2

要开始转换为乔姆斯基范式（使用维基百科页面提供的定义（1）），您需要找到一个等效的本质上非收缩语法。G带有开始符号的文法S本质上是非收缩的 iff

1. S is not a recursive variable
2. G has no ε-rules other than S -> ε if ε ∈ L(G)

调用您的语法，具有非递归开始符号G的等效语法是：G'

G' : S -> A
     A -> aAb | bAa | ε

显然，is 的可空变量集G'是{S,A}，因为A -> ε是一个产生式，G'并且S -> A是一个链式规则。我假设你已经获得了一个从语法中删除 ε-规则的算法。该算法应该产生类似于以下的语法：

G'' : S -> A | ε
      A -> aAb | bAa | ab | ba

语法G''本质上是非收缩的；您现在可以将剩余的算法应用于文法，以找到 Chomsky 范式的等价文法。