《形式语言与自动机》(王柏、杨娟编著)课后习题答案

形式语言与自动机形式语言与自动机理论-蒋宗礼-第三章参考答案导读：就爱阅读网友为您分享以下“形式语言与自动机理论-蒋宗礼-第三章参考答案”的资讯，希望对您有所帮助，感谢您对的支持!因此我们只需要证明对任何的2NFA M1?(Q1,?,?1,F1,q0)，都存在FAM2?(Q2,?,?2,F2,q0)与之等价。

对于任何的2NFA M1?(Q1,?,?1,F1,q0)，构造FA M2?(Q2,?,?2,F2,q0)，按三个方式构造?2：1．如果q?Q1,a??,?1(q,a)?{p,R},则?2(q,a)?p；2．如果q?Q1,a??,?1(q,a)?{p,S},则如果??1(p,a)?{o,R}，则?2(q,a)?o；如果??1(p,a)?{o,S}，则重复第二步；如果??1(p,a)?{o,L}，则对于集合A = {r|b?Q1,?1(r,b)?(o,R)}，?2(q,a)?r,r?A。

3．如果q?Q1,a??,?1(q,a)?{p,L},则设集合 A = {r|b?Q1,?1(r,b)?(p,R)}，?2(q,a)?r,r?A*************************************************** ****************************28．证明定理3-8：Moore机与Mealy机等价（郭会02282015）证明：不妨设Moore机M1=(Q1,?,?,?1,?1,q01)，Mealy机M2=(Q2,?,?,?2,?2,q02)，则根据Moore机和Mealy机等价的定义知，必须证明：T1(x)??1(q0)T2(x),其中T1(x)和T2(x)分别表示M1和M2关于x的输出。

??Moore机M1,?Mealy机M2,使M2与M1等价（1）构造M2，?2??1,q02?q01,Q2?Q1?q?Q1?{q01},?1(q)?a,?q'?Q1且?b??,?1(q',b)=q,就构造?2（q',b）=a（2）证明?x??*，?1(q0)T2(x)?T1(x)不妨设x?x1x2……xn,则?i?N,(i?1,2……n)则M1的输出为:T1(x)??1(q0)?1(?1(q0,x1))……?1(?1((…?1(q0,x1)，x2)…)，xn)由题意可知?1(q0,x1)，?1(?1(q0,x1),x2)，…，?1(……?1 (?1(q0,x1),x2) xn) 均为Moore机中的状态，由（1）中的构造假设知，M2的输出为：T2(x)??2(q0,x1)?2(?2(q0,x1),x2)…?2(……?2(?2(q0,x1),x2) ? ?1(q0,x1)?1(?1(q0,x1),x2)…?1(……?1(?1(q0,x1),x2) xn) xn) ?T1(x)??1(q0)T2(x)??Mealy机M2,?Moore机M1,使M1与M2等价（1）构造M1，q01?q02Q1?Q2?{qij|??2(qi,a)?qj,其中qi,qj?Q2,a??}?1?{?|?(qi,a)?qij,?(qij,?)?qj其中?2(qi,a)?qj}?1?{?|?1(qi,a)?qij,?1(qij,?)?qj,?(qij)??2(qi,a) }（2）证明?x??*，T1(x)＝?1(q0)T2(x)不妨设x?x1x2……xn,则?i?N,(i?1,2……n)则M1的输出为:T2(x)??2(?2(q0,x1))……?2(?2((…?2(q0,x1)，x2)…)，xn) 由题意可知?2(q0,x1)，?2(?2(q0,x1),x2)，…，?2(……?2 (?2(q0,x1),x2) xn) 均为Mealy机中的状态，由（1）中的构造假设知，M1的输出为：T1(x)??1(q0)?1(?2(q0,x1))?1(?1(q0,x1),x2)…?1(……?1(?1(q 0,x1),x2) xn)??1(q0)?2(?2(q0,x1))……?2(?2((…?2(q0,x1)，x2)…)，xn) ?T1(x)??1(q0)T2(x)综上所述，Moore机与Mealy机等价第三章作业答案1．已知DFA M1与M2如图3－18所示。

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

形式语言与自动机形式语言与自动机（计算机网络班）第一章绪论 1. 幂集2. 字母表的性质3. 真前缀、真后缀、前缀、后缀4. 语言的形式化表示题目：填空题{Φ,{Φ}}的幂集是：{Φ,{Φ},{{Φ}},{Φ,{Φ}}} 判断题对于任何一个非空集合A, A ?2A 错误{a,d,f}?{a,b,c,…,z}是字母表正确ε一定是字符串的前缀或后缀，当字符串不为ε时，则ε一定是其真前缀或真后缀正确∑={aa,ab,bb,ba}，求字符串aaaaabbbba 的所有前缀的集合、后缀的集合、真前缀的集合、真后缀的集合。

解：由前缀、后缀、真前缀、真后缀的集合可以有：其前缀集合为：{ε,aa,aaaa,aaaaab,aaaaabbb,aaaaabbbba} 其真前缀集合为：{ε,aa,aaaa,aaaaab,aaaaabbb}其后缀集合为：{ε,ba,bbba,abbbba, aaabbbba, aaaaabbbba } 其真后缀集合为：{ε,ba,bbba,abbbba, aaabbbba} 设}1,0{=∑，请给出上∑的下列语言的形式表示。

所有最多有一对连续的0或者最多有一对连续的1的串。

解答：****}0,01}{11,{}0,10{}1,10}{00,{}1,01{εε 。

所有最多有一对连续的0并且最多有一对连续的1的串。

解答：按照实际情况分成4类：1) 只有一对连续的0： **}1,10}{00{}1,01{。

2) 只有一对连续的1： **}0,01}{11{}0,10{。

3) 没有连续的0并且没有连续的1：**}01{}10{ 。

4) 有一对连续的0和一对连续的1：******}10}{00{}01}{11{}10{}01}{11{}10}{00{}01{ 。

所有长度为偶数的串。

解答：...2,1,}1,0{2 n n所有倒数第10个字符是0的串。

解答：{0,1}*0{0,1}9。

第二章正则文法 G=(V ,T,P,S)1. 文法产生句子用到的是推导，判断一个句子的合法性可以使用产生语言文法的推导和规约进行判断2. 文法的构造。

第三章作业答案1．已知DFA M1与M2如图3－18所示。

(xxxx 02282068) (1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。

(2) 请给出它们的形式描述。

Sq q1q q图3－18 两个不同的DFA解答：(1)M1在处理1011001的过程中经过的状态序列为q0q3q1q3q2q3q1q3;M2在处理1011001的过程中经过的状态序列为q0q2q3q1q3q2q3q1;(2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述:M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} *******************************************************************************2．构造下列语言的DFA( xx02282085 ) （1）{0，1}*，1（2）{0，1}+，1（3）{x|x{0，1}+且x 中不含00的串}（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）（4）{ x|x{0，1}*且x中不含00的串}（可接受空字符串，所以初始状态也是接受状态）（5）{x|x{0，1}+且x中含形如10110的子串}（6）{x|x{0，1}+且x中不含形如10110的子串}（设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）（7）{x|x{0，1}+且当把x看成二进制时，x模5和3同余，要求当x为0时，|x|=1,且x0时，x的首字符为1 }1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进入陷阱状态2.设置7个状态：开始状态qs,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态qt3.状态转移表为（8）{x|x{0，1}+且x的第十个字符为1}（设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）（9）{x|x{0，1}+且x以0开头以1结尾}（设置陷阱状态，当第一个字符为1时，进入陷阱状态）（10）{x|x{0，1}+且xxx至少含有两个1}（11）{x|x{0，1}+且如果x以1结尾，则它的xx为偶数；如果x以0结尾，则它的xx为奇数}可将{0，1}+的字符串分为4个等价类。

形式语言与自动机期末复习题及答案（一）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种基本的专业能力：计算思维能力、算法的设计与分析能力、程序设计和实现能力、计算机软硬件系统的认知、分析、设计与应用能力。

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

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

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

新技术楼电梯DFA模型班级：1003104学号：1100300808姓名：李佳宁一、自然语言描述：1电梯的基本情况：1)新技术楼一共有10层。

3)电梯内部设有开门、关门和1-10数字键。

4)除第一层只有向上键、第十层只有向下键以外，在每一层楼电梯门外部均设有向上和向下键。

2电梯的运行方式：对于任意的i,j,k (1≤i< j<k≤10)上升期间：（1）当电梯经过第i层向上运动时，用户按下j层键和k层键，电梯会先停在第j层，再停在第k层。

（2）当电梯经过第i层向上运动时，在内部有j键按下，外部k层有向键按下，先到j再到k。

（3）当电梯经过第i层向上运动时，外部j，k层有向上键按下，先到j再到k。

（4）当电梯经过第i层向上运动时，外部j，k层有向下键按下，先到k再到j。

（5）当电梯经过第i层向上运动时，在内部有k键按下，外部j层有向下键按下，先到k层后再回到j层。

（6）当电梯经过第j层向上运动时，用户之前已按下k键，此时再按下i键，电梯会停止在第k层，且不会再返回第i层。

（7）在j层向上的电梯，在电梯内有k键被按下，i层外有键按下，则先到k 层再返回i层。

（8）在j层向上的电梯，在电梯外i层k层有向下键按下，当电梯向上状态结束后，先到k层再到i层。

（9）按键一但按下后，将不能够取消。

（10）当电梯超重时电梯将停在该楼层，直到电梯载重恢复到极限之下时电梯才会接着运行下降期间运行状态与向上类似，这里不多加说明。

二．DFA设计：1.状态：Q1 电梯停在1楼 Q2 电梯停在2楼 Q3 电梯停在3楼 Q4 电梯停在4楼 Q5 电梯停在5楼 Q6 电梯停在6楼 Q7 电梯停在7楼 Q8 电梯停在8楼 Q9 电梯停在9楼Q10 U1 电梯停在10楼电梯上升过程中经过1楼U2 电梯上升过程中经过2楼 U3 电梯上升过程中经过3楼 U4 电梯上升过程中经过4楼 U5 电梯上升过程中经过5楼 U6 电梯上升过程中经过6楼 U7 电梯上升过程中经过7楼 U8 电梯上升过程中经过8楼 U9 电梯上升过程中经过9楼 D2 电梯下降过程中经过2楼 D3 电梯下降过程中经过3楼 D4 电梯下降过程中经过4楼 D5 电梯下降过程中经过5楼 D6 电梯下降过程中经过6楼 D7 电梯下降过程中经过7楼2、输入信号： 1≤i ≤10，i 为整数，u 、d 为字母三、DFA 图(由于本楼层实在太多且全部由本人完成，故只选5层楼为例，并假设第5层楼为顶楼)：D8电梯下降过程中经过8楼 D9D10电梯下降过程中经过9楼 电梯下降过程中经过10楼 E1电梯超重停在1楼 E2电梯超重停在2楼 E3电梯超重停在3楼 E4电梯超重停在4楼 E5电梯超重停在5楼 E6电梯超重停在6楼 E7电梯超重停在7楼 E8电梯超重停在8楼 E9电梯超重停在9楼 E10电梯超重停在10楼i电梯内部i 键被按下 iu电梯外部第i 层向上键被按下(无10u) id 电梯外部第i 层向键被按下（无1d ）E 使电梯超重状态的输入R 使电梯由超重状态恢复的输入三、DFA 表达式：DFA A = {Q, Σ, δ, Q0, F}：Q={Q1，Q2，Q3，Q4，Q5，Q6，Q7，Q8，Q9，Q10，U1，U2，U3，U4，U5，U6，U7，U8，U9，D2，D3，D4，D5，D6，D7，D8，D9，D10，E1，E2，E3，E4，E5，E6，E7，E8，E9，E10}；∑={1,2,3,4,5,6,7,8,9,10,1u,2u,3u,4u,5u,6u,7u,8u,9u,2d,3d,4d,5d,6d,7d,8d,9d,10d,E,R}；转移函数（以下所有状态下标都在1~10范围内）：（Qi，i）=Qi ；δ（Qi，E）=Ei ；δ（Ei，R）=Qi ；δ（Qi，iu）=Qi （i小于10）；δ（Qi，id）=Qi （i大于1）；δ（Qi，i+1 至10）=Ui ；δ（Qi，（i+1）u 至9u）= Ui ；δ（Qi，（i+1）d 至10d）= Ui ；δ（Qi，1 至i-1）=Di ；δ（Qi，1u 至（i-1）u）= Di ；δ（Qi，2d 至（i-1）d）= Di ；δ（U(i-1)，i）=Qi ；δ（U(i-1)，iu）=Qi ；δ（U(i-1)，id）=Qi ；δ（D(i+1)，i）=Qi ；δ（D(i+1)，iu）=Qi ；δ（D(i+1)，id）=Qi ；δ（U(i-1)，i+1 至10）=Ui ；δ（U(i-1)，(i+1)u 至9u）=Ui ；δ（U(i-1)，(i+1)d 至10d）=Ui ；δ（D(i+1)，i-1 至1）=Di ；δ（D(i+1)，(i-1)u 至1u）=Di ；δ（D(i+1)，(i-1)d 至2d）=Di ；Q0=Q1；F={Q1，Q2，Q3，Q4，Q5，Q6，Q7，Q8，Q9，Q10}；四、小组分工：全部由李佳宁一人完成（小组人数一人）。

形式语言与自动机课后习题答案第二章4．找出右线性文法，能构成长度为1至5个字符且以字母为首得字符串。

答：G={N,T,P,S}其中N={S,A,B,C,D} T={x,y} 其中x∈{所有字母} y∈{所有得字符} P如下: S→x S→xA A→y A→yBB→y B→yC C→y C→yD D→y6．构造上下文无关文法能够产生L={ω/ω∈{a,b}*且ω中a得个数就是b得两倍}答：G={N,T,P,S}其中N={S} T={a,b} P如下:S→aab S→aba S→baaS→aabS S→aaSb S→aSab S→SaabS→abaS S→abSa S→aSba S→SabaS→baaS S→baSa S→bSaa S→Sbaa7．找出由下列各组生成式产生得语言（起始符为S）(1)S→SaS S→b(2)S→aSb S→c(3)S→a S→aE E→aS答：（1）b(ab)n /n≥0}或者L={(ba)n b/n≥0}(2) L={a n cb n /n≥0}(3)L={a2n+1 /n≥0}第三章1．下列集合就是否为正则集，若就是正则集写出其正则式。

（1）含有偶数个a与奇数个b得{a,b}*上得字符串集合（2）含有相同个数a与b得字符串集合（3）不含子串aba得{a,b}*上得字符串集合答：（1）就是正则集，自动机如下题（2）。

(3) 就是正则集先瞧L’为包含子串aba得{a,b}*上得字符串集合显然这就是正则集，可以写出表达式与画出自动机。

（略）则不包含子串aba得{a,b}*上得字符串集合L就是L’得非。

根据正则集得性质，L也就是正则集。

4．对下列文法得生成式，找出其正则式（1）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：S→aA S→BA→abS A→bBB→b B→cCC→D D→bBD→d（2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下：S→aA S→BA→cC A→bBB→bB B→aC→D C→abBD→d答：(1) 由生成式得：S=aA+B ①A=abS+bB ②B=b+cC ③C=D ④D=d+bB ⑤③④⑤式化简消去CD，得到B=b+c(d+bB)即B=cbB+cd+b =>B=(cb)*(cd+b) ⑥将②⑥代入①S=aabS+ab(cb)*(cd+b)+(cb)*(cd+b) =>S=(aab)*(ab+ε)(cb)*(cd+b) (2) 由生成式得：S=aA+B ①A=bB+cC ②B=a+bB ③C=D+abB ④D=dB ⑤由③得 B=b*a ⑥将⑤⑥代入④ C=d+abb*a=d+ab+a ⑦将⑥⑦代入② A=b+a+c(d+b+a) ⑧将⑥⑧代入① S=a(b+a+c(d+ab+a))+b*a=ab+a+acd+acab+a+b*a5、为下列正则集，构造右线性文法：(1){a,b}*(2)以abb结尾得由a与b组成得所有字符串得集合(3)以b为首后跟若干个a得字符串得集合(4)含有两个相继a与两个相继b得由a与b组成得所有字符串集合答：（1）右线性文法G=({S},{a,b},P,S)P: S→aS S→bS S→ε(2) 右线性文法G=({S},{a,b},P,S)P: S→aS S→bS S→abb(3) 此正则集为{ba*}右线性文法G=({S,A},{a,b},P,S)P: S→bA A→aA A→ε(4) 此正则集为{{a,b}*aa{a,b}*bb{a,b}*, {a,b}*bb{a,b}*aa{a,b}*}右线性文法G=({S,A,B,C},{a,b},P,S)P: S→aS/bS/aaA/bbBA→aA/bA/bbCB→aB/bB/aaCC→aC/bC/ε7、设正则集为a(b a)*(1)构造右线性文法(2)找出（1）中文法得有限自b动机答：（1）右线性文法G=({S,A},{a,b},P,S)P: S→aA A→bS A→ε（2）自动机如下：)9、对应图（a）(b)得状态转换图写出正则式。

形式语言与自动机复习总结适合《形式语言与自动机》（第2版）、杨娟，石川，王柏主编1.形式语言：形式化描述的字母表上的字符串集合，是一种公认的符号和表达式所描述的一种语言，是通用的语言。

2.自动机：具有离散的输入输出模型。

a)状态：一个标识，能区分自动机在不同时刻的状况。

b)自动机本质：根据输入和规则决定下一个状态。

c)部分常见的自动机：i.有限自动机：具有读头的有限控制器和一条写有字符的输入带组成。

ii.下推自动机：由一个输入带，一个有限控制器和一个下推栈组成。

iii.图灵机：一个具有读写头的有限控制器和一条无限带组成。

3.部分术语a)字母表：字符的有限集合，记为。

b)字符串：由字母表中的字符构成的序列。

Note: 一般字符串常用来表示，单个字符常用来表示。

c)字（串）：字母表上的字符串。

d)空串：不包含任何字符的字符串，用表示。

e)长度：字符串上的字符个数，用表示。

f)连接：设为串，且，，那么和的连接定义为。

性质：i.ii.iii.g)字符串的逆：字符串的倒置，用或表示，其中。

h)幂运算：设为字母表，为任意自然数，定义：i.ii.设，则iii.中的元素由i和ii生成i)闭包：j)闭包：Note:4.语言：设为字母表，则任何集合是字母表上的一个语言。

a)语言的积：和的积表示为，表示由和的字符串连接所构成的字符串的集合。

Note:b)语言的幂：。

Note: 字符串和语言的关系可以类比集合的元素和集合的关系。

5.文法：定义语言的数学模型。

a)列举法：表示有限集合。

b)文化产生系统：由定义的文法规则产生语言。

c)机器识别系统：当一个字符串能被识别系统接受，则这个字符串是语言的一个句子。

d)BNF：讨论某种程序设计语言语法的元语言<数字><字母><标识符> <字母>|<标识符><字母>|<标识符><数字>“定义为”, “或者”, <>: “必须的部分”6.Chomsky文法体系：将BNF中的“”用“”代替，用字符代替汉字包含两个不同的有限符号的集合：非终结符和终结符，形式规则的有限集，起始符，文法，的集合，, 。