正规文法与有限自动机的相互转换

淮阴工学院

编译原理课程设计报告

选题名称: 正规文法与有限自动机的相互转换 系（院）: 计算机工程学院 专 业:计算机科学与技术（软件工程方向） 班 级: 软件1082 姓 名: 陈超 学 号: 1081305202 指导教师: 高丽 王文豪 江波 于永彦 学年学期: 2011 ~ 2012 学年 第 1 学期

2012 年 01 月 07 日

1

摘要：

正规文法包括左线性文法和右线性文法。由于正规文法和正规表达式在描述语言的能力上是等价的，而正规表达式和有限自动机在描述语言的能力上也是等价的，因此，正规文法和有限自动机之间也存在着等价性。通常，对于正规文法G和有限自动机M，G所定义的语言记作L(G)，M所能识别的语言记作L(M)，如果有L(G)=L(M),则称G和M是等价的。

关键词：正规文法；有限自动机；等价性；构造方法

2

目 录

1课题综述 .................................................................................................................... 3

1.1目的 ·······························································································································3 1.2设计内容 ·······················································································································3 1.3设计原则 ·······················································································································4

2系统分析 .................................................................................................................... 4

2.1正规式 ···························································································································4 2.2有限自动机（有穷自动机） ·························································································5 2.3NFA向DFA的转换 ·······································································································5 2.4正规式与有限自动机之间的转换 ·················································································6

3系统设计 .................................................................................................................... 6

3.1从正规文法到有限自动机 ·····························································································6

3.11正规文法到有限自动机的等价性证明 ................................................................... 6 3.12 正规文法到有限自动机的构造方法 .................................................................. 8 3.2从有限自动机到正规文法 ·····························································································8

3.21 有限自动机到正规文法的等价性证明 ................................................................ 8 3.22 有限自动机到正规文法的构造方法 .................................................................... 9

4代码编写 .................................................................................................................. 10 5运行与测试 .............................................................................................................. 14

1课题综述

1.1目的

1.理解正规文法与有限自动机（FA）的本质联系； 2.掌握正规文法与有限自动机之间相互转化的算法原理；

3.学会使用Visual C++等编程工具实现正规文法与有限自动机之间的相互转化；

1.2设计内容

使用Visual C++/Visual C#等工具，设计软件MySoft_3，可以实现以下功能：

3

1.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取文法的产生式、非终结符、终结符、开始符等基本信息；

2.判断该文法是否为正规文法，若是，则将其转化为有限自动机； 3.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取有限自动机的状态集、字母表、初态、终态集、转移函数等基本信息；

4.判断该自动机是否合法，若合法，则将其转化为正规文法；

1.3设计原则

正规文法与有穷自动机有着特殊的关系，采用下面的规则可从正规文法G直接构造一个有穷自动机NFA M；使得L(M)=L(G)：

（1）M的字母表与G的终结符相同；

（2）为G中的每一个非终结符生成M的一个状态，G的开始符S是开始状态；

（3）增加一个新状态Z，作为NFA的终态；

（4）对G中的形如A->tB的规则（其中T为终结符或，A为非终结符的产生式），构造M的一个转换函数f(A,t)=B；

（5）对G中形如A->t的产生式，构造M的一个转换函数f（A，t）=Z。

2系统分析

2.1正规式

正规式：正则表达式，表示正规集的工具。 一个正规式对应一个正规文法（3型文法） 之间能够进行准换 三个基本规则： A->xB,B->y 则 A=xy。

A->xA|y 则A=x*y （x*代表x从1到无穷多个） A->x,A->y 则A=x|y

4