形式语言与自动机理论试题答案解析

形式语言与自动机理论试题答案解析

一、按要求完成下列填空

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}

0,1 （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）

S0,10,10,10,10,10,10,10,10,110,1

二、判断（正确的写T，错误的写F） 5x2'

1.设R1和R2是集合{a,b,c,d,e}上的二元关系，则

(RR)RRRRR1231323 ( 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 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={0n1n0n|n>=1}。假设L是RL，则它满足泵引理。不妨设N是泵引理所指的仅依赖于 L的正整数，取Z=0N1N0N 显然，Z∈L 。

按照泵引理所述，必存在u，v，w。由于|uv|<=N,并且|v|>=1，所以v只可能是由0组成的非空串。不妨设v=0k，k>=1 此时有u=0Nkj ，w=0j1N0N 从而有uviw=0Nkj(0k)i0j1N0N 当i=2时，有uv2w=0Nk1N0N 又因为k>=1, 所以 N+k>N 这就是说0Nk1N0N不属于L， 这与泵引理矛盾。所以，L不是RL。

五、构造等价于下图所示DFA的正则表达式。(12分) q0 1 q1 S

0 1 0 1 1

q2 0 q0

3

答案(之一)：(

01+(1+00)((1+00*1)0)*((1+00*1)1)

(+(1+00)((1+00*1)0)*00*)

预处理： 

1 q1

 q0 X 0 Y

1 0 1 1  q2 0 0 q3 去掉q3：  1 1  q0 q X 0 Y

1 0 1+00*1 00* q2

 去掉q1：  q0 X 01

Y

1+00 (1+00*1)1 00* (1+00*1)0 q2 )*

+(1+00)((1+00*1)0)*00*

去掉q2：

去掉q0：

X  q0 Y

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

六、设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

0q00001000 00q0001000 000q001000 0000q010000

00001q10000

000010q100

0000100q10

00001000q1

00001000Bq2

处理输入串10000的过程中经历的ID变化序列如下： q010000 1q100000 10q1000 100q100 1000q10 10000q1

10000Bq2

七、根据给定的NFA，构造与之等价的DFA。（14分） NFA M的状态转移函数如下表

Y

状态说明 状态 0 输入字符 1 {q0,q2} 2 {q0,q2} {q2} {q2,q1} { q0} 开始状态 q0 q1 q2 q3 {q0,q1} {q3,q0}  {q3,q2} {q3,q1} {q3 } 终止状态 解答：

状态说明 状态 输入字符 0 开始状态 1 [q0,q2] [q0,q2] [q0,q1,q2,q3] [q0,q1,q2,q3] [q0, q2,q3] [q0,q1,q2,q3] 2 [q0,q2] [q0,q2] [q0,q1,q2] [q0,q1,q2] [q0,q2] [q0,q1, q2] q0 [q0,q1] [q0,q2] [q0,q1,q2] [q0,q1,q3] [q0,q2,q3] [q0,q1] [q0,q1,q3] [q0,q1] [q0,q1,q3] [q0,q1,q2,q3] [q0,q1,q2,q3] 终止状态 终止状态 终止状态 [q0,q1,q2,q3] [q0,q1,q2,q3] [q0,q1,q2,q3] [q0,q1, q2] q0[q0,q1]001,201,22[q0,q1,q3][q0,q2,q3]12[q0,q1,q2]210,1[q0,q1,q2,q3]2

00,1[q0,q2]