好文档 - 专业文书写作范文服务资料分享网站

形式语言与自动机理论试题

天下 分享 时间: 加入收藏 我要投稿 点赞

形式语言与自动机理论试题

一、按要求完成下列填空

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

(R?R)R?RR?RR1231323

2 ( T ) 2.对于任一非空集合A,Φ? 3.文法G:S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言

2型语言

1型语言

0型语言 ( T )

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|aSBC aB?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是泵引理所指的仅依赖于 L的正整数,取Z=010 显然,Z∈L 。

按照泵引理所述,必存在u,v,w。由于|uv|<=N,并且|v|>=1,所以v只可能是由0组成的非空串。不妨设v=0,k>=1 此时有u=0uvw=0iN?k?jnnnNNNkN?k?j ,w=010 从而有

jNN(0k)i0j1N0N 当i=2时,有uv2w=0N?k1N0N 又因为k>=1,

N?kN所以 N+k>N 这就是说010N不属于L,

这与泵引理矛盾。所以,L不是RL。

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

1 q0 q1 S

0 1 0 1 1 答案(之一):( 01+(1+00)((1+00*1)0)*((1+00*1)1) )* (0 ?+(1+00)((1+00*1)0)*00*)

q2 0 q3

预处理:

X

去掉q3:

X

去掉q1:

? ? q0 0 1 0 1 1 ? 0 ? q3 1 q1 Y

q2 0 ? q0 0 1 0 1 q1 Y

1+00*1 00* q2 ? ? 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,{2}),其中δ的定义如下: δ(0,0)=(q0,0,R) δ(q0,1)=(q1,1,R) δ(q1,0)=(q1,0,R) δ(1,B)=(q2,B,R)

请根据此定义,给出M处理字符串00001000,10000的过程中ID的变化。(10分) 解:处理输入串00001000的过程中经历的ID变化序列如下:

qqqq000001000

0q00001000 000010q100

00q0001000 0000100q10

000q001000 00001000q1

0000q010000 00001000Bq2

00001q10000

处理输入串10000的过程中经历的ID变化序列如下:

q010000

1q100000 10q1000 100q100 1000q10 10000q1

10000Bq2

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

形式语言与自动机理论试题

形式语言与自动机理论试题一、按要求完成下列填空1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集(2x4')(1){Φ,{Φ},{{Φ}},{Φ,{Φ}}}(2){Φ,{ε},{0},{00},{ε,0},{ε,00},{0,
推荐度:
点击下载文档文档为doc格式
7rytq4yuhf5136q5shpe
领取福利

微信扫码领取福利

微信扫码分享