欢迎您光临某某医疗机构!

正规文法_NFA_DFA_状态转换图_正规式之间的等价变

时间:2020-03-29 02:00

  正规文法_NFA_DFA_状态转换图_正规式之间的等价变换关系及变换方法

  四川师范大学学报(自然科学版)Journal niversity(Natural Science) Vo 1997收稿日期1996212203 正规文法、N FA、DFA、状态转换图、正规式 之间的等价变换关系及变换方法 (四川师范大学计算机科学系成都610066) 摘要正规文法、NFA、DFA、状态转换图、正规式是形式语言理论的基础概念, 也是 编译原理词法分析理论中的重要概念和工具. 本文讨论了它们之间的等价变换关系, 出了变换的具体方法并简介了它们的用途.关键词正规文法, NFA 状态转换图,正规式, 等价变换 中图法分类号TP301. 在编译原理词法分析理论中,均要涉及到正规文法、N FA、DFA、状态转换图、正规式这几 个重要内容. 它们分别在词法分析及词法分析器自动生成的理论研究、表示及实现等方面, 着重要作用.本文将完整地给出它们之间的等价变换关系和具体的变换方法. 1正规文法与N FA 间的等价变换 由正规文法G 所描述的语言L 和对应的NFA 之间存在等价性(其证明见参考文献[ 故可构造正规文法到NFA 的转换方法. 反之, 亦可从N FA 转换 到正规文法. 两者之间的转换方法为文法产生式与N FA 的函数的对应转换(见参考文献 可知,正规文法与N FA 之间可等价转换. FA与DFA 间的等价变换 之间存在等价性(其证明见参考文献[ 并可用子集法和等价类划分法把NFA 转换为等价的最小化的DFA (其转换方法见参考文献[ 又由正规文法NFA FADFA 所以正规文法与DFA间可等价转换(其转换方法见 参考文献[ FA与状态转换图间的等价变换 由状态转换图的定义, 可知状态转换图只不过是N FA 的图形化表示, FA是一一对 FA可等价的转换为状态转换图, 反之, 状态转换图亦可转换为N FA. 态转换图间可等价变换,且它们之间的转换方法是函数与图形化表示的一一对应. 又由正规文法N FA FA状态转换图, 所以正规文法与状态转换图间亦可等价转换. 下面给出正规文法与状态转换图间的相互转换方法(产生式与图结点和边的对应转换法) 记正规文法G中的开始符号S 正规文法G中的其余非终结符A 则正规文法G产生式集P 中的产生式, 可由下述规则转换为状态转换图中的状态结点和 的产生式,转换为 的产生式,转换为 按照上述规则,正规文法G 一定可等价转换为对应的状态转换图T. 反之, 按照上述规 状态转换图T一定可等价转换为对应的正规文法G. FA与正规式间的等价变换 和对应的正规式R所描述的语言L 并可用指定的算法(规则)把正规式转换为N FA (其算法见参考 文献[ 下面给出把NFA 转换为正规式R的方法(按转换规则逐步压缩法) 上的终结符串,正规式R 形如R1R2…Rn, Ri am;若有(qi 且不相等;若ri, 开始,反复利用(1) 把多个形如ri, j、rj 直至联结到ri, 为止.所得串即为R 中的一个独立项Ri 所有的Ri便组成正规式R 又由正规文法NFA FA正规式, 所以正规文法和正规式间可等价转换. 正规文法可 用正规方程式联立求解的方法, 转换为正规式(其具体作法见参考文献[ 四川师范大学学报(自然科学版)20 为正规文法,可借助于对应的N FA 实现, 即正规式 FA正规文法. 5转换关系图 通过上述讨论, 可知正规文法、N FA、DFA、状态转换图和正规式它们之间的转换关系可 表示:图结点 产生式转换成 对应的 图结点 函数转换成对应的产生式当正规文法G本身为DFA时, 产生式转换成对应的函数 状态转换图 函数转换成对应的产生式 当正规文法G为最小DFA时产生式转换成对应的函数 产生式转换为 正规方 立求解正规式 最小DFA 等价类划分法 DFA 子集法 NFA 函数转换成 对应的产生式 产生式转换成 对应的函数 正规文法 1转换关系图6用途 正规文法是正规语言(正规集)的形式化描述, 用于正规语言的形式化表示和理论研 ii)有穷自动机FA FA和DFA 是具有有限个记忆的离散动态系统的形式模型,用于 数字计算机、图形识别、信息和编码以及神经过程等的形式模型表示和研究. 在编译原理的词 法分析中, 用于单词识别、生成过程的模型表示和实现. iii)状态转换图是正规文法、有穷自动机FA 的图形表示, 直观易懂, 与通常的程序流程 图很相近, 易于实现程序的编制. 正规式是正规文法、有穷自动机FA的代数化表示, 它的表示准确、紧凑、高效, 可以 构造高效的词法分析器. 用于词法分析器的自动生成, 也用于各种信息(如模式识别、情报检索 的处理.参考文献 形式语言、自动机和语法分析.湖北: 华中工学院出版社, 1985 2陈火旺, 程序设计语言编译原理.北京: 国防工业出版社, 1984 程序设计语言编译方法.辽宁: 大连理工大学出版社, 1995 EQUIVAL EN TRANSFORMA STATE TRAN SIT ION IAGRAM EXPRESSIONDeng Chaocheng epartm ent Computer ormal Chengdu610066, ichuan)AbstractIn ransformat ion relat ion Regulargrammar, NFA ransition diagram Regularexp ression concretemethods ransformat ion resented.Key wordsRegular grammar, NFA ransition diagram, Regular exp ression, Equivalent ransformat ion Classif ication code 四川师范大学学报(自然科学版)20