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

摘要

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.%迄今为止,左、右线性文法与有限自动机的等价性都是通过相互模拟构造来证明的。文章首先引入字母表上的右线性方程组及其最小解的概念,证明了最小解的存在性与有效可解性,描述了最小解的结构;其次通过右线性方程组及其最小解,证明了右线性文法与有限自动机的等价性。完全类似地,可以引入字母表上的左线性方程组及其最小解,并且证明左线性文法与有限自动机的等价性;最后简要阐述了右线性方程组在有限自动机的矩阵模型和正则语言类的形式模型方面的研究意义。