作业帮自动机如何转换到正规表达式?
来源：学生作业帮 编辑：拍题作业网作业帮 分类：数学作业 时间：2024/04/29 04:59:34
自动机如何转换到正规表达式?
下图为一确定有限自动机的状态转换图,与该自动机等价的正规表达式是__（12）__,图中的__（13）__是可以合并的状态.
（12）A.(a|b)*bb(a*b*)* B.(a|b)*bba*|b*
C.(a*b*)bb(a|b)* D.(a*|b*)*bb(a*|b*)
（13）A.0和1 B.2和3 C.1和2 D.0和3
下图为一确定有限自动机的状态转换图,与该自动机等价的正规表达式是__（12）__,图中的__（13）__是可以合并的状态.
（12）A.(a|b)*bb(a*b*)* B.(a|b)*bba*|b*
C.(a*b*)bb(a|b)* D.(a*|b*)*bb(a*|b*)
（13）A.0和1 B.2和3 C.1和2 D.0和3
1、使用C/C++程序设计语言和递归下降子程序的方法编写该函数绘图语言的词法分析器.并要求设计一个词法分析器的测试小程序来调用自己编写的词法分析器测试各种不同的输入.
2、词法分析的任务是对输入的字符串形式的源程序按顺序进行扫描,在扫描的同时,根据源语言的词法规则识别具有独立意义的单词（符号）,并产生与其等价的属性字流（内部编码）作为输出.通常属性字流即是对识别的单词给出的标记符号的集合.
·目的：
通过自己动手编写词法分析器,掌握记号、模式与单词,掌握正规式与正规集,掌握有限自动机,掌握如何从正规式到词法分析器的各种算法.理解如何理论联系实际以及明白理论与实际的差别.
二、分析与设计
词法分析程序一般具有如下功能:读入字符串形式的源程序;识别出具有独立意义的最小语法单位:单词.
事实上,由正规表达式到最小化DFA的转换源程序中的测试生成串部分就是对所输入的单词进行判断,看其是否能被生成的DFA接受（也就是这个单词是否符合正规式定义的要求）.这本质上就是一个简单的词法分析.
定义某种语言的单词,并给出编号.该语言单词包括：保留字、运算符、标识符、常量、格式符等.根据给定的语言子集构造词法分析器.输出为中间文件.
在设计时为了便于理解,不使用内部编码而用枚举对同类型的单词进行标识.例如所有的常量统一用“CONST_ID”对其进行标识,当扫描时遇到常量就输出该常量的值和“CONST_ID”标识.
这里给出词法分析程序大概的设计方法：
1、根据要求写出词法分析的正规文法G；
2、根据正规文法G,写出正则式RE；
3、根据正则式RE,画出NFA；
4、将NFA转化为DFA；
5、将DFA转化为mininum state DFA；
6、mininum state DFA就是词法分析程序的流程图,根据此流程图编写相应的词 法分析程序.
以下是较为详细的设计：
①总体结构与模块划分
测试模块（scannermain.cpp）
词法分析器模块（scanner.h scanner.cpp）
2、词法分析的任务是对输入的字符串形式的源程序按顺序进行扫描,在扫描的同时,根据源语言的词法规则识别具有独立意义的单词（符号）,并产生与其等价的属性字流（内部编码）作为输出.通常属性字流即是对识别的单词给出的标记符号的集合.
·目的：
通过自己动手编写词法分析器,掌握记号、模式与单词,掌握正规式与正规集,掌握有限自动机,掌握如何从正规式到词法分析器的各种算法.理解如何理论联系实际以及明白理论与实际的差别.
二、分析与设计
词法分析程序一般具有如下功能:读入字符串形式的源程序;识别出具有独立意义的最小语法单位:单词.
事实上,由正规表达式到最小化DFA的转换源程序中的测试生成串部分就是对所输入的单词进行判断,看其是否能被生成的DFA接受（也就是这个单词是否符合正规式定义的要求）.这本质上就是一个简单的词法分析.
定义某种语言的单词,并给出编号.该语言单词包括：保留字、运算符、标识符、常量、格式符等.根据给定的语言子集构造词法分析器.输出为中间文件.
在设计时为了便于理解,不使用内部编码而用枚举对同类型的单词进行标识.例如所有的常量统一用“CONST_ID”对其进行标识,当扫描时遇到常量就输出该常量的值和“CONST_ID”标识.
这里给出词法分析程序大概的设计方法：
1、根据要求写出词法分析的正规文法G；
2、根据正规文法G,写出正则式RE；
3、根据正则式RE,画出NFA；
4、将NFA转化为DFA；
5、将DFA转化为mininum state DFA；
6、mininum state DFA就是词法分析程序的流程图,根据此流程图编写相应的词 法分析程序.
以下是较为详细的设计：
①总体结构与模块划分
测试模块（scannermain.cpp）
词法分析器模块（scanner.h scanner.cpp）