关于Chomsky范式的算法及其实现

On the algorithm of chomsky normal form and its complementation

在形式语言中通过Chomsky范式“标准化”上下文无关文法,从而构造性地证明了:给定一上下文无关文法G=(V,∑,R,S)和一字符串x,必存在多项式算法确定是否x∈L(G)。本文指出了Harry R Lew-is,Christos H Papadimitrion的著作在定义Chomsky范式算法中的若干不妥之处,并进行了修改,且实现了Chomsky范式算法的程序.

In formal languge, context-free grammer with Chomsky normal forms is normalized. It is proved constructly that there is a polynomial algorithm which, given a context-free grammar G and a string x, decides whether x∈L（G）. In this paper, we revise the algorithm of Chomsky normal forms of book written by Harry R Lewis and Christos H Papadimitrion, and complete the program for the algorithm.