西理工编译原理试题集1-7(7)

2. 已知字母表? = {a， b}上语言L = {w | w中a的个数是偶数}。 （１）给出该语言的正规式 （２）画出接收该语言的NFA （３）把该NFA转换成等价的DFA （４）对该DFA进行状态最小化 2解法1：

（１） 语言L的正规式是：

(a b*a | b)* 或 b*(a b*a b*)*

（２）画出接收该语言的NFA

? ? ? 1 2 ? 3 a 4 ? b 13 ? 14 ? 5 ? 6 ? ? b 7 ? 8 ? 9 a 10 ? 11 ? 12 （3）NFA转换成DFA I {1，2，3，12，13} Ia ————Ib ————S a B A B C {4}={4，5，6，8，9} {14}＝{2，3，11，12，13，14} {4，5，6，8，9} ————{10}＝{2，3，10，11，12，————{7}＝{6，7，8，9} B D E 13} {2，3，11，12，13，14} ————{4}={4，5，6，8，9} ————{14}＝{2，3，11，12，13，C B C 14} {2，3，10，11，12，13} ————{4}={4，5，6，8，9} ————{14}＝{2，3，11，12，13，D B C 14} {6，7，8，9} ————{10}＝{2，3，10，11，12，————{7}＝{6，7，8，9} E D E 13} 得到的DFA为： A b a a b B a a a D b E C b b

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

?＝{I(1)，I(2)}＝{{ B，E }，{A，C，D }}

∵{ B，E }a＝{D}，落入I(2)中；{ B，E }b＝{E}；落入I(1)中； ∴I(1)＝{ B，E }不必再分。

∵I(2)}＝{A，C，D }a＝{B}，落入I(1)中；I(2)}＝{A，C，D }b＝{C}，落入I(2)中； ∴I(2)}＝{A，C，D }不必再分。

故，得到的接受该语言的最简DFA是：

b start a A a B

b 解法2

（２）画出接收该语言的NFA

? b a 1 2 b ? a 3

（3）NFA转换成DFA

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

b start a A a B

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

（４）对该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结束的所有符号串的集合。

（１）写出定义该语言的正则表达式。 （２）画出接收该语言的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， （１）该正则表达式所定义的语言是什么？