形式语言与自动机试卷

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 的转移图。

一、用递归定义给出下列语言的有限描述（每题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分）。

形式语言与自动机试题
判断
(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.。

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可以作为终态。

形式语⾔及⾃动机哈尔滨⼯业⼤学（中⽂版）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?。

形式语言与自动机理论试题一、按要求完成下列填空1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4'）(1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}}(2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}}2.设∑={0,1},请给出∑上的下列语言的文法 （2x5'）(1)所有包含子串01011的串 S →X01011YX →ε|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时，进入陷阱状态）1S110,10 (2) {x|x ∈{0，1}+且x 的第十个字符为1}（设置一个陷阱状态，一旦发现x 的第十个字符为0，进入陷阱状态）1S0,10,10,10,10,110,0,10,10,10,10,1二、判断（正确的写T ，错误的写F ） 5x2'1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则3231321)(R R R R R R R ⊆( T )任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x ∈。

)),(),((321R y z R R z x z ∈∧∈∃⇒ },,,,{e d c b a z ∈ )),(),(),((321R y z R z x R z x z ∈∧∈∧∈∃⇒)),(),(()),(),((3231R y z R z x z R y z R z x z ∈∧∈∃∧∈∧∈∃⇒ 3231),(),(R R y x R R y x ∈∧∈⇒ 3231),(R R R R y x ∈⇒2.对于任一非空集合A ，Φ⊆A2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言2型语言1型语言0型语言 ( T )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分）。

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∑=为字母表中０个字符组成的。

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∑=为字母表中０个字符组成的。