首页 | 本学科首页   官方微博 | 高级检索  
     

关于Chomsky范式的算法及其实现
引用本文:孙燮华.关于Chomsky范式的算法及其实现[J].中国计量学院学报,2006,17(3):238-242.
作者姓名:孙燮华
作者单位:中国计量学院,信息工程学院,浙江,杭州,310018
摘    要:在形式语言中通过Chomsky范式“标准化”上下文无关文法,从而构造性地证明了:给定一上下文无关文法G=(V,∑,R,S)和一字符串x,必存在多项式算法确定是否x∈L(G)。本文指出了Harry R Lew-is,Christos H Papadimitrion的著作在定义Chomsky范式算法中的若干不妥之处,并进行了修改,且实现了Chomsky范式算法的程序.

关 键 词:上下文无关文法  Chomsky范式  算法
文章编号:1004-1540(2006)03-0238-05
收稿时间:2006-01-21
修稿时间:2006-01-21

On the algorithm of chomsky normal form and its complementation
SUN Xie-Hua.On the algorithm of chomsky normal form and its complementation[J].Journal of China Jiliang University,2006,17(3):238-242.
Authors:SUN Xie-Hua
Affiliation:College of Information Engineering, China Jiliang University, Hangzhou 310018, China
Abstract: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.
Keywords:context-free grammar  chomsky normal forms  algorithm
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号