编译原理作业集-第三章-修订版

编译原理作业集 第三章 词法分析

I Ia Ib S {1，3} ————{2}={2} ————{3}＝{1，3} A {2} ————{3}＝{1，3} ————{2}={2} B 得到的DFA如下：

b b start a A a B

（４）对该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进行状态最小化

提示：(1) 以0开头并且以0结尾的，由0和1组成的符号串。

5已知Σ={0，1}上正则表达式为(0|1)*0(0|1)(0|1)， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM

a B B A A B - 16 -

编译原理作业集 第三章 词法分析

（４）对该DFA进行状态最小化

提示：(1) 由0和1组成的符号串，且从右边开始数第3位为0。

6已知Σ={0，1}上正则表达式为0*10*10*10*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA

（４）对该DFA进行状态最小化

提示：(1) 含3个1的由0和1组成的符号串。 {α|α∈{0，1}+，且α中含有3个1 }。

7有一个语言，它接收Σ={a，b}上所有满足如下条件的字符串：不含子串abb的由a和b组成的符号串的全体。 （１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：正则表达式为：b*(a*|(ba)*)*。

8 已知Σ={0，1}上正则表达式为((ε|0)1*)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：(1)由0和1组成的符号串。

9已知Σ={0，1}上正则表达式为(a*|b*)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：(1)所有由a和b组成的符号串。

10. 已知语言为Σ={a，b}上的、由a和b组成的但是不以bb结束的所有符号串的集合。

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM

- 17 -

编译原理作业集 第三章 词法分析

（１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA

（４）对该DFA进行状态最小化

提示：(1) (a|b)*a(a|b|ε)。All the strings of a’s and b’s that end with a, ab or aa. Or： All the strings of a’s and b’s that do not end with bb.。

11已知Σ={a，b}上正则表达式为(aa|b)*(a|bb)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA

（４）对该DFA进行状态最小化 提示：（1）All the strings of a’s and b’s that can be divided into two substings, where in the left substring, the even number of consecutive a’s are separated by b’s while in the right substring, the even number of consecutive b’ are separated by a’s.

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

（１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：(0|1)*00。

13已知语言为Σ={0，1}上所有由0和1组成的二进制串的集合，这些串都是以0打头以0结尾的。

（１）写出定义该语言的正则表达式。 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 提示：0(0|1)*0。

14. 已知Σ={0，1}上正则表达式为1(0|1)*101， （１）该正则表达式所定义的语言是什么？

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM

- 18 -

编译原理作业集 第三章 词法分析

（２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

15已知Σ={a，b}上正则表达式为(a|b)*abb(a|b)*， （１）该正则表达式所定义的语言是什么？ （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:21 AM - 19 -

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库编译原理作业集-第三章-修订版在线全文阅读。