形式语言与自动机理论试题答案解析.doc
《形式语言与自动机理论试题答案解析.doc》由会员分享，可在线阅读，更多相关《形式语言与自动机理论试题答案解析.doc（6页珍藏版）》请在冰点文库上搜索。
形式语言与自动机理论试题答案解析
一、按要求完成下列填空
1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4）
（1）{Φ,{Φ},{{Φ}},{Φ,{Φ}}}
（2）{Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}
2.设∑={0,1},请给出∑上的下列语言的文法（2x5）
（1）所有包含子串01011的串
S→X01011Y
X→ε|0X|1X
Y→ε|0Y|1Y
（2）所有既没有一对连续的0，也没有一对连续的1的串
A→ε|A’|A”
A’→0|01|01A’
A”→1|10|10A”
3.构造识别下列语言的DFA2x6
（1）{x|xÎ{0，1}+且x以0开头以1结尾}
（设置陷阱状态，当第一个字符为1时，进入陷阱状态）
（2）{x|xÎ{0，1}+且x的第十个字符为1}
（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）
二、判断（正确的写T，错误的写F）5x2
1.设和是集合{a,b,c,d,e}上的二元关系，则（T）
任取（x.,y）,其中x,y，使得。
2.对于任一非空集合A，Φ（T）
3.文法G：
SA|ASAa|b|c|d|e|f|g是RG（F）
4.3型语言2型语言1型语言0型语言（F）
5.s（rs+s）r=rrs（rrs）（F）
不成立，假设r,s分别是表示语言R，S的正则表达式，例如当R={0}，S={1},L（s（rs+s）*r）是以1开头的字符串，而L（rr*s（rr*s）*）是以0开头的字符串.L（s（rs+s）*r）L（rr*s（rr*s）*）
所以s（rs+s）*rrr*s（rr*s）*,结论不成立
三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导（12分）。
bB→bb
CB→BC
bC→bc
cC→cc
推导一：
S=>aSBC
=>aaSBCBC
=>aaaBCBCBC
=>aaabCBCBC
=>aaabBCCBC
=>aaabbCCBC
=>aaabbCBCC
=>aaabbBCCC
=>aaabbbCCC
=>aaabbbcCC
=>aaabbbccC
=>aaabbbccc
推导二：
S=>aSBC
=>aaSBCBC
=>aaaBCBCBC
=>aaaBBCCBC
=>aaaBBCBCC
=>aaabBCBCC
=>aaabbCBCC
=>aaabbBCCC
=>aaabbbCCC
=>aaabbbcCC
=>aaabbbccC
=>aaabbbccc
四、判断语言{|n>=1}是否为RL，如果是，请构造出它的有穷描述（FA,RG或者RL）；如果不是，请证明你的结论（12分）
解：
设L={|n>=1}。
假设L是RL，则它满足泵引理。
不妨设N是泵引理所指的仅依赖于L的正整数，取Z=显然，Z∈L。
按照泵引理所述，必存在u，v，w。
由于|uv|<=N,并且|v|>=1，所以v只可能是由0组成的非空串。
不妨设v=，k>=1此时有u=，w=从而有uvw=当i=2时，有uvw=又因为k>=1,
所以N+k>N这就是说不属于L，
这与泵引理矛盾。
所以，L不是RL。
五、构造等价于下图所示DFA的正则表达式。
（12分）
S
q1
q0
q2
q3
1
0
0
0
1
1
1
0
答案（之一）：
（01+（1+00）（（1+00*1）0）*（（1+00*1）1））*（e+（1+00）（（1+00*1）0）*00*）
q1
q0
q2
q3
1
0
0
0
1
1
1
0
e
e
X
Y
e
预处理：
去掉q3：
q1
q0
q2
1
0
1
1+00*1
0
e
X
Y
e
00*
去掉q1：
q0
q2
1+00
（1+00*1）0
e
X
Y
e
00*
（1+00*1）1
01
q0
e
X
Y
e+（1+00）（（1+00*1）0）*00*
01+（1+00）（（1+00*1）0）*（（1+00*1）1）
去掉q2：
去掉q0：
X
Y
（01+（1+00）（（1+00*1）0）*（（1+00*1）1））*（e+（1+00）（（1+00*1）0）*00*）
六、设M=（{}，{0,1}，{0,1，B}，{δ}，,B,{}）,其中δ的定义如下：
δ（，0）=（，0，R）
δ（，1）=（，1，R）
δ（，0）=（，0，R）
δ（，B）=（，B，R）
请根据此定义，给出M处理字符串00001000,10000的过程中ID的变化。
（10分）
解：
处理输入串00001000的过程中经历的ID变化序列如下：
00001000000010000000100000001000000010000
00001000000001000000010000000100000001000B
处理输入串10000的过程中经历的ID变化序列如下：
100001000001000010000100001000010000B
七、根据给定的NFA，构造与之等价的DFA。
（14分）
NFAM的状态转移函数如下表
状态说明
状态
输入字符
0
1
2
开始状态
q0
{q0,q1}
{q0,q2}
{q0,q2}
q1
{q3,q0}
{q2}
q2
{q3,q1}
{q2,q1}
终止状态
q3
{q3,q2}
{q3}
{q0}
解答：
状态说明
状态
输入字符
0
1
2
开始状态
q0
[q0,q1]
[q0,q2]
[q0,q2]
[q0,q1]
[q0,q1,q3]
[q0,q2]
[q0,q2]
[q0,q2]
[q0,q1]
[q0,q1,q2,q3]
[q0,q1,q2]
[q0,q1,q2]
[q0,q1,q3]
[q0,q1,q2,q3]
[q0,q1,q2]
终止状态
[q0,q1,q3]
[q0,q1,q2,q3]
[q0,q2,q3]
[q0,q2]
终止状态
[q0,q2,q3]
[q0,q1,q2,q3]
[q0,q1,q2,q3]
[q0,q1,q2]
终止状态
[q0,q1,q2,q3]
[q0,q1,q2,q3]
[q0,q1,q2,q3]
[q0,q1,q2]
升级会员 