计算理论期末练习题(2015)

复习重点1、集合序列元组函数关系图串：字母表中符号的有穷序列语言:是字符串的集合2、DFA、NFA、NFA到DFA的转换，DFA、NFA的形式化五元组表达3、正则表达式、正则表达式和NFA之间的转换、利用泵引理证明不是正则语言4、上下文无关文法下推自动机乔姆斯基范式（基本概念）CFG到下推自动机的转换从右至左压入栈中5、利用泵引理证明不是上下文无关语言6、图灵机、图灵可识别语言：接受、拒绝、循环判定器：对所有输入都停机的图灵机，永不循环。图灵可判定语言：能让图灵机停机的语言，接受或者拒绝要求可以做简单的判定性证明（例如：ADFA、ACFG、HALT-TM、ETM）7、可归约性。要求可以利用规约，完成简单的定理证明。计算理论练习题1、画出识别下述语言的DFA状态图，其中，字母表为{0,1}。1）{w|w从1开始且以0结束}；2）{w|w含有至少3个1}；3）{w|w含有子串0101}；q1的0自循环处考虑004）{w|w的长度不小于3，并且第3个符号为0}；5）{w|w从0开始且长度为奇数}；6）{w|w是除11和111以外的任何字符}；7）{w|w不含子串110}；2、写出下述语言的正则表达式。1）{w|w不含子串110}；(0∪10)*1*2）{w|w的长度不超过5}；ε∪∑∪∑∑∪∑∑∑∪∑∑∑∑∪∑∑∑∑∑3）{w|w是除11和111外的任意串}；ε∪0∑*∪10∑*∪110∑*∪111∑∑*包含11或111的串仍属于题设4）{w|w的奇数位均为1}；(1Σ)*(1)前一个括号为串长为偶数，加后一个则奇偶都可以5）{w|w含有至少2个0，并且至多含1个1}。0*(00010001100)0*确保两个0一定在，并且最多1个1，不能在外面，即有可能为空3、利用泵引理证明下述语言不是正则的。1）A1={0n1n2n|n0};证明：假设A1是正则的。设p是泵引理给出的关于A1的泵长度。令S=0p1p2p,∵S是A1的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含0，xyyz中，0比1、2多，xyyz不是A1的成员。违反泵引理的条件1，矛盾。∴A1不是正则的。2）A2={|w{a,b}*};证明：假设A2是正则的。设p是泵引理给出的关于A2的泵长度。令S=apbapbapb,∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含a，所以xyyz中第一个a的个数将比后两个a的个数多，故xyyz不是A2的成员。违反泵引理的条件1，矛盾。∴A2不是正则的。4、给出产生下述语言的上下文无关文法。1）{w|w至少包含3个1}；S→A1A1A1AA→0A|1A|ε2）{w|w以相同的符号开始和结束}；S→0A0|1A1A→3）{w|w的长度为奇数}。S→0A|1AA→B→0A|1A5、利用泵引理证明下述语言不是上下文无关的。1）{w#t|w,t{a,b}*,且w是t的子串}；假设该语言上下文无关，设p为泵长度，取S=0p1p#0p1p,由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。现在假设#ϵx，则必存在不全为0的i,j，使得vy=1i0j，下面分两种情况考虑：②j≠0,则uxz=0p1p-i#0p-j1p不在该语言中②j=0,则uv2xy2z中#左侧的字符串长度大于右边，不在该语言中。0p1p-i1i#0j0p-j1p=uvxyz;0p1p-i12i#02j0p-j1p=uv2xy2z;2）{t1#t2##tk|k2,ti{a,b}*,且存在ij是的ti=tj}。假设该语言上下文无关，设p为泵长度，取S=apbp#apbp,由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。于是vxy跨越#两侧.此时，S经抽取成uxz后，具有apbi#ajbp的形式，其中，i,j不全为p。(亦可为apbp-i#ap-jbp，只是符号的不同，传达的意思都是p-i不等于p-j，是因为i与j是相等的)因此，uxz不在该语言中。综上该语言不是上下文无关的。6、给出识别语言（01001010）*的NFA，将该NFA转化为等价的DFA。7、已知DFAG如下图所示,写出CONVERT(G)的结果，要求步骤8、把下述正则表达式转换成非确定型自动机（NFA）。a)(0∪1)*000(0∪1)*b)(((00)*(11))∪01)*9、已知CFGG，如下：E→E＋T|TT→T×E|FF→（E）|a给出下述字符串的语法分析树和派生。a.ab.a+ac.a+a+ad.((a))10、在下列每个输入串上，给出M所进入的格局序列：a.0b.00c.000d.000000