正规文法与有限自动机的等价构造  

THE EQUIVALENT CONSTRUCTION BETWEEN REGULAR GRAMMAR AND FINITE AUTOMATA

作　　者：钱忠胜[1] 邹俊[1] 

机构地区：[1]江西财经大学信息管理学院

出　　处：《计算机应用与软件》2008年第6期110-112,共3页Computer Applications and Software

摘　　要：在功能上,正规文法与有限自动机描述和识别语言是等价的,它们之间也存在等价构造算法,但这些构造算法有些复杂。对其算法进行了简化且给以了证明,并提出了一个从有限自动机构造等价左线性正规文法的算法,同时也进行了证明,最后给出了该算法的一个实例。With respect to the function, regular grammar is equivalent to finite automata in accepting languages. There exist some equivalent construction algorithms, which are rather complex. The simplified forms of the constructions and their proofs are presented. A construction about the equivalent transformation from finite automata to left linear regular grammar is also provided and preyed. A relevant example is given.

关 键 词：有限自动机 DFA NFA 正规文法 

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