首页>电子书>其他>形式语言与自动机理论课后答案

形式语言与自动机理论课后答案

ca1a03  在  2021-01-08 07:13:03  上传  731.39 KB
形式语言与自动机理论(第3版) 蒋宗礼 姜守旭 编著 清华大学出版社。
课后1 、2、3、4章答案,可以打印
2(1){x0≤x≤100Hx∈}
(2){r|∈{a,y
且|k<4
(3){B|Bc{l,2,3,4}}
(4){L|Lc{a,b}*}
(5){x|x=2n-1,n∈M}
(6){(4,b)|a+b=10且a,b∈[4,9}
(7){xx∈{0,l},且计0的个数是1的个数的两倍}
(8)tr∈{01,且中1的个数是10}
(9){x|x∈{0,l},且中倒数第十个字符为1}
(10∈Ax∈,101,/∈11,∑=10)
13给出下列集合的幂集。(02282075冯蕊)
2){中}
3){①,{}
(4){E,0,00}
解答
(1){Φ}
(2){①,{}
(3){Φ,{Φ},{},{,{}
(4){Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{e,0,00}
(5){①,{0},{1},{0,1}
14列出集合{0,1,2,3,4}中
(褚颖娜02282072)
(1)所有基数为3的子集
{0,1,2},{0,1,3},{0,1,4},{0,2,3,},{0,2,4}
2,4},{1,3,4},{0,3,4},{2,3,4}
(2)所有基数不大于3的子集
0},{1},{2},{3},{4},{3,4},{2,4},{2,3},{1,4},{1,3},{0,
4},{0,3},{0,2},{1,2},{0,1},{0,1,2},{0,1,3}
{0,1,4},{0,2,3,},{0,2,4},{1,2,3},{1,2,4},{1,3,4},{0,
3,4},{2,3,4}
15解答:
1、3、8、10、11、12、16正确
学霸助手[xuebazhushou.com-课后答案期末试卷复习提纲

16证明下列各题囗
(02282081刘秋雯)
1)A=B,iffA是B的子集且B是A的子集
证明
充分条件
A=B
则由集合相等的定义知
对于仟何x∈A,有x∈B
∴A为B的子集
同理,B为A的」集
必要条件
A为B的子集
对于仟何x∈A,都有x∈B
又∵B为A的子集
,对」任何ⅹ∈B有,x∈A
由集合相等的定义知,A=B
2)如果A为B的子集,则|A|(=|B
证明:
A为B的子集,则对于任何xCA
有x∈B
∴存在一个集合C使B-AUC且A∩C为空集
则B|A+C
C|〉=0
3)如果A为B的真子集,则|A〈=|B
证明:
(1)当A为有穷集合时,因为A为B的真子集,且则对于任何xCA
有x∈B
且存在∈B的x,此x不∈A
∴在个非空集合C,使B=AUC且A∩C为空集
则B|AH+C|且C>=1
A(
(2)当A为无穷集合,因为A为B的真子集,则B一定也为无穷集合,|A|∞,B
∴A=B
综合(1),(2)所述,|AK=B
4)如果A是有穷集且A为B的真子集则|A|(|B
证明
见上题证明(1)
5)如果A为B的子集,则对于任何x∈A,有x∈B
证明
若A为B的子集,则由子集定义可知,对于任何x∈A,有x∈B
6)如果A是B的真子集,则对于任何x∈A,有x∈B,并且存在x∈B,但ⅹ不
学霸助手[xuebazhushou.com-课后答案期末试卷复习提纲

∈A
证明:
由真子集的定义可证
7)如果A为B的子集,B为C的子集,则A为C的子集
证明
A为B的子集,B为C的子集
则对于任何x∈A,则x都∈B
且,又对于任何y∈B,则y∈C,∴对」任何x∈A,x∈C
∴A为C的子集
8)如果A为B的真子集,B为C的真子集,则A为G的真子集
证明:
A为B的真子集,B为C的真子集
则对于任何x∈A,则x都∈B
且,存在x∈B但次x不∈A
又对于仁何y∈B,则y∈C,存在y∈C但此y不∈B,
∴对」任何x∈A,x∈C,存在x∈Cx不∈A
∴A为C的真子集
9)如果A为B的子集,B为C的真子集,则A为C的真子集
证明
因为A为B的子集,B为C的真子集
则对」任何x∈A,x都∈B,且ⅹ都∈C
又对于任何y∈B,则y∈C,存在y∈C但此y不∈B,则y不∈A
∴对于任何x∈A,x∈C,存在x∈C.x不∈A
A为C的真子集
10)如果A为B的真子集,B为C的子集,则A为G的真子集
让明:
A为B的真子集,B为C的子集
对于任何ⅹ∈A,则x都∈B
且存在ⅹ∈B但次x不∈A,
又对于任何y∈B,则y∈C
∴对于任何x∈A,x∈C,存在x∈C.x不∈A
∴A为C的真子集
1)如果A=B,则|A|=|B
证明:
A=B,则A与B所含元素相同
AB
12)如果A为B的子集,B为C的真子集,或如果A为B的真子集,B为C的子
集,则A为C的真子集
证明:证明见9,10
1.7A={1,2345,6}B={1,3,5}C={2,4“6}U={0,1,2,3,452678,9}
学霸助手[xuebazhushou.com-课后答案期末试卷复习提纲

{1,35}=B
(2(4c
{1,35}({2,4,6}
={1,2,3,4,56}=A
((4∩(-O
1350.13.5,89}
{0,13,5,7,8,9}=C
(4)A-B-C
{2,4,6}-{2,4,6}
(5)A×B×C×d
∵A×Φ=①
(列)扎(A
4350.9089
={0,1,3,5,7,8,9}=
(7).A×BxAC
Ax{(a,b)(a∈B,b∈C或(∈B,b∈C或(a∈B,b∈O)}
(a,b,()(4∈A,b∈B,c∈O或(a∈A,b∈B,C∈O或(a∈Ab∈BC∈O}
(叭C

{1,2,3,4,5,6}
学霸助手[xuebazhushou.com-课后答案期末试卷复习提纲

1.8对论域U上的集合A、B、C,证明以下结论成立。(02282047吴贤珺)
(1)A∪B=B∪A
证:对仟意的x,
∈A∪B
X∈Ax∈B
今X∈Bx∈A
◇→X∈B∪A
故 AUBCE∪A且B∪AcA∪B
则AUB=BUA
(2)(A∪B)∪C=A∪(B∪C)
证:对任意的x
∈(A∪B)∪C
今X∈(AJB)Vx∈C
→(x∈A∨x∈B)∨xCC
兮x∈Ayx∈BVx∈C
∈AV(x∈BVx∈C
冷→X∈Avx∈(B∪C)
今→x∈A∪(B∪C)
故(AUB) UC CAU(B∪C)且A∪(B∪C)c(A∪B)∪C
则(A∪B)∪C=A∪(B∪C)
(3)AUB=A iffBca
证:①由BcA∪B及A∪B=A知BcA
②由BA知x∈B,x∈A
则对任意的x,
∈AJB
→x∈A∨x∈B
→x∈A
故A∪BCA,又 ACAUB,所以AUB=A。
综合①②得到AUB= A iffbca。
(4)A×(B∪C)=(A×B)∪(AuC)
证:对任意的有序对(a,b)
(a,b)∈A×(BUC)
→a∈A∧b∈(B∪C)
→a∈A∧(b∈Bvb∈C)
台(a∈A∧b∈B)∨(a∈A入b∈C)
兮(a,b)∈A×B(a,b)∈A×C
(a,b)∈(A×B)∪(AxC)
故A×(B∪C)c(A×B)U(A∪C)且(A×B)∪(A∪C)cAX(B∪C
则A×(B∪C=(A×B)J(A∪C)
(5)(B∩C)×A=(B×A)∩(C×A)
学霸助手[xuebazhushou.com-课后答案期末试卷复习提纲

证:对任意的有序对(b,a),
(b,a)∈(B∩C)×A
>b∈(B∩C)Aa∈A
→(b∈B∧b∈C)∧a∈A
(b∈B∧a∈A)∧(b∈C∧a∈A)
兮(b,a)∈B×A∧(b,a)∈C×A
(b,a)∈(B×A)∩(CxA)
故(BC)XAc(BXA)∩(CXA)且(B×A)n(CXA)c(B∩C)×A
则(B∩C)xA-(B×A)∩C×A)。
6)A×(B一C)-(A×B)-(A×C
证:对任意的有序对(a,b),
(a,b)∈A×(B—C)
a∈A∧b∈(B一C)
台a∈A∧(bCB∧bC)
(a∈A∧b∈B)∧(a∈A∧b还C)
分(a,b)∈A×B∧(a,b)FA×C
冷冷(a,b)∈(AxB)-(AC)
故A×(B∪C)二(AXB)U(A∪C)且(A×B)∪(A∪C)A×(B∪C
则Ax(B∪C)=(AXB)J(AUC)。
需要说明的是:对于(a,b)∈A×B∧(a,b)A×C
∈Ab∈B)∧(a∈A∧bgC
本来,由(a,b)≠AXC只能得到(a≠ AveC)。但是(a,b)∈AXB,故a∈A,
这样,必须bC
7)如果AcB,则24c
证:对任意的C,C∈24→CcA
由于ACB,故CcB,则C∈2B,从而2Ac2B。
∩2
证:对仟意的C,
C∈2
CcA∩B
CcA∧CcB
C∈2A∧C∈2B
台C∈2^∩2R
则20c2A∩2B且2^∩2c2h,故22=24∩2B。
(9)|A∪B|≤|A|+|B
证:由容斥原理,|AUB|=|A|+|B|-|A∩B
学霸助手[xuebazhushou.com-课后答案期末试卷复习提纲

)当A∩B时,AUB|<|A|+|B
②当A∩B=时,|AUB|=|A|+|B
由①②知|AUB|≤|A|+|B|。
(10)(B-C)×A=(B×A)-(C×A)
证:对任意的有序对(b,a)
(b,a)∈(B-C)×A
>b∈(B-C)∧a∈A
(b∈B∧bgC)∧a∈A
>(b∈B∧a∈A)∧(bgC∧aCA)
令(b,a)∈B×A∧(b,a)C×A
(b,a)∈(B×A)(C×A)
故(B-C)×Ac(BXA)(C×A)且(B×A)(C×A)c(B-C)XA
则(B-C)XA-(B×A)-(C×A)。
需要说明的是:对于(b,a)∈BXA∧(b,a)∈CXA
→(b∈B∧a∈A)A(b还C∧a∈A)
本来,由(b,a)gCXA只能得到(a≠A∨b终C)。但是(b,a)∈B×A,故a∈A,
这样,必须bC。
(11)如果AB,则BcA
证:对任意的x,x∈B→xgB
由于AcB,故x≠A,即x∈。因此,BcA
(12)B=A分A∪B=U且A∩B=中
证:①由B=A以及A的定义知,A∪B=A∪A=U,A∩B=A∩A=Φ。
②由A∩B=中知,对任意的x∈B,xA,即x∈B,x∈A,故BA。
又由A∪B=U知,对任意的x∈A,xgA,则x∈B,故AcB。
这样,B
综合①②得,B=A分→A∪B=U且A∩B=d
(13)A⌒B=A∪B
证:对任意的ⅹ,
x∈AAB
兮Xg(A∩B)
学霸助手[xuebazhushou.com-课后答案期末试卷复习提纲

EAVXB
◇>x∈Ax∈b
∈(4UB
则团∩ BCA B且AUBc团B
故A∩B=UB
(14)小B=A∩B
证:对任意的x
∈AB
g(A∪B)
分XgA∧XgB
兮ⅹ∈4∧x∈
∈(A∩B)
则A∪BcA∩B且A∩B
故∪丿B=A∩B
9解答
(6)R={(a,a)、(b,b),(c,c)(d,d).(e,),(a,b),(bc)(a,c)}
(9)R={(a,a)2(bb),(c,c)d,d)e,e),(a,b),(b,c)、a,c),ba),(c,b)、(c,a)}
110设R1和R2是集合{a2b,c,d,e}上的二元关系,其中,
RI(a,b),c, d),(b, d),(b, b), (d, e), R2((a, a), (b, c),d, c),(e, d), (c,a))
求:RR2R2R13R1R2RR2
解答:
R1R2={(a,c),(cc)(b,c,d,d)}
R2R1={(a,b),b,d),d,d),(e,e),(c,b)}
R1={(ab),(c,d)bd)(b,b),(de)、a,d),(a,e)、be),(c,e)}
R2={(aa)b,c),(d,c),(c,d)(c,a)(b,a)d,a)(c,c),(c,a)}
R1'=R1∪{(a,a)、(b,b),c,c,d,d,e,e)}
R2=R2+∪{(aa),(b,b),(c,c),dd),e,e)}
9
学霸助手[xuebazhushou.com-课后答案期末试卷复习提纲
我要下载
意见反馈 联系客服 返回顶部

登录注册找回密码

Vaptcha启动中...

Vaptcha启动中...

充值账单订单冲正

*扫码按套餐金额一次性付款立即点击“确认”按钮

*充值提示成功,请重新登录账户生效

*充值问题联系Q或邮箱最迟24小时内答复

*充值问题先尝试【订单冲正】自助解决

*无法解决Q421644184或Q邮箱,支付宝订单平台账号

*推荐用chrome浏览器访问本站,禁用360浏览器

啥都没有哦

*输入正确支付宝订单号,2021开头的,点“确认”按钮

*有疑问请及时联系Q 421644184或此Q对应的邮箱

*提供支付宝支付订单号截图及平台用户名

*推荐用chrome浏览器访问本站,禁用360浏览器

在线咨询 x
如果您有任何疑问
点击咨询