13. 一个正规式只能对应一个有限状态自动机； （ ）
14. 在词法分析的状态转换图中，有些结点是带星号的，这些结点肯定是终态结点。（ ）
15. 适当设置扫描缓冲区的大小（比如容纳256个字符）可以保证单词符号不会被它的边界所 打断。（ ） 解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
三.单项选择题
1. 程序语言下面的单词符号中，____一般不需要超前搜索 a. 关键字 b. 标识符 c. 常数 d. 算符和界符
2. 在状态转换图的实现中，____ 一般对应一个循环语句 a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是
3. 从左线性文法构造有限自动机时，通常自动机状态个数比文法非终结符号数多____个。 (a)4 (b)2 (c)0 (d)1
4. 正规表达式(ε|a|b)2表示的集合是 _____。 (a){ε，ab，ba，aa，bb} (b){ab，ba，aa，bb} (c){a，b，ab，aa，ba，bb} (d){ε，a，b，aa，bb，ab，ba}
5. 有限状态自动机可用五元组（VT，Q，δ，q0，Qf）
来描述，设有一有限状态自动机M的定义如下： VT={0， 1}，Q={q0， q1， q2}，Qf ={q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2 M所对应的状态转换图为____ 。
6. 有限状态自动机可用五元组（VT，Q，δ，q0，Qf） 来描述，设有一有限状态自动机M的定义如下： VT={0， 1}，Q={q0， q1， q2}，Qf= {q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2 M所能接受的语言可以用正则表达式表示为____。 ①(0|1)* ②00(0|1)* ③(0|1)*00 ④0(0|1)*0
7. 有限状态自动机可用五元组（VT，Q，δ，q0，Qf） 来描述，设有一有限状态自动机M的定义如下： VT={0， 1}，Q={q0， q1， q2}，Qf ={q2}，δ的定义为： δ（q0，0）=q1 δ（q1，0）=q2 δ（q2，1）=q2 δ（q2，0）=q2 M所能接受的语言为____。 ①由0和1所组成的符号串的集合 ②以0为头符号和尾符号、由0和1所组成的符号串的集合 ③以两个0结束的，由0和1所组成的符号串的集合 ④以两个0开始的，由0和1所组成的符号串的集合
8. 从接受语言的能力上来说，非确定型有穷自动机和________是等价的。 a. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.确定性有穷自动机； b. ⅰ.左线性正规文法；ⅱ.右线性正规文法；ⅲ.确定性有穷自动机； c. ⅰ.正规式；ⅱ.上下文无关文法；ⅲ.正规文法； d. ⅰ.正规式；ⅱ.确定性有穷自动机；ⅲ.下推自动机；
9. 下面四个选项中，关于编译过程中扫描器的任务的叙述，________是不正确的。 ①组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输 出；删除注释；删除空格和无用字符；行计数、列计数；发现并定位词法错误；建立符号表 。 ②按词法规则分割出单词，识别其属性，并转换成属性字的形式输出；发现并定位词法 错误；建立符号表；输出状态转换图。 ③组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输 出。 ④组织源程序的输入；按词法规则分割出单词，识别其属性，并转换成属性字的形式输 出；行计数、列计数；发现并定位词法错误；建立符号表；输出状态转换图。
10. ______不是NFA的成分。 A.有穷字母表 B.初始状态集合 C.终止状态集合 D.有限状态集合
11. 词法分析的常用方法有____。 A.有穷自动机理论 B.图灵机 Ｃ.图论 Ｄ.无穷自动机理论
12. 设有两个状态S和T，如果从S出发能读出某个字w而停于终态，那么从T出发也能读出同样
的字而停于终态；反之，果从T出发能读出某个字w而停于终态，那么从S出发也能读出同样的
字而停于终态。则我们称状态S和状态T是____。 A. 可区分的；B. 等价的；C. 多余的；D. 无用的。
13. 词法分析器的输出结果是____。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值
14. 编译过程中扫描器的任务包括______。
①组织源程序的输入
②按词法规则分割出单词，识别出其属性，并转换成属性字的形式输出 ⑧删除注解
④删除空格及无用字符 ⑤行计数、列计数 ⑥发现并定位词法错误 ⑦建立符号表
a．②③④⑦ b．②③④⑥⑦ c．①②③④⑥⑦ d．①②③④⑤⑥⑦
15. 下述正则表达式中______与(a*+b)*(c+d)等价(即有相同符号串集)。(x+y亦可写作x|y) ①a*(c+d)+b(c+d) ②a*(c+d)*+b(c+d)* ③a*(c+d)+b(c+d) ④(a+b)*c+(a+b)*d ⑤(a*+b)*c+(a*+b)*d a.①③ b. ③④⑤ c.③ d.④⑤
16. 正则式的“*”读作______。 a，并且 L或者 c．连接 d．闭包
17. 在状态转换图中，结点代表____，用圆圈表示。 a.输入缓冲区 b.向前搜索 c.状态 d.字符串
18. 与(a|b)*(a|b)等价的正规式是____。(第4章) A. a*| b* B. (ab)*(a|b)* C. (a|b)(a|b)* D. (a|b)*
19. 无符号常数的识别和拼数工作通常都在____ 阶段完成。 Ａ．词法分析 Ｂ．语法分析 Ｃ．语义分析 Ｄ．代码生成 解答: 1. 2. 3. 4. 5. 6. 7. 8.