形式语言与自动机理论蒋宗礼第一章参考答案

1/26考答案你知道的各种颜色。解：{红，橙，黄，绿，青，蓝，紫}⑵大学教师中的各种职称。解：{助教，讲师，副教授，教授}程。解：{语文，数学，英语，物理，化学，生物，历史，地理，政治}，母亲，妹妹，我}⑸你知道的所有交通工具。解：{汽车，火车，飞机，轮船，马车}⑺集合{1,2,3,4}的幂集。解：{Φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}}数。⑼0~100的所有正整数。合的集合。故A={{10},{1,9},{2,8},{3,7},{4,6},{1,2,7},{1,3,6},{1,4,5},{2,3,5},{1,2,3,4}}1.2请用命题法给出下列集合2/26()VxA,x[1,10],i[1,|A|],|xiiii=1(1)Φ(2){Φ}(3){Φ,{Φ}}(5){0,1}解答:(1){Φ}(2){Φ,{Φ}}(3){Φ,{Φ},{{Φ}},{Φ,{Φ}}}(5){Φ,{0},{1},{0,1}}2)(1)所有基数为3的子集，(2)所有基数不大于3的子集4}，{3，4}，{2，4}，{2，3}，{1，4}，{1，3}，{0，3/26(02282081刘秋雯)则由集合相等的定义知(1)当A为有穷集合时，因为A为B的真子集，且则对于任何x∈AAABB穷集合，|A|＝∞，|B|综合(1)，(2)所述，|A|<=|B|见上题证明(1)4/26由真子集的定义可证(1).AnB5/26={1,3,5}=B(2).(AnB)UC(3).(AnB)U(UC) ={2,4,6}–{2,4,6}A×=(6).(AnB)UAUCUA C=AnAUC=AUC=A6/26⑴A∪B＝B∪Ax∈A∪B一x∈Ax∈B一x∈Bx∈A一x∈B∪A则A∪B＝B∪A。⑵(A∪B)∪C＝A∪(B∪C)x∈(A∪B)∪CxABxCxAxBxCx∈Ax∈(B∪C)一x∈A∪(B∪C)故(A∪B)∪CA∪(B∪C)且A∪(B∪C)(A∪B)∪C则(A∪B)∪C＝A∪(B∪C)。⑶A∪B＝AiffBA②由BA知Vx∈B,x∈Ax∈A∪Bx∈Ax∈B故A∪BA，又AA∪B，所以A∪B＝A。综合①②得到A∪B＝AiffBA。⑷A×(B∪C)＝(A×B)∪(A∪C)故A×(B∪C)(A×B)∪(A∪C)且(A×B)∪(A∪C)A×(B∪C)则A×(B∪C)＝(A×B)∪(A∪C)。⑸(B∩C)×A＝(B×A)∩(C×A)7/26证：对任意的有序对(b,a)，A故(B∩C)×A(B×A)∩(C×A)且(B×A)∩(C×A)(B∩C)×A则(B∩C)×A＝(B×A)∩(C×A)。⑹A×(B－C)＝(A×B)－(A×C)故A×(B∪C)(A×B)∪(A∪C)且(A×B)∪(A∪C)A×(B∪C)则A×(B∪C)＝(A×B)∪(A∪C)。8/26(10)(B－C)×A＝(B×A)－(C×A)证：对任意的有序对(b,a)，故(B－C)×A(B×A)－(C×A)且(B×A)－(C×A)(B－C)×A则(B－C)×A＝(B×A)－(C×A)。 BxBBAABUABΦ②由A∩B＝Φ知，对任意的x∈B，xA，即Vx∈B，x∈A，故BA。 x∈AB一x∈Ax∈Bx∈AB一x∈A^x∈B解答:9/2610/2612(1)RRRR。1221证明：用反证法，假设RR=RR。1221212211221所以RRRR。1221(2)(RR)R=R(RR)。123123证明：任取(x.,y),其中x,y={a,b,c,d,e}，使得(x,y)=(RR)R123123123123123123所以得证(RR)R=R(RR)。123123(3)(RUR)R=RRURR。1231323xyxyabcd,e}，使得(x,y)=(RR)R。1232311/2612313231323一(x,y)=RRURR1323所以得证(RUR)R=RRURR1231323(4)R(RUR)=RRURR。3123132证明：任取(x.,y),其中x,y={a,b,c,d,e}，使得(x,y)=R(RR)。31231231231323132一(x,y)=RRURR3132所以得证R(RUR)=RRURR。3123132(5)(RnR)RRRnRR。1231323yRnRR123de1231233231323(x,y)=RRnRR1323所以得证(RnR)RRRnRR。1231323(6)R(RnR)RRnRR。312313212/26231231231323132(x,y)=RRnRR3132所以得证R(RUR)=RRnRR。3123132数集的等价类(02282075冯蕊)1.14.在什么样的假设下，人与人之间的“同乡关系”是等价关系。当“同乡关(吴玉涵)(1)对于Vx=*13/26(2)如果对于任给的x,y=*，如果xRLy，故对于Vz=*，xz=R与yz=L同时成立或同时不成立，L综上，该关系的等价性和右不变性均得以证明。RL的等价类.xRLy(1)Vx,y={0n1m|n≥0,m>0},都有Vz=Σ*,均有xz=L与yz=L同时成立或者同(2)Vx,y={0n1m|n≥0,m=0},都有Vz=Σ*,均有xz=L与yz=L同时成立或者同(3)Vx,y茫{0n1m|n,m≥0},都有Vz=Σ*,均有xz=L与yz=L同时成立或者同时14/26.....1.19.给出下列对象的递归定义(02282072褚颖娜)gRn在无向图G中，若两顶点v1,v2之间存在一条无向边，则v1,v2是G的一条长位1的路为G的一条长度为k的路在有向图G中，若两顶点v1,v2之间存在一条有向边，则v1,v2是G的一条长位1的路为G的一条长度为k的路若x为单字符，则x的倒序是它本身nnnn1233nnnn1233根根=()kkkkkkkk(122334(1)11当nk时，nnnn34===n()由归纳原理，对任一={0}都成立()假设nk时成立，即=k15/2616/26vE=v=vknkvknkvE=v=vknkvknk()设，是有穷集合，则从到的映射有A个。()假设时成立，即从到的映射有A=mk个(V1E0(V1E0deg(v)2E0)设Em，假设Vn1时成立，即deg(v)2E2m当Vn1时，设VV'{v},V'{v},deg(v)'2m0个结点相连，则增加边数，deg()，对于个结点增加00E====v=v(==(=====v)由归纳原理，为)由归纳原理，17/26v=v=v=v= 0vv=0000vv= v=v=()高度为时，最多有=2个叶子，成立()假设高度为时成立，即最多有叶子个当高度为时，第层上最多有结点个，则第层上最多有叶子为()由归纳原理，高度为的二元树最多含有个叶子()假设，m时成立，即aa=a+p+1个个p个个个个()由归纳原理，aam=an+m成立。18/26)假设时成立，即的前缀有+1=n+1个。(1){1,2}。解答：字母表为(1)(2)(6)aaaaabbbba}⑵后缀:{ε,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba,aaaaabbbba}⑶真前缀:{ε,a,aa,aaa,aaaa,aaaaa,aaaaab,aaaaabb,aaaaabbb,aaaaabbbb}⑷真后缀:{ε,a,ba,bba,bbba,bbbba,abbbba,aabbbba,aaabbbba,aaaabbbba}集合可以有：19/26(段季芬)这是学科本身决定的。计算机科学与技术学科所要解决的根本问题是什么能被有效的自动化。现代计算机技术认为，要想有效的实现自动化，经过抽象进行形式化。解答：字母表是非空有穷集合，由字母表中的元素连接而成的字符串叫做字母表上的句子。假设字母表为空集，则字母表中唯一的元素就是c,而c不论如何组合，其组成的句子都为空，其研究就失去了意义，所以字母表要具有非空性。们将语言看做句子的集合,句子看做字母按照一定规则组成的字符串,故主要根据规则的形式区分语言类,大部分问题都可转化为判定某个句子是否属于某个语言的问题.而这就要求从一个句子的结构出发,而一个整体的句子在结构上将其划成几个部分,对于我们的研究会有很大的帮助.事实上研究句子的前缀,后缀,也就是为了将句子结构进行有意识的划分而更加方便的研究句子,看其是否符合某个形式语言的组成规则.1234520/26、1、0。其中，每6解：该语言的每一个句子从前向后看和从后向前看时，有一部分是对称相等的。而且，这对称相等的两个串中间一定有另外一个串。7解：该语言的特点是在其句子中一定可以找到这样的一个串：该串是从句子的第一个字符开始的连续的串，且紧跟该串之后的连续一段字符串恰好是该串从后往前看是的那个串，而且这样的两个串之后一定还有另外一个字符串。8解：该语言的每一个句子有这样的特点：该句子的第一个字符和最后一个字符都是09(刘钰02282083)12341234(1)LUL=LUL设Va=LUL,a=L或a=La=L或a=LVa=LUL,故原式得证12122121(2)LU(LUL)=(LUL)UL3设Va=LU(LUL)a=L或a=L或a=LVa=LU(LUL)12312321/26故，原式得证(3)(L*)*=L*11如果L=,(L*)*==L*111如果L，假设L={a,a...a},n1,1112nnn112n11121n故(L*)*=L*，原式得证11(4)(L+)+=L+11如果L=,(L+)+==L+11如果L，假设L={a,a...a},n1,1112nLaaaaaaaaaL{a,a...a,aa,aa...aa...}112n11121n112n11121n故(L+)+=L+，原式得证(5)(LL)L=L(LL)123123(LL)L={xy|xL,yL}L={xyz|xL,yL,zL}=123123123{x|xL}{yz|yL,zL}=L(LL)123123故，原式得证(6)L(LUL)=LLULL1213L(LUL)={x|xL}{y|yL或yL}={xy|xL,yL或xL,yL}12131213故，原式得证22/26(7)(LUL)L=LLULL1(LUL)L={x|xL或xL}{y|yL}={xy|xL,yL或xL,yL}21312131故，原式得证(8)(LUL)*=(L*L*)*2121设Va(LUL)*,假设a=xx...x,则{x,x,...x}LUL2112n12n21则xL或xLk2k1k2k1又因为cL*，cL*L*L*L*,L*L*L*1112212xkL1*L2*,因此a=x1x2...xnL1*L2*(L2UL1)*(L2*L1*)*同理可证(LUL)*(L*L*)*121综上(LUL)*=(L*L*)*2121故，原式得证(9)(LU{c})*=L*1当{c}L时，原式显然成立1当{c}亿L时，设L={x,x...x},1112n因为cx=xc=x(LU{c})*={c,x,x...x}*={c,x,x...x,xx,xx...xx...}112n12n11121nx所以(LU{c})*=L*1故，原式得证23/26(10)*={}故，原式得证(11)(LULULUL)*=(L*L*L*L*)*1244设Va(LULULUL)*,假设a=xx...x,则{x,x,...x}LULULUL213412n12n2134则xL或xL,或xL,或xL，因此k2k1k3k4xL*或xL*,xL*或xL*，当k=1,2,nk2k1k3k4L*,L*,L*,L*L*L*L*L*L*,L*L*L*L*L*又因为21341123421234L*L*L*L*L*,L*L*L*L*L*3123441234LLLLk234...n12341234