一.单选题
1.是否存在这样一些语言,它们能被确定有限自动机识别,但不能用正则表达式表示。
A、存在
B、不存在
C、无法判定是否存在
正确答案： B
正则表达式和自动机在接受语言的能力上是等价的。
2.将识别各类单词的有限自动机合并后得到的有限自动机会:
A、可能是NFA,也可能是DFA
B、一定是DFA
C、一定是NFA
D、一定是最小的DFA
正确答案： A
3.词法分析器的输入是( )
A、单词符 串
B、源程序
C、语法单位
D、目标程序
正确答案： B
词法分析器的功能是将源程序由字符序列转换等价的token序列,并检查源程序中的词法错误,因此词法分析器的输入是源程序。
4.作为语法分析程序子程序的词法分析程序,它的返回结果是( )
A、单词属性值
B、单词在符 表中的位置表示法
C、单词的种别编码和语义值
D、单词的种别编码
正确答案： C
当词法分析程序作为语法分析器的子程序存在时,语法分析器的每次调用,词法分析器都会返回一个token,token是单词的机内表示,包含单词的种类信息和语义值。
5.将编译程序分成若干个“遍”是为了( )
A、利用有限的机器内存并提高机器的执行效率
B、使程序的结构更加清晰
C、提高程序的执行效率
D、利用有限的机器内存但降低了机器的执行效率
正确答案： B
所谓“遍”就是对源程序或源程序的中间表示形式从头到尾扫描一次,并作加工处理,生成新的中间结果或目标程序。编译程序分成若干“遍”,实际就是编译程序对源程序或其等价的中间代码扫描了若干次,每次都执行不同的功能,这样做的目的是编译程序的结构更加清晰。
6.词法分析中能够发现以下( )错误。
A、操作数类型不匹配
B、标识符重复声明
C、程序中出现非法符
D、除法溢出
正确答案： C
词法分析器的功能是将源程序由字符序列转换等价的token序列,并检查源程序中的词法错误,以上错误中,只有非法符合属于词法错误。
7.编译程序中的语法分析器接受以 为单位的输入,并产生有关信息供以后各阶段使用。
A、表达式
B、产生式
C、单词
D、语句
正确答案： C
8.在词法分析阶段不能识别的是( )。
A、标识符
B、运算符
C、四元式
D、常数
正确答案： C
二.多选题
1.正则表达式和有限自动机的关系以下说法正确的是:
A、一个正则表达式只能等价于一个确定的有限自动机
B、正则表达式、NFA和DFA在接受语言的能力上是相互等价的
C、对任何形式正则表达式r,都存在一个NFA M,满足L(M)=L(r)
D、一个正则表达式可以转化为一个等价的自动机,但自动机不一定都能表示为等价的正则表达式
正确答案： BC
正则表达式和自动机在接受语言的能力上是等价的,并且一个正则表达式有可能等价于多个自动机。
2.与DFA相比，NFA的非确定性体现在:
A、允许有多个开始状态
B、允许有多个终止状态
C、在没有任何输入的情况下允许进行状态转换
D、一个状态可以有多个不同后继状态
正确答案： AC
3.关于NFA的确定化说法正确的是:
A、NFA的确定化算法具有消除ε空边的功能
B、给定一个NFA,一定存在一个DFA,使得两者等价
C、一个NFA只能存在一个DFA与其等价
D、NFA确定化后会使得状态转换函数成为单值函数
正确答案： ABD
根据等价定理B正确。而且NFA确定化后转化为DFA,而DFA无空边,且状态转换函数是单值函数,所以A和D正确。C错是因为NFA等价的DFA可以有多个,但最简DFA就一个。
4.以下说法正确的是:
A、NFA确定化后就成为最简DFA
B、一个自动机的最简DFA是唯一的
C、没有等价状态的DFA是最简DFA
D、DFA终止状态和非终止状态是不等价的
正确答案： BD
和NFA等价的DFA可以有多个,但最小化的DFA只有一个。C错是因为如果没有无关状态,也没有等价状态的DFA才是最简DFA。
三.简答题
1.对下图所示非确定有限状态自动机M，将M分别进行确定化和最小化。
正确答案：
（1）NFA非确定机转为DFA确定机
|
a |
b |
|
|
{1,2,3,4}+ |
{2,3,4} |
{2,3,4,5} |
|
{2,3,4} |
{2,3,4} |
{2,3,4,5} |
|
{2,3,4,5}* |
{2,3,4} |
{2,3,4,5} |
（2）DFA化简
｛1,2,3,4}和{2,3,4}遇到a和b的后继状态一样，为等价状态。
所以最简DFA为两个状态:A: {1,2,3,4} ,{2,3,4} , B:{2,3,4,5}
最简DFA如下：
PS:
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！