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直接跟在右边 。 （１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
2. 已知字母表? = {a， b}上语言L = {w | w中a的个数是偶数}。 （１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
3. 有一个语言，它接收Σ={0，1}上的含奇数个1的所有串。 （１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：正则表达式为0*1 (0|10*1)*。
4. 已知Σ={0，1}上正则表达式为0(0|1)*0， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
5. 已知Σ={0，1}上正则表达式为(0|1)*0(0|1)(0|1)， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA
（３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
6. 已知Σ={0，1}上正则表达式为0*10*10*10*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
7. 有一个语言，它接收Σ={a，b}上所有满足如下条件的字符串：不含子串abb的由a和b组
成的符号串的全体。 （１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
8. 已知Σ={0，1}上正则表达式为((ε|0)1*)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
9. 已知Σ={0，1}上正则表达式为(a*|b*)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
10. 已知语言为Σ={a，b}上的、由a和b组成的但是不以bb结束的所有符号串的集合。 （１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
11. 已知Σ={a，b}上正则表达式为(aa|b)*(a|bb)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA
（３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
12. 已知语言为Σ={0，1}上所有由0和1组成的二进制数串的集合，这些串从数值上可以看作
是4的倍数。 （１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
13. 已知语言为Σ={0，1}上所有由0和1组成的二进制串的集合，这些串都是以0打头以0结尾 的。 （１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
14. 已知Σ={0，1}上正则表达式为1(0|1)*101， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化
15. 已知Σ={a，b}上正则表达式为(a|b)*abb(a|b)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 解答: 1. 2. 3. 4. 5. 6. 7. 8.