正规文法与有限自动机的相互转换
二零一五年十二月二十七日
目 录
摘要................................................................ 1 关键词.............................................................. 1 1课题综述 .......................................................... 1 1.1目的 ............................................................ 1
1.2设计内容..................................................... 1 1.3设计原则..................................................... 1 2系统分析 .......................................................... 2 2.1正规式 .......................................................... 2 2.2有限自动机（有穷自动机） ........................................ 2 2.3NFA向DFA的转换 ................................................. 3 2.4正规式与有限自动机之间的转换 .................................... 3 3系统设计 .......................................................... 4 3.1从正规文法到有限自动机 ...................................... 4
3.11正规文法到有限自动机的等价性证明 ........................ 4 3.12 正规文法到有限自动机的构造方法........................ 5
3.2从有限自动机到正规文法 ...................................... 6
3.21 有限自动机到正规文法的等价性证明....................... 6 3.22 有限自动机到正规文法的构造方法......................... 7
4 运行与测试........................................................ 7
总结 ............................................................ 9 参考文献............................................................ 9 附录............................................................... 10
摘要：正规文法包括左线性文法和右线性文法。由于正规文法和正规表达式在描述语言的能力上是等价的，而正规表达式和有限自动机在描述语言的能力上也是等价的，因此，正规文法和有限自动机之间也存在着等价性。通常，对于正规文法G和有限自动机M，G所定义的语言记作L(G)，M所能识别的语言记作L(M)，如果有L(G)=L(M),则称G和M是等价的。 关键词：正规文法；有限自动机；等价性；构造方法
1课题综述
1.1目的
1.理解正规文法与有限自动机（FA）的本质联系； 2.掌握正规文法与有限自动机之间相互转化的算法原理；
3.学会使用Visual C++等编程工具实现正规文法与有限自动机之间的相互转化； 1.2设计内容
使用Visual C++/Visual C#等工具，设计软件MySoft_3，可以实现以下功能：
1.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取文法的产生式、非终结符、终结符、开始符等基本信息；
2.判断该文法是否为正规文法，若是，则将其转化为有限自动机； 3.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取有限自动机的状态集、字母表、初态、终态集、转移函数等基本信息；
4.判断该自动机是否合法，若合法，则将其转化为正规文法； 1.3设计原则
正规文法与有穷自动机有着特殊的关系，采用下面的规则可从正规文法G直接构造一个有穷自动机NFA M；使得L(M)=L(G)：
（1）M的字母表与G的终结符相同；
第 1 页 共 13 页
（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
正规式主要用到了递归的思想，无论遇到多复杂的正规式都可以拆分成上面这三种形式，然后进行解题。
2.2有限自动机（有穷自动机）
DFA（Deterministic Finite Automation ）：确定的有限自动机表达式：M=（S，∑，f，So，Z）
1.S为一个有限状态集合
2.∑是一个字母表，它所包含的的每个元素称为一个输入字符；
3.f是一个从SX∑（笛卡尔乘积）至S的单值部分映射。f（S，a）=s'意味着当现在的状态为s，输入字符a时，将转换到下一状态s'.s'为s的一个后继状态。
4.So∈S，是唯一的初态； 5.Z?S，是一个终态集。
第 2 页 共 13 页
NFA（Nondeterministic Finite Automata）：不确定的有限自动机如果理解了有限自动机，则无限自动机和它的区别就是上面的第四项。So?S，它的初态不是唯一的，而是一个集合。
2.3NFA向DFA的转换
这个转换是一个比较简单的过程。
1.如果有一个不确定的有限自动机，则可以转化为图的方式。此处不详述怎样转图的方式。
2.先将初态确定，然后根据输入的每个元素可以得到哪些状态，依次列表。 3.这些状态集合可以称为这个有限状态集合n个子集。按0,1,2??的顺序编号。
4.因为这些子集之间的关系是输入一个确定值确定的，所以这些子集之间存在一些关系，即把这些子集的关系写出来完成NFA向DFA的转换。 如果不懂可以从网上找一个例子进行理解。
2.4正规式与有限自动机之间的转换
若
a
b
第 3 页 共 13 页