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

《形式语言与自动机》期末测试题(规定时间：2小时)学号姓名1. (12 pts) 选择填空(多选)：(a)由正规表达式a*定义的语言: A,C (或只回答C)(b)语言{a m b m m _0} : B(c)语言{a m b m c m m _0} : D(d)语言{a m b n c m m,n _0} : B(e)对角化(diagonalization )语言L d:F(f)通用语言( universal )语言L u:E供选择的答案:A. 是某个有限状态自动机的语言；B. 是某个下推自动机的语言，但不是任何有限状态自动机的语言；C. 是某个有限状态自动机的语言，但不是任何空栈接受方式的确定下推自动机的语言;D. 是某个可停机的图灵机的语言，但不是任何下推自动机的语言；E. 是某个图灵机的语言，但不是任何可停机的图灵机的语言；F. 不是任何图灵机的语言.2. (7 pts)图灵机({ q 0, q i, q2, q3}, { 0,1 }, { 0,1,B }, :, q o, B, {q 3 })有如下转移规则:：(q o, 0)=(q i,1, R) (q i,1)=(q2, 0, L)■(q2, 1)=(q o, 1, R)、.(q1, B) = (q3, B, R )给出从初始IDq o O11O开始，该图灵机可以到达的完整的ID序列，直到它停机3. (12 pts)设有四个语言(或问题) A, B, C和D.这些语言可以是，也可以不是递归可枚举语言，但已知如下条件: (此题出得不好)i. A可以归约到B (不一定是多项式时间归约，下同)；ii. B可以归约到C ；iii. D可以归约到C ；对于以下6个命题，分别指出它们是“真”，或是“假”，或是“不能确定”：(a) A是递归可枚举的但不是递归的，而C是递归的.假(A不是递归的与C是递归的不可能同时成立)(b) B不是递归的，而D是递归可枚举的.不能确定(c) A的补不是递归可枚举的，而B的补是递归可枚举的.不能确定(d) B的补不是递归的，而C的补是递归的.假（e ） 如果A 是递归的，那么 B 的补是递归的•不能确定 （f ）如果C 是递归的，那么 D 的补是递归的•真4. （11 pts ）文法G 的产生式集合为： S_.AS b, A_.BB a b, B 「. BA a.下面的左图表示对于文法 G 和字符串ababb 应用CYK 算法时所构造的表，各集合与表元素符号之间的 对应关系可参照右边的图.试问（a ）计算X i5时与哪几对表元素相关？ （5 pts ） (b) X 15 = ？(5 pts) {S,A,B}(c) 是否有 ababb L(G)?(1 pt) Yes5. （8 pts ）对于正规语言和上下文无关语言两类语言，分别指出下列四个问题是否可判定 的：（a ） 给定该语言类中的任一语言 L ，判定L 是否为空？ 都可以（b ） 给定该语言类中的任一语言 L 和任何字符串 w ，判定w 是否属于L ？.都可以（c ） 给定该语言类中的语言 L 和M ，判定L 是否与 M 相等？.对正规语言可以，对上下文无关语言不可以对于递归语言和递归可枚举语言两类语言，分别指出上述问题（ b ）是否可判定的： 对递归语言可以，对递归可枚举语言不可以 6. （15 pts ）对下面描述每一对语言，指出以下 4种选择中的哪一个正确表达了它们之间的关系:（1）二（2）:语言 （ 1 ）是语言 （ 2）的真子集; （1） -： （2）:语言 （ 2）是语言 （ 1）的真子集； （1） =（ 2）:语言（1）和语言（2）相等；（1） ？（ 2）：语言（1）和语言（2）之间没有包含关系，即（1）中的某些串不在（2） 中，（2）中的某些串不在（1 ）中.（a ）（ 1）产生式集为 S >0S1 1S0 ；的CFG 的语言.（2）正规表达式 （0+1）*的语言.人5X 5{S,A,B } {S }X 4为5{A,B } {S }{S,B }X 3X 35{S,B }{S,B }{S }X 2 为3X 34 X 45 {A,B }{S,A }{A,B }{S,A }{S,A }X 1X> 2X 33X 44a b a b ba 1a 2a 3a 4a 5X 5 5(1)二(2) . (2) gen erates all stri ngs of 0's and 1's, while (1) does n't gen erate strings like 11, or any odd-length string.(b) (1)以终态方式接受的PDA ({ p , q }, { 0,1 } , { X,Z }，:, q, Z , { p })的语言，其中:.转移包括：、(q,0,Z)=(q,XZ), 、(q,0,X)=(q,XX), 、(q,1,X)=(p, ),、(p,1,X)=(p,；).(2)产生式集为S_；0S1 OS ；的CFG 的语言.(1)( 2). These almost look the same. (2) is the set of strings of the form 0n1 m such that 0 < m < n. However, the PDA of (1) cannot reach state p without reading at least one 0 and one 1, so it accepts the set of stri ngs of the form 0n1 m such that 1 _ m _ n .(c) ( 1)产生式集为S >AS SB ；, A》0和B >1的CFG 的语言.(2)正规表达式0*1*的语言.(1 ) =( 2)(d) (1)正规表达式(0+1)*11(0+1)* 的语言.(2)正规表达式(0*1*11)*0*110*1* 的语言.(1)_： ( 2) . (1) is all strings of 0's and 1's with two consecutive 1's. (2) missessome of these stri ngs, e.g., someth ing ending with 110101(e) (1) NFA ({ p , q }, { 0,1 } ,q, { q })的语言，其中转移函数 :.为：&q,0)={p }, 0q,1)=电5(p,0)={p,q}, S(p,1)={p}.(2)产生式集为S—.AS ；, A)0B和B)0B 1B 0的CFG 的语言.(1) = ( 2) . Both define the Ianguage of regular expression (0(0+1)*0)*.7. (10 pts)利用上下文无关语言的闭包运算可以证明某些语言是或不是上下文无关语言.试证明{a n b n+2 n _0}为上下文无关语言，而{a n b n'i c i d n'j e j i,j <n}不是上下文无关语言(提示，已知{0n1n n _0}为上下文无关语言，而{0n1n2n n 一0}不是上下文无关语言).前者可以用连接和同态运算；后者可以用同态运算。

a) 构造一个接受L(r) 的-NFA（Construct a -NFA that accepts L(r)）. (3 pts)b) 给出语言L(r) 的反向的一个正规表达式（Give a regular expression for the reversal of L(r)）. (3 pts)c) 构造可以生成语言 L(r) 的一个上下文无关文法（Construct a context-free grammar generating the language L(r)）.d)e)f) (6 pts)3. (6 pts) 下图是一个扩展的两个状态的有限自动机，其中 R，S，T，和 U 是正规表达式。

可以用不同的形式给出等价于该扩展自动机的正规表达式，试给出两种这样的正规表达式。

（Give two regular expressions which describe the following generic two-state finite automata in two different ways, where R, S, T, and U are regular expressions.）4. (6 pts) 正规表达式 a*b 表示 {a, b} 上的一个语言。

试构造接受该语言的补语言的一个 DFA。

（The regular expression a*b denotes a language on {a, b}. Construct a DFA that accepts the complement of this language.）5. (8 pts) 试给出下列每个正规语言的一个正规表达式（Give a regular expression for each of the following regular languages）：a) { xwxR x, w (a + b)+ }, where (a + b)+ = (a + b) (a + b)*b) { w w {a , b}* x, y( x, y {a , b}* w = xy | y | =3 y = yR ) }w : w 2 fa; bg6. (7 pts) 下面是图灵机 M 的转移图。

形式语言与自动机试题
判断
(1) 被图灵机接受的语言是递归语言【错、图灵机接受的语言递归可枚举语言，可识别的语
言是递归语言】
(2) 递归语言对补运算封闭【对、递归语言的补也是递归语言】
(3) 上下文无关语言对补运算封闭【错、CFL 在并、乘积、闭包运算下封闭，在代换下封闭，
在交、补运算下不封闭】
(4) RL 与CFL 的交是RL 【错、CFL 与RL 的交是CFL 】
(5) NP 问题是不可判定的【错】
(6) 非先天二义性语言都是可以被确定的PDA 接受【错】
(7) 存在能被一般图灵机接受的语言，但它不能被任何总是停机的图灵机接受【错】
(8) 不存在图灵机不能接受的语言【错、存在图灵机不能识别的语言】
(9) 两个CFL 的交肯定不是CFL 【错、CFL 在交运算下是不封闭的】
(10) 任意两个CFL 是否相同时不可判定的【对】
大题：
1、 已知{}*0,1,2L ⊆是所有三进制数中模3余2的符号串的集合。

构造一个DFA M 使L （M ）
=L 。

2、 证明{}{}*0,1T L ww w =∈不是RL
3、 构造一个确定的PDA M ，时(){}
n n 1a b 0L M n +=>
4、 证明L=(a i b j |j<i)不是CFL
5、 给定文法()G S S SaA A →： A cSd e →，将其改造成等价的乔姆斯基范式文法*G ，并利用CYK 算法判断cedae 是否是L(G[S])的句子。

6、 构造图灵机TM M ，M 只接受由0打头的二进制符号串w ，输出-w 的补码（求反后加1），
例如，输入w ：010011，则M 输出101101.。

一、用递归定义给出下列语言的有限描述（每题6分，共12分）1．字母表},,{c b a =∑上，以aa 结尾的所有符号串的集合。

2．字母表},,{c b a =∑上，每个a 至少有一个b 紧跟其后的所有符号串的集合。

二、文法和语言的转换（每题4分，共12分）。

1．已知语言}2,0,0,0|{>>≥>=s t n m e c c a b a L s t n m m n ，试构造相应的文法。

2．已知语言}0|{2i m n c b a L i m n ≤+≤=，试构造相应的文法。

3．已知语言}10,}1,0{{*的个数为偶数的个数为奇数中且，L ϖϖ∈=，试构造相应的文法。

三、已知上下文无关文法如下，试构造其chomsky 范式（12分）。

BabA AbAC ABa S ||→a Aa A |→A bC bBcB ||→ε||Ba Cb C →四、已知右线性文法][S G （每题4分，共12分）aA S →a bS aA A ||→(1) 构造FA(2) 确定化(3) 写出确定化后的自动机对应的正规式。

五、试用泵引理证明语言}|{k n m l d c b a L l k n m ++≠=不是正规语言（14分）。

六、构造如下文法相应的npda (14分)。

bBcA aAB aAbBB S ||→aBBc A →Ac cAb bBA B ||→七、分别给出有穷自动机)(FA 、下推自动机)(PDA 和图灵机)(TM 的物理模型，并指出它们的异同。

如有可能，给出它们相应的应用实例（12分）。

八、设计一个图灵机用于拷贝由b 构成的符号串。

确切地说，也就是构造一个机器能够执行计算ϖ0q ├ϖϖf q ，其中+∈}{b ϖ，0q 为初态，f q 为终态（12分）。

形式语⾔及⾃动机哈尔滨⼯业⼤学（中⽂版）4PDA与CFG的等价性4.1由CFG到PDA定理5.如果L是上下⽂⽆关语⾔,那么存在PDA P,使L=N(P).证明.构造PDA:设CFG G=(V,T,P′,S)且L(G)=L,构造PDAP=({q},T,V∪T,δ,q,S,?)其中δ定义:(1)对每个变元A:δ(q,ε,A)={(q,β)|A→β∈P′}(2)对每个终结符a:δ(q,a,a)={(q,ε)}那么P可以模拟G的最左派⽣,每个动作只根据栈顶的符号:如果是终结符则与输⼊串匹配,如果是⾮终结符⽤产⽣式来替换.充分性:要证明S??w=?(q,w,S)?*(q,ε,ε).那么任意w∈L(G),则存在最左派⽣S??lm w,并且除最后⼀步派⽣的w外,每次派⽣的最左句型都有xAα的形式,这⾥x∈T?,A∈V,α∈(V∪T)?.S=x1A1α1?lm x2A2α2?lm···?lm x n?1A n?1αn?1?lm x nαn=ww=x1y1=x2y2=···=x n?1y n?1=x n y n=w (q,w,S)=(q,y1,A1α1)?*(q,y2,A2α2)?*···?*(q,y n?1,A n?1αn?1)?*(q,y n,αn)=(q,ε,ε)当处于S??lmw的第i步时,若x i y i=w,有:x i A iαi??lm x i+1A i+1αi+1=?(q,y i,A iαi)?*(q,y i+1,A i+1αi+1)因为,当最左派⽣处于左句型x i A iαi时,ID为(q,y i,A iαi),如果有A i→β的产⽣式,则x i A iαi?lm x iβαi⽽x iβαi也是左句型,所以最左的变量即为A i+1,则A i+1之前x i之后的终结符记为x′,A i+1之后的记为αi+1,那么就有x i A iαi?lm x iβαi=x i x′A i+1αi+1那么由(1)P模拟A i→β的动作得到(q,y i,A iαi)?(q,y i,βαi)=(q,y i,x′A i+1αi+1)由(2)P会弹出x′,⽽y i会去掉与x′匹配的前缀,剩下的部分记为y i+1(即y i=x′y i+1),那么(q,y i,x′A i+1αi+1)?*(q,y i+1,A i+1αi+1)因此当S??lmw有(q,w,S)?*(q,ε,ε),即L(G)?N(P).必要性:要证明(q,w,S)?*(q,ε,ε)=?S??w.我们证明更⼀般的结论(q,x,A)?*(q,ε,ε)=?A??x.通过对ID转移的次数进⾏归纳证明.归纳基础:当仅需要1次时,只能是x=ε且A→ε为产⽣式.(因为即使x=a和产⽣式A→a,也需要2步才能清空栈:替换栈顶A为a,再弹出a.)所以A??ε成⽴.归纳递推:假设转移次数不⼤于n(n≥0)步时结论成⽴.当需要n+1步时,因为A是变元,其第1步转移⼀定是(q,x,A)?(q,x,Y1Y2···Y m)且A→Y1Y2···Y m是产⽣式,其中Y i是变元或终结符.⽽其余的n步转移(q,x,Y1Y2···Y m)?*(q,ε,ε)中,每个Y i不论是变元或终结符,从栈中被完全弹出时,都会消耗掉部分的x,记为x i,那么显然有x=x1x2···x m.⽽且为了清空每个Y i,需要的转移次数都不超过n,所以对i=1,2,···,m有(q,x i,Y i)?*(q,ε,ε)=?Y i??x i.再由A的产⽣式有Y1Y2···Y m??lm x1Y2···Y m??lm x1x2···Y m??lm x1x2···x m=x.A?lm因此(q,w,S)?*(q,ε,ε)=?S??w,即N(G)?L(G).⽰例为⽂法S→aAA,A→aS|bS|a构造PDA.构造PDA P=({q},{a,b},{a,b,A,S},δ,q,S,?),其中δ为δ(q,ε,S)={(q,aAA)}δ(q,a,a)={(q,ε)}δ(q,ε,A)={(q,aS),(q,bS),(q,a)}δ(q,b,b)={(q,ε)}.利⽤GNF的构造⽅法将⽂法转换为GNF格式的CFG G=(V,T,P′,S),那么PDA P的另⼀种构造⽅式为:P=({q},V,T,δ,q,S,?)为每个产⽣式,定义δ:δ(q,a,A)={(q,β)|A→aβ∈P′}.⽰例上例中的⽂法是GNF,构造PDA P′=({q},{a,b},{S,A},δ,q,S,?),其中δ为δ(q,a,S)={(q,AA)}δ(q,a,A)={(q,S),(q,ε)}δ(q,b,A)={(q,S)}.4.2由PDA到CFG定理6.如果PDA P,有L=N(P),那么L是上下⽂⽆关语⾔.证明.⽂法构造:设PDA P=(Q,Σ,Γ,δ,q0,Z0,?).那么构造CFG G=(V,T,P,S),其中V是形如[qXp]的对象和符号S的集合,其中p,q∈Q,X∈Γ,产⽣式集合P包括:(1)为Q中的每个p,构造⼀个产⽣式:S→[q0Z0p](2)如果δ(q,a,X)包括(p,Y1Y2···Y n),构造⼀组产⽣式:[qXr n]→a[pY1r1][r1Y2r2]···[r n?1Y n r n]这⾥a∈Σ∪{ε};X,Y i∈Γ;p,q∈Q;⽽r1,r2,···r n是Q中各种可能的n个状态;若i=0则构造产⽣式[qXp]→a.那么(q,w,X)?*(p,ε,ε)??[qXp]??w.充分性:ID序列(q,w,X)?*(p,ε,ε)表⽰栈弹出X⽽消耗了串w(状态从q到了p);⽽[qXp]??w 表⽰在P中经过栈符号X可以产⽣出w(状态从q到了p);设w=ax,a∈Σ∪{ε}.(1)我们要证明(q,w,X)?*(p,ε,ε)=?[qXp]??w(2)左边部分ID动作变化如果需多步完成,那么第1步时,⼀定有δ(q,a,X)包含(p,Y1Y2···Y n),(i)则第1步为(q,ax,X)?(p,x,Y1Y2···Y n)⽽其余步骤中,为弹出Y i会消耗x中的⼀部分x i,显然w=ax=ax1x2···x n;(ii)设弹出Y i之前和之后(弹出Y i+1之前)的状态分别是r i?1和r i,消耗的串是x i,这⾥i=1,2,···n且r0=p,那么其他步骤就是(r i?1,x i,Y i)?*(r i,ε,ε)(iii)⽽根据⽂法的构造规则,有[qXp]?a[pY1r1][r1Y2r2]···[r n?1Y n r n](iv)因此,只要i=1,2,···,n有(r i?1,x i,Y i)?*(r i,ε,ε)=?[r i?1Y i r i]??x i成⽴,就有[qXp]?a[pY1r1][r1Y2r2]···[r n?1Y n r n]??ax1x2···x n=w成⽴.(3)⽽左边部分ID动作变化如果仅需1步完成(或者说i=0时),由于(q,a,X)?(p,ε,ε),P只能消耗不超过⼀个的字符,即w=a(a∈Σ∪{ε}),且(p,ε)在δ(q,a,X),所以,由⽂法构造规则[qXp]→a,即(q,a,X)?(p,ε,ε)=?[qXp]?a因此(q,w,X)?*(p,ε,ε)=?[qXp]??w.必要性:略.⽰例将PDA P=({p,q},(0,1),{X,Z},δ,q,Z)转为CFG,其中δ如下:(1)δ(q,1,Z)={(q,XZ)}(4)δ(q,ε,Z)={(q,ε)}(2)δ(q,1,X)={(q,XX)}(5)δ(p,1,X)={(p,ε)}(3)δ(q,0,X)={(p,X)}(6)δ(p,0,Z)={(q,Z)}0S →[qZq ]S →[qZp ]消掉[qZp ],因与⾃⼰循环1[qZq ]→1[qXq ][qZq ][qZq ]→1[qXp ][pZq ][qZp ]→1[qXq ][qZp ]...[qZp ]→1[qXp ][pZp ]因⽣成step 2中的[qZp ]······5确定型下推⾃动机(DPDA)PDA P =(Q,Σ,Γ,δ,q 0,Z 0,F )是确定型下推⾃动机(DPDA ),当且仅当:(1)δ(q,a,X )⾄多有⼀个动作,这⾥a ∈Σ∪{ε};(2)如果δ(q,a,X )=?,那么δ(q,ε,X )=?.即?(q,a,Z )∈Q ×Σ×Γ,|δ(q,a,Z )|+|δ(q,ε,Z )|≤1.在任何情况下都不需要去选择可能的移动就是DPDA,以终态⽅式接受的语⾔也称为DCFL.虽然与PDA 不等价,但也有意义,例如语法分析器通常都是DPDA,DPDA 接受的语⾔是⾮固有歧义语⾔的真⼦集,Knuth 提出LR(k )⽂法的语⾔也恰好是DPDA 接受语⾔的⼀个⼦集,解析的时间复杂度为O (n ),LR(k )⽂法也是YACC 的基础.任何DPDA 都⽆法接受L wwr ,但是可以接受L wcwr ={wcw R|w ∈(0+1)?}.0,Z 0/0Z 01,0/101,Z 0/1Z 00,1/010,0,0/ε5.1RL 与DPDA定理7.如果语⾔L 是正则的,那么有DPDA P ,使L =L (P ).(注意是以终态⽅式接受.)DPDA P 可以不使⽤栈,⽽仅模拟DFA 即可.⼜因为L wcwr 显然是CFL,所以L (P )语⾔类真包含正则语⾔.5.2DPDA 与CFLDPDA P ⽆法识别L wwr .所以L (P )语⾔类真包含于上下⽂⽆关语⾔.5.3DPDA 与歧义⽂法定理8.如果有DPDA P ,语⾔L =L (P ),那么L 有⽆歧义的CFG.定理9.如果有DPDA P ,语⾔L =N (P ),那么L 有⽆歧义的CFG.证明略.DPDA也因此在语法分析中占重要地位.但是并⾮所有⾮固有歧义CFL都会被DPDA 识别.例如L wwr有⽆歧义⽂法S→0S0|1S1|ε.5.4语⾔间的关系a nb nc nww Rwcw Ra?b?。

2．1回答下面的问题： （周期律 02282067） （1）在文法中，终极符号和非终极符号各起什么作用？✓ 终结符号是一个文法所产生的语言中句子的中出现的字符，他决定了一个文法的产生语言中字符的范围。

✓ 非终结符号又叫做一个语法变量，它表示一个语法范畴，文法中每一个产生式的左部至少要还有一个非终结符号，（二，三型文法要求更严，只允许左部为一个非终结符号）他是推导或归约的核心。

（2）文法的语法范畴有什么意义？开始符号所对应的语法范畴有什么特殊意义？ ✓ 文法的非终结符号A 所对应的语法范畴代表着一个集合L （A ），此集合由文法产生式中关于A 的产生式推导实现的✓ 开始符号所对应的语法范畴则为文法G = {V ，T ，P ，S}所产生的语言L （G ）={w S T w w **|⇒∈且}（3）在文法中，除了的变量可以对应一个终极符号行的集合外，按照类似的对应方法，一个字符串也可以对应一个终极符号行集合，这个集合表达什么意义？✓ 字符串对应的终极符号行集合表示这个字符串所能推导到的终极字符串集合，为某个句型的语言。

（4）文法中的归约和推导有什么不同？✓ 推导：文法G = {V ，T ，P ，S}，如果,)(,,*T VP ∈∈→δγβα则称γαδ在G 中推导出了γβδ。

✓ 归约：文法G = {V ，T ，P ，S}，如果,)(,,*T VP ∈∈→δγβα则称γβδ在G 中归约到γαδ。

✓ 这他们的定义，我个人理解两个概念从不同角度看待文法中的产生式，推导是自上而下（从产生式的左边到右边），而归约是自下而上（从产生式的右边到左边），体现到具体实际中，如编译中语法分析时语法树的建立，递归下降，LL （1）等分析法采用自开始符号向下推导识别输入代码生成语法树，对应的LR （1），LALR 等分析法则是采用自输入代码（相当于文法中语言的句子）自底向上归约到开始符号建立语法树，各有优劣。

（5）为什么要求定义语言的字母表上的语言为一个非空有穷集合？ ✓ 非空：根据字母表幂的定义：εε,}{0∑=为字母表中０个字符组成的。

形式语言与自动机理论_哈尔滨工业大学中国大学mooc课后章节答案期末考试题库2023年1.令字母表【图片】, 则克林闭包【图片】中元素的长度为？参考答案:只能是有限的2.由字符0和1构成且含有奇数个1的DFA，至少需要几个状态？参考答案:23.双栈PDA可以接受任意图灵机接受的语言。

参考答案:正确4.由某字母表【图片】中的字符构成的全部正则表达式的集合，也可以看做是一个语言，则该语言为：参考答案:上下文无关语言5.由字符0和1构成且含有奇数个1和偶数个0的DFA，至少需要几个状态？参考答案:46.字符串的长度可以是任意的，那么也可以是无穷长的。

参考答案:错误7.设【图片】和【图片】是字母表【图片】上的任意语言且【图片】是无穷的，则两个语言的连接【图片】一定是无穷的。

参考答案:错误8.每一个有穷的语言都是正则语言。

参考答案:正确9.任何正则语言都是上下文无关语言。

参考答案:正确10.任意有穷集合的克林闭包一定是无穷集合。

参考答案:错误11.递归可枚举语言是可判定的语言。

参考答案:错误12.任何有限的语言都是上下文无关语言。

参考答案:正确13.NFA处于某个状态q且输入某字符a时，如果状态转移函数未定义，则NFA会：参考答案:停止自动机的运行，并拒绝该串。

14.有穷自动机有了空转移（不消耗输入串的状态跳转）, 改变了它识别语言的能力。

参考答案:错误15.对同一个语言，可能存在两个不同的有穷自动机识别。

参考答案:正确16.带有空转移的非确定有穷自动机中，对于某一个状态，是否可以同时存在“对某字符a的非确定性”和“空转移”？参考答案:可以。

17.图灵机是算法的好模型。

参考答案:错误18.确定的图灵机与非确定的图灵机等价。

参考答案:正确19.由字符0和1构成且含有偶数个1的DFA，至少需要几个状态？参考答案:220.如果一个语言是不可判定的，那么它的补也一定是不可判定的参考答案:错误21.确定的有穷自动机中，“确定的”含义是：参考答案:状态转移是确定的22.由字符0和1构成且长度为偶数的全部字符串的DFA，至少需要几个状态？参考答案:223.集合的克林闭包与正比包一定不相等参考答案:错误24.设【图片】是字母表【图片】上的任意语言，则语言【图片】的闭包【图片】一定是无穷的。

形式语言与自动机期末复习题及答案（一）1.有图灵机 M=(Q, ∑, Γ, δ,q 0 , B , F) 接受语言{w t w│w ∈{a, b}*}，按照下图说明其接受过程。

（本题15分 ）[q 1[q 6,B]答：abtab 的分析过程：[q 1,B]abtab├a [q 2,a]btab├ab [q 2,a]tab├abt [q 3,a]ab├ ab [q 4,B]tab├a [q 5,B]btab├[q 6,B]abtab├a [q 1,B]btab ├ab [q 2,b]tab├abt [q 3,b]ab ├abta [q 3,b]b ├abt [q 4,B]ab├a [q 5,B]btab ├ab [q 7,B]tab ├abt [q 8,B]ab├abta [q 8,B]b ├abtab [q 8,B]B├abta [q 9,B]b 接受abtab√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√√2.简述《形式语言与自动机》课程的主要内容。

(本题10分)答：语言的文法描述；RL （RG 、FA 、RE 、RL 的性质 ）；CFL （CFG(CNF 、GNF)、PDA 、CFL 的性质）；TM （基本TM 、构造技术、TM 的修改）；CSL （CSG 、LBA ）。

3.简述《形式语言与自动机》课程的学习目的和基本要求。

(本题10分) 答：本专业人员4种基本的专业能力：计算思维能力、算法的设计与分析能力、程序设计和实现能力、计算机软硬件系统的认知、分析、设计与应用能力。

其中计算思维能力包括：逻辑思维能力和抽象思维能力、构造模型对问题进行形式化描述、理解和处理形式模型。

本课程应使学生掌握如下知识：正则语言、下文无关语言的文法、识别模型及其基本性质、图灵机的基本知识。

锻炼培养如下能力：形式化描述和抽象思维能力、了解和初步掌握“问题、形式化描述、自动化（计算机化）”这一最典型的计算机问题求解思路。

1.写出表示下列语言的正则表达式。

（吴贤珺02282047）⑴{0, 1}*。

解：所求正则表达式为：(0+1)*。

⑵{0, 1}+。

解：所求正则表达式为：(0+1)+。

⑶{ x│x∈{0,1}+ 且x中不含形如00的子串 }。

解：根据第三章构造的FA，可得所求正则表达式为：1*(01+)*(01+0+1)。

⑷{ x│x∈{0,1}*且x中不含形如00的子串 }。

解：根据上题的结果，可得所求正则表达式为：ε+1*(01+)*(01+0+1)。

⑸{ x│x∈{0,1}+ 且x中含形如10110的子串 }。

解：所求正则表达式为：(0+1)*10110(0+1)*。

⑹ { x│x∈{0,1}+ 且x中不含形如10110的子串 }。

解：根据第三章的习题，接受x的FA为：要求该FA对应的正则表达式，分别以q0、q1、q2、q3、q4为终结状态考虑：q为终态时的正则表达式：(0*(11*0(10)*(ε+111*11*0(10)*)0)*)*q为终态时的正则表达式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)*1q为终态时的正则表达式：0*11*0((10)*(111*11*0)*(00*11*0)*)*2q为终态时的正则表达式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)*3q为终态时的正则表达式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)*4将以上5个正则表达式用“+”号相连，就得到所要求的正则表达式。

⑺ { x│x∈{0,1}+ 且当把x看成二进制数时，x模5与3同余和x为0时，│x│=1且x≠0时，x的首字符为1}。

解：先画出状态转移图，设置5个状态q0、q1、q2、q3、q4，分别表示除5的余数是0、1、2、3、4的情形。

另外，设置一个开始状态q.由于要求x模5和3同余，而3模5余3,故只有q3可以作为终态。