转换为乔姆斯基范式

Question

我确实需要你的帮助。 我有这些产生式：

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

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

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

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

我立即陷入困境。原因是A是一个可为空的符号（ε是其主体的一部分）

当然我不能删除A符号。

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

Answer 1

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

Answer 2

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

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 | ε

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

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

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