编译原理试题集78677 下载本文

9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19.

四.名词解释 1. 状态转换图;

2. 正规式(正规表达式、正则表达式)的形式化定义;

3. 给出确定性有限状态自动机的形式化定义;

4. 给出非确定性有限状态自动机的形式化定义;

5. DFA状态最小化。

解答: 1. 2. 3. 4. 5.

五.简答题

1. 写出标识符(以字母打头,由字母和数字组成的符号串)的正则表达式。

2. 词法分析器对程序语言的单词符号一般如何分类?

3. 人运狼、羊、菜过河,一次运一件,不让羊吃掉菜,也不让狼吃掉羊,画出渡河的状态 转换图。可否将其抽象为一个有限自动机?

4. C语言无符号实数用正则表达式怎么定义?

5. 分析下面各正规表达式所表示的语言。 (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

6. 何谓扫描器?扫描器的功能是什么?

7. 试简述有穷状态自动机与正则表达式的等价性概念。

解答: 1. 2. 3. 4. 5. 6. 7.

六.应用题

1. 有一个语言,它接收Σ={0,1}上所有满足如下条件的字符串:每个1都有0直接跟在右边 。 (1)给出该语言的正规式 (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

2. 已知字母表? = {a, b}上语言L = {w | w中a的个数是偶数}。 (1)给出该语言的正规式 (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

3. 有一个语言,它接收Σ={0,1}上的含奇数个1的所有串。 (1)给出该语言的正规式 (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化 提示:正则表达式为0*1 (0|10*1)*。

4. 已知Σ={0,1}上正则表达式为0(0|1)*0, (1)该正则表达式所定义的语言是什么? (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

5. 已知Σ={0,1}上正则表达式为(0|1)*0(0|1)(0|1), (1)该正则表达式所定义的语言是什么? (2)画出接收该语言的NFA

(3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

6. 已知Σ={0,1}上正则表达式为0*10*10*10*, (1)该正则表达式所定义的语言是什么? (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

7. 有一个语言,它接收Σ={a,b}上所有满足如下条件的字符串:不含子串abb的由a和b组

成的符号串的全体。 (1)给出该语言的正规式 (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

8. 已知Σ={0,1}上正则表达式为((ε|0)1*)*, (1)该正则表达式所定义的语言是什么? (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

9. 已知Σ={0,1}上正则表达式为(a*|b*)*, (1)该正则表达式所定义的语言是什么? (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

10. 已知语言为Σ={a,b}上的、由a和b组成的但是不以bb结束的所有符号串的集合。 (1)写出定义该语言的正则表达式。 (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

11. 已知Σ={a,b}上正则表达式为(aa|b)*(a|bb)*, (1)该正则表达式所定义的语言是什么? (2)画出接收该语言的NFA

(3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

12. 已知语言为Σ={0,1}上所有由0和1组成的二进制数串的集合,这些串从数值上可以看作

是4的倍数。 (1)写出定义该语言的正则表达式。 (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

13. 已知语言为Σ={0,1}上所有由0和1组成的二进制串的集合,这些串都是以0打头以0结尾 的。 (1)写出定义该语言的正则表达式。 (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

14. 已知Σ={0,1}上正则表达式为1(0|1)*101, (1)该正则表达式所定义的语言是什么? (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化

15. 已知Σ={a,b}上正则表达式为(a|b)*abb(a|b)*, (1)该正则表达式所定义的语言是什么? (2)画出接收该语言的NFA (3)把该NFA转换成等价的DFA (4)对该DFA进行状态最小化 解答: 1. 2. 3. 4. 5. 6. 7. 8.