右线性文法与有限自动机等价性的一个新证明  

A New Proof of Equivalence of Right-linear Grammar and Finite Automata

作　　者：韩光辉[1] 曾诚[2] 

机构地区：[1]武汉商业服务学院信息工程系,湖北武汉430056 [2]武汉大学软工程国家重点实验室,湖北武汉430072

出　　处：《电脑与信息技术》2012年第1期1-4,32,共5页Computer and Information Technology

基　　金：国家自然科学基金(项目编号:60873083);湖北省教育科学"十一五"规划课题(项目编号:2010B338)

摘　　要：迄今为止,左、右线性文法与有限自动机的等价性都是通过相互模拟构造来证明的。文章首先引入字母表上的右线性方程组及其最小解的概念,证明了最小解的存在性与有效可解性,描述了最小解的结构;其次通过右线性方程组及其最小解,证明了右线性文法与有限自动机的等价性。完全类似地,可以引入字母表上的左线性方程组及其最小解,并且证明左线性文法与有限自动机的等价性;最后简要阐述了右线性方程组在有限自动机的矩阵模型和正则语言类的形式模型方面的研究意义。So far,equivalence of left-linear or right-linear grammar and finite automata is proved by using mutual simulation.In this paper,concepts of system of right-linear equations over an alphabet and its minimal solution are introduced,existence and effective solvability of the minimal solution are proved,and structure of the minimal solution is described;A new proof of equivalence of right-linear grammar and finite automata is presented based on the system of right-linear equations and its minimal solution.Similarly,system of left-linear equations over an alphabet and its minimal solution can be introduced,then equivalence of left-linear grammar and finite automata can be proved;Finally,significance of system of right-linear equations,in researches on matrix models of finite automata and formal models of class of regular languages,is briefly elaborated.

关 键 词：右线性文法 有限自动机 等价性 右线性方程组 最小解 

分 类 号：TP301.2[自动化与计算机技术—计算机系统结构]