| 右线性文法与有限自动机等价性的一个新证明 |
| |
| 引用本文： | 韩光辉,曾诚.右线性文法与有限自动机等价性的一个新证明[J].电脑与信息技术,2012,20(1):1-4,32. |
| |
| 作者姓名： | 韩光辉 曾诚 |
| |
| 作者单位： | 1. 武汉商业服务学院信息工程系,湖北武汉,430056
2. 武汉大学软工程国家重点实验室,湖北武汉,430072 |
| |
| 基金项目： | 国家自然科学基金，湖北省教育科学"十一五"规划课题 |
| |
| 摘 要： | 迄今为止,左、右线性文法与有限自动机的等价性都是通过相互模拟构造来证明的。文章首先引入字母表上的右线性方程组及其最小解的概念,证明了最小解的存在性与有效可解性,描述了最小解的结构;其次通过右线性方程组及其最小解,证明了右线性文法与有限自动机的等价性。完全类似地,可以引入字母表上的左线性方程组及其最小解,并且证明左线性文...
|
| 关 键 词： | 右线性文法 有限自动机 等价性 右线性方程组 最小解 |
A New Proof of Equivalence of Right-linear Grammar and Finite Automata |
| |
| HAN Guang-hui,ZENG Cheng.A New Proof of Equivalence of Right-linear Grammar and Finite Automata[J].Computer and Information Technology,2012,20(1):1-4,32. |
| |
| Authors: | HAN Guang-hui ZENG Cheng |
| |
| Affiliation: | 1.Information Engineering Department,Wuhan Commercial Service College,Wuhan 430056,China; 2.State Key Laboratory of Software Engineering,Wuhan University,Wuhan 430072,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | right-linear grammar finite automata equivalence system of right-linear equations minimal solution |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
