转换为乔姆斯基范式 [英] Conversion to Chomsky Normal Form

问题描述

我确实需要您的帮助. 我有这些作品:

I do need your help. I have these productions:

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

我应该应用乔姆斯基范式(CNF).

I should apply the Chomsky Normal Form (CNF).

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

In order to apply the above rule I should:

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

我立即陷入困境.原因是A是可为空的符号(ε是其主体的一部分)

Immediately I get stuck. The reason is that A is a nullable symbol (ε is part of its body)

我当然不能删除A符号.

Of course I can't remove the A symbol.

有人可以帮助我获得最终解决方案吗?

Can anyone help me to get the final solution?

推荐答案

要开始转换为Chomsky范式(使用Wikipedia页面提供的定义(1))，您需要找到一个等效的，本质上是非合同的语法.开头为S的语法G本质上是无约束的iff

To begin conversion to Chomsky normal form (using Definition (1) provided by the Wikipedia page), you need to find an equivalent essentially noncontracting grammar. A grammar G with start symbol S is essentially noncontracting iff

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

调用语法G时，具有非递归开始符号的等效语法G'为:

Calling your grammar G, an equivalent grammar G' with a non-recursive start symbol is:

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

很显然，G'的可为空的变量集是{S,A}，因为A -> ε是G'的生成，而S -> A是链规则.我假设您已获得一种从语法中删除ε规则的算法.该算法应产生类似于以下内容的语法:

Clearly, the set of nullable variables of G' is {S,A}, since A -> ε is a production in G' and S -> A is a chain rule. I assume that you have been given an algorithm for removing ε-rules from a grammar. That algorithm should produce a grammar similar to:

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

语法G''本质上是非契约的；您现在可以将其余算法应用于语法，以找到Chomsky范式的等效语法.

The grammar G'' is essentially noncontracting; you can now apply the remaining algorithms to the grammar to find an equivalent grammar in Chomsky normal form.

这篇关于转换为乔姆斯基范式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！