CFG转CNF（附代码）

定理3.6 任一上下下文无关文法都可以用乔姆斯基范式的上下文无关文法产生。

证明思路 能够把任一上下文无关文法G转换成乔姆斯基范式。转换分几个阶段把不符合要求的规则替换成等价的符合要求的规则。首先，添加一个新的起始变元。然后删除所有形如的规则，再删除所有形如的单一规则。在删除时，要对文法做适当的弥补，使得它仍然产生相同的语言。最后，把所有留下来的规则转换成适当的形式。

证明

1. 首先，添加一个新的起始变元和规则，其中S是原来的起始变元。这样可以保证起始变元不出现在规则的右边。

2. 第二阶段，考虑所有的规则。删除一条规则，这里A不是起始变元。对在规则右边出现的每一个A，删除这个A后得到一条新的规则。换句话说，如果是一条规则，其中u和v是变元和终结符的字符串，则添加规则。对A的每一次出现都如此进行，因而对于规则，要添加，，和。如果有规则，则要添加，除非前面已经删除过规则。重复上述步骤，直至删除所有不包括起始变元的规则。

3. 第三阶段，处理所有的单一规则。删除一条单一规则。然后，只要有一条规则，就要添加规则，除非是已在前面被删除的单一规则。和前面一样，u是变元和终结符的字符串。重复上述步骤，直至删除所有的单一规则。

4. 最后，把所有留下的规则转化成适当的形式。把每一条规则替换成规则，其中，每一个是一个变元或终结符，是新的变元。至此，所有的规则只能是下述几种形式：
   1
   2
   3
   4
   5
   6

其中是终结符，A、B、C是变元，是开始阶段引入的新起始变元。前3中规则已经符合要求。为了把后三种规则转换成符合要求的规则，对每一个终结符引入一个新的变元和规则（如果不出现在规则的右边，则不需要引入），把后3中规则分别替换成，和。

CFG转CNF代码（github）