形式语言与自动机理论试题
一、按要求完成下列填空
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.
构造识别下列语言的DFA 2x6'
(1) {x|x?{0，1}+且x以0开头以1结尾}
（设置陷阱状态，当第一个字符为1时，进入陷阱状态）
00110,10S1
(2) {x|x?{0，1}+且x的第十个字符为1}
（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）
0,1S0,10,10,10,10,10,10,10,10,110,1
二、判断（正确的写T，错误的写F） 5x2'
1.设R1和R2是集合{a,b,c,d,e}上的二元关系，则( T )
任取(x.,y),其中x,y?{a,b,c,d,e}，使得(x,y)?(R1?R2)R3。 ??z((x,z)?R1?R2?(z,y)?R3) z?{a,b,c,d,e} ??z((x,z)?R1?(x,z)?R2?(z,y)?R3)
??z((x,z)?R1?(z,y)?R3)??z((x,z)?R2?(z,y)?R3) ?(x,y)?R1R3?(x,y)?R2R3 ?(x,y)?R1R3?R2R3
2.对于任一非空集合A，Φ?2 ( T ) 3.文法G：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言
2型语言
1型语言
0型语言 ( F )
A(R?R)R?RR?RR1231323
?? 5.s（rs+s）*r=rr*s（rr*s）* ( 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)*r? rr*s(rr*s)*,结论不成立
三、设文法G的产生式集如下，试给出句子aaabbbccc的至少两个不同的推导（12分）。 S?aBC|aSBCaB?ab
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
四、判断语言{0n1n0n|n>=1}是否为RL，如果是，请构造出它的有穷描述(FA,RG或者RL）；如果不是，请证明你的结论（12分）
解：设L={010|n>=1}。假设L是RL，则它满足泵引理。不妨设N是泵引理所指的仅
nnn依赖于 L的正整数，取Z=0N1N0N 显然，Z∈L 。
按照泵引理所述，必存在u，v，w。由于|uv|<=N,并且|v|>=1，所以v只可能是由0组成的非空串。不妨设v=0，k>=1 此时有u=0kN?k?j ，w=010jNN 从而有
uviw=0N?k?j(0)010 当i=2时，有uvw=0kijNN2N?k10 又因为k>=1,
NN所以 N+k>N 这就是说0N?k10不属于L，
NN 这与泵引理矛盾。所以，L不是RL。
五、构造等价于下图所示DFA的正则表达式。(12分)
q0 S 1 q1 1 1 0 1 0 答案(之一)：( 01+(1+00)((1+00*1)0)*((1+00*1)1) )* (0 ?+(1+00)((1+00*1)0)*00*)
q2 0 q3
预处理：
去掉q3：
去掉q1：
? ? q0 0 1 0 1 1 ? 0 ? q3 q1 Y
1+00*1 00* q2 1 q1 Y
X q2 0 X ? q0 0 1 0 1 ? ? q0 X 01 Y
(1+00*1)1 00* 1+00 (1+00*1)0 q2
去掉q2：
去掉q0：
?+(1+00)((1+00*1)0)*00*
? q0 Y
X 01+(1+00)((1+00*1)0)*((1+00*1)1)
(01+(1+00)((1+00*1)0)*((1+00*1)1))* (?+(1+00)((1+00*1)0)*00*)
X Y
六、设M=（{q0,q1,q2}，{0,1}，{0,1，B}，{δ}，q0,B,{q2}）,其中δ的定义如下： δ（q0，0）=（q0，0，R） δ（q0，1）=（q1，1，R） δ（q1，0）=（q1，0，R） δ（q1，B）=（q2，B，R）
请根据此定义，给出M处理字符串00001000,10000的过程中ID的变化。（10分） 解：处理输入串00001000的过程中经历的ID变化序列如下： q000001000
00001q10000
0q00001000 000010q100
00q0001000 0000100q10
000q001000 00001000q1
0000q010000 00001000Bq2
处理输入串10000的过程中经历的ID变化序列如下： q010000 10000Bq2
七、根据给定的NFA，构造与之等价的DFA。（14分） NFA M的状态转移函数如下表
1q100000
10q1000
100q100
1000q10
10000q1