转换为乔姆斯基正常形式

我确实需要你的帮助。我有这些作品：转换为乔姆斯基正常形式

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

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

为了应用上面的规则我应该：

我立刻会被卡住。原因是A是空的符号（ε是它的身体的一部分）

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

任何人都可以帮助我获得最终解决方案吗？

2011-06-26 Joachim

正如Wikipedia所指出的，乔姆斯基标准形式有两种定义，它们在ε生产的处理上有所不同。您必须选择允许这些语法的语法，否则您将永远得不到相同的语法：您的语法生成空字符串，而遵循另一个定义的CNF语法不能胜任这一点。

2011-06-26 14:41:59

所以你实际上是在说我的推理完全错误？我应该怎么做？...... – Joachim

@Joachim：我在说你应该仔细阅读维基百科上的定义，并决定你是否想要一个完全等价的语法。 –

我不明白这个评论。由于ε是语法语言的成员，显然第一个定义是适用的。 OPs问题可以通过使语法基本上不收缩来解决，然后去除链式规则和无用的符号。 – danportin

要开始转换为乔姆斯基标准格式（使用维基百科页面提供的定义（1）），您需要找到一个基本上等价的非收缩语法。文法G与开始符号S基本上noncontracting 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 | ε

显然，一套可空变量G'是{S,A}，因为A -> ε是生产G'而S -> A是连锁规则。我假设你已经有了一个从语法中去除ε-规则的算法。该算法应产生类似于下面的语法：

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

语法G''基本上是非收缩的;您现在可以将其余的算法应用到语法中，以查找Chomsky标准形式的等价语法。

2011-06-26 23:36:58 danportin

非常感谢您的解释。不幸的是，我仍然遇到解决练习的问题。我是一名学生，因为几天后我要参加考试（编程语言和编译器）......我想知道我是否可以依靠某些知识来填补我的空白......是我的电子邮件地址：[email protected]谢谢 – 2011-06-27 16:39:51

如果您试图首先解决问题并接受答案，您可能会发现SO的成员知识渊博，乐于助人。 – danportin

回答