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

PAGE PAGE 3 淮阴工学院 编译原理课程设计报告 选题名称: 正规文法与有限自动机的相互转换 系（院）: 计算机工程学院 专 业:计算机科学与技术（软件工程方向） 班 级: 软件1082 姓 名: 陈超 学 号: 1081305202 指导教师: 高丽 王文豪 江波 于永彦 学年学期: 2011 ~ 2012 学年 第 1 学期 2012 年  摘要： 正规文法包括左线性文法和右线性文法。由于正规文法和正规表达式在描述语言的能力上是等价的，而正规表达式和有限自动机在描述语言的能力上也是等价的，因此，正规文法和有限自动机之间也存在着等价性。通常，对于正规文法G和有限自动机M，G所定义的语言记作L(G)，M所能识别的语言记作L(M)，如果有L(G)=L(M),则称G和M是等价的。 关键词：正规文法；有限自动机；等价性；构造方法 目 录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc315076723 1课题综述 PAGEREF _Toc315076723 \h 3 HYPERLINK \l _Toc315076724 1.1目的 PAGEREF _Toc315076724 \h 3 HYPERLINK \l _Toc315076725 1.2设计内容 PAGEREF _Toc315076725 \h 3 HYPERLINK \l _Toc315076726 1.3设计原则 PAGEREF _Toc315076726 \h 4 HYPERLINK \l _Toc315076727 2系统分析 PAGEREF _Toc315076727 \h 4 HYPERLINK \l _Toc315076728 2.1正规式 PAGEREF _Toc315076728 \h 4 HYPERLINK \l _Toc315076729 2.2有限自动机（有穷自动机） PAGEREF _Toc315076729 \h 5 HYPERLINK \l _Toc315076730 2.3NFA向DFA的转换 PAGEREF _Toc315076730 \h 5 HYPERLINK \l _Toc315076731 2.4正规式与有限自动机之间的转换 PAGEREF _Toc315076731 \h 6 HYPERLINK \l _Toc315076732 3系统设计 PAGEREF _Toc315076732 \h 6 HYPERLINK \l _Toc315076733 3.1从正规文法到有限自动机 PAGEREF _Toc315076733 \h 6 HYPERLINK \l _Toc315076734 3.11正规文法到有限自动机的等价性证明 PAGEREF _Toc315076734 \h 6 HYPERLINK \l _Toc315076735 3.12 正规文法到有限自动机的构造方法 PAGEREF _Toc315076735 \h 8 HYPERLINK \l _Toc315076736 3.2从有限自动机到正规文法 PAGEREF _Toc315076736 \h 8 HYPERLINK \l _Toc315076737 3.21 有限自动机到正规文法的等价性证明 PAGEREF _Toc315076737 \h 8 HYPERLINK \l _Toc315076738 3.22 有限自动机到正规文法的构造方法 PAGEREF _Toc315076738 \h 9 HYPERLINK \l _Toc315076739 4代码编写 PAGEREF _Toc315076739 \h 10 HYPERLINK \l _Toc315076740 5运行与测试 PAGEREF _Toc315076740 \h 14 1课题综述 1.1目的 1.理解正规文法与有限自动机（FA）的本质联系； 2.掌握正规文法与有限自动机之间相互转化的算法原理； 3.学会使用Visual C++等编程工具实现正规文法与有限自动机之间的相互转化； 1.2设计内容 使用Visual C++/Visual C#等工具，设计软件MySoft_3，可以实现以下功能： 1.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取文法的产生式、非终结符、终结符、开始符等基本信息； 2.判断该文法是否为正规文法，若是，则将其转化为有限自动机； 3.根据用户输入的文本文件（*.txt）的名称，打开文件，并从文件中获取有限自动机的状态集、