资源描述：
《第四章课外训练答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1写出能被5整除的十进制整数的文法及正规表达式。正规文法：左线性文法为：S->A0
2、A5
3、0
4、5A->A0
5、A1
6、A2
7、A3
8、A4
9、A5
10、A6
11、A7
12、A8
13、A9
14、1
15、2
16、3
17、4
18、5
19、6
20、7
21、8
22、9正规表达式为：(1
23、2
24、3
25、4
26、5
27、6
28、7
29、8
30、9)(0
31、1
32、2
33、3
34、4
35、5
36、6
37、7
38、8
39、9)*(0
40、5)
41、(0
42、5)2写一个文法，使其语言是奇数集，且每个奇数不以0开头。S->ABC
43、CC->1
44、3
45、5
46、7
47、9A->C
48、2
49、4
50、6
51、8B->0
52、A
53、ε3：已知有限自动机如图(1)以上状态转换图表示的语言有什么特征？符号串含有连续的两个1(2)写出其正规式与正规文法.正
54、规式为：（0
55、1）*11（0
56、1）*(3)构造识别该语言的确定有限自动机DFA.确定化为：01{A}q0{A}{A,B}{A,B}q1{A}{A,B,C}{A,B,C}q2{A,C}{A,B,C}{A,C}q3{A,C}{A,B,C}终态有：q2,q3状态转换图为：略4请构造与正规式R=(a*b)*ba(a
57、b)*等价的状态最少的DFA（确定有限自动机）根据正规式所构造的NFA为：4bbaa,b3211aε确定化ab{1}q0{1}{1,2}{1,2}q1{1}{1,2,3}{1,2,3}q2{1,4}{1,2,3}{1,4}q3{1,4}{1,2,4}{1,
58、2,4}q4{1,4}{1,2,3,4}{1,2,3,4}q5{1,4}{1,2,3,4}其中q3,q4,q5是终态最小化：将状态划分为终态集和非终态集{q0.q1.q2}{q3，q4,q5}输入af(q0,a)=q0∈{q0,q1,q2}f(q1，a）=q0∈{q0,q1,q2}f(q2,a)=q3∈{q3,q4,q5}q2与q0,q1输入a到达的状态属于不同集合,，所以进一步划分为：{q0,q1}{q2}f(q0,b)=q1∈{q0,q1}f(q1，b）=q2∈{q2},q0,q1输入b到达的状态属于不同集合,进一步划分为：{q0}{q1}f(q3,a)=
59、q2∈{q2}f(q4,a)=q2∈{q2}f(q5,a)=q2∈{q2}输入a到达的状态属于相同集合；f(q3,b)=q4∈{q3,q4,q5}f(q4,b)=q5∈{q3,q4,q5}f(q5,b)=q5∈{q3,q4,q5}输入b到达的状态属于相同集合；q3,q4,q5是等价状态最终划分为：{q0}{q1}{q2}{q3.q4,q5}最小化的状态转换矩阵为：abq0q0q1q1q0q2q2q3q2q3q3q3q3是终态状态转换图略5．设字符集∑={a,b},请写出不以a开头的但以aa结尾的字符串集合的正规表达式，并构造与之等价的状态最少的DFA。正规式为
60、：b(a
61、b)*aa根据正规式所构造的NFA为：xybaa21a,b确定化ab{x}q0Φ{1}{1}q1{1,2}{1}{1,2}q2{1,2,y}{1}{1,2,y}q3{1,2,y}{1}状态q3是终态最小化：将状态划分为终态集和非终态集{q0.q1.q2}{q3}输入af(q0,a)=Φf(q1，a）=q2∈{q1,q2,q0}f(q2,a)=q3∈{q3}输入a到达的状态属于不同集合，所以进一步划分为：{q0}{q1}{q2}{q3}即abq0Φq1q1q2q1q2q3q1q3q3q1q0是初态，q3是终态状态转换图略
