编译原理作业三 T3-1构造自动机A ，使得它能识别形式如±dd*·d*E ±dd 的实数，其中，d ∈{0,1,2,3,4,5,6,7,8,9} T3-4将图所示NFA 确定化和最小化。 解：依据该NFSA 的状态图构造DFSA 如下表所示。 I I x I y [q 0] 0 [q 1] 1 [q 2] 2 [q 1] 1 [q 2,q 3] 3 [q 2] 2 [q 1,q 3] 4 [q 2,q 3] 3 [q 3,q 4] 5 [q 1,q 3] 4 [q 1,q 3] 4 [q 2,q 3,q 4] 6 [q 3] 7 [q 3,q 4] 5 [q 3,q 4] 5 [q 3] 7 [q 2,q 3,q 4] 6 [q 3,q 4] 5 [q 1,q 3] 4 [q 3] 7 [q 3,q 4] 5 [q 3] 7 DFSA 相应的状态图如下图所示： 6 1 2 3 4 5 7 X X y y y X X X X X y y y y S 3 1 4 2 5 6 7 ± d E d d d d ±
对DFSA 进行最小化： 已知K={0，1,2,3,4,5,6,7}，K 可分为两个子集 K1={0,1,2,3,4,7}（非终态集） K2={5,6}（终态集） 在K1中，因为状态1只有x 输入，状态2只有y 输入，其他状态均有x ，y 输入，所以可以将K1分割为K11={0,3,4,7} K12={1} K13={2} 在K11中 {0}x=1∈K12 {3,4,7}x={5,6}?K2 故可将K11分割为 K111={0} K111={3,4,7} {3,4,7}x={5,6}?K2 {3,4,7}y={4,7}?K111 因此状态3,4,7是否等价取决于对K2的划分结果 在状态K2={5,6}中 {5,6}x=5∈K2 {5,6}y={4,7}?K111 所以状态5,6等价，所以状态3,4,7等价 所以，将原状态集合划分为{0}、{3,4,7}、{1}、{2}、{5,6} 最小化后的状态图为： S 1 2 3 5 X X X X y y y y
第三章 ******************************************************* ************************ 1．构造下列语言的DFA ( 陶文婧 02282085 ) （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个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5 余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t （8）{x|x{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态） （9）{x|x{0，1}+且x以0开头以1结尾} （设置陷阱状态，当第一个字符为1时，进入陷阱状态）
（10）{x|x{0，1}+且x中至少含有两个1} （11）{x|x {0，1}+且如果x以1结尾，则它的长度为偶数；如果x以0结尾，则它的长度为奇数} 可将{0，1}+的字符串分为4个等价类。 q0：[]的等价类，对应的状态为终止状态 q1:x的长度为奇且以0结尾的等价类 q2：x的长度为奇且以1结尾的等价类 q3: x的长度为偶且以0结尾的等价类 q4: x的长度为偶且以1结尾的等价类 （12）{x|x是十进制非负数}
第三章词法分析 本章要点 １．词法分析器设计， ２．正规表达式与有限自动机， ３．词法分析器自动生成。 本章目标： １．理解对词法分析器的任务，掌握词法分析器的设计； ２．掌握正规表达式与有限自动机； ３．掌握词法分析器的自动产生。 本章重点： 1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。 2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。 （1）非形式描述的语言?正规式 （2）正规式→ NFA（非确定的有限自动机） （3）NFA → DFA（确定的有限自动机） （4）DFA →最简DFA 本章难点 （1）非形式描述的语言?正规式 （2）正规式→ NFA（非确定的有限自动机） （3）NFA → DFA（确定的有限自动机） （4）DFA →最简DFA
作业题 一、单项选择题 （按照组卷方案，至少15道） 1. 程序语言下面的单词符号中，一般不需要超前搜索 a. 关键字 b. 标识符 c. 常数 d. 算符和界符 2. 在状态转换图的实现中，一般对应一个循环语句 a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是 3. 用了表示字母，d表示数字， ={l，d}，则定义标识符的正则表达式可以是：。 (a)ld*(b)ll*(c)l(l | d)*(d)ll* | d* 4. 正规表达式(ε|a|b)2表示的集合是 (a){ε，ab，ba，aa，bb} (b){ab，ba，aa，bb} (c){a，b，ab，aa，ba，bb} (d){ε，a，b，aa，bb，ab，ba} 5. 有限状态自动机可用五元组（V T，Q，δ，q0，Q f）来描述，设有一有限状态自动机M的定义如下： V T={0，1}，Q={q0，q1，q2}，Q f={q2}，δ的定义为： δ（q0，0）=q1δ（q1，0）=q2 δ（q2，1）=q2δ（q2，0）=q2 M所对应的状态转换图为。
形式语言与自动机课后作业答案 第二章 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→yB B→y B→yC C→y C→yD D→y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa 7．找出由下列各组生成式产生的语言（起始符为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) 不是正则集，用泵浦引理可以证明，具体见17题（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→B A→abS A→bB B→b B→cC C→D D→bB D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→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*a 5.为下列正则集，构造右线性文法： (1){a,b}* (2)以abb结尾的由a和b组成的所有字符串的集合
第三章习题参考解答 3.1 构造自动机A，使得 ① ② ③当从左至右读入二进制数时，它能识别出读入的奇数； ④它识别字母表{a, b}上的符号串，但符号串不能含两个相邻的a，也不含两个相邻的b； ⑤它能接受字母表{0, 1}上的符号串，这些符号串由任意的1、0和随后的任意的11、00对组成。 ⑥它能识别形式如 ±dd*? d*E ±dd 的实数，其中，d∈{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。 3.2 构造下列正规表达式的DFSA： ① xy*∣yx*y∣xyx； ② 00∣(01)*∣11； ③ 01((10∣01)*(11∣00))*01； ④ a(ab*∣ba*)*b。 3.3 消除图3.24所示自动机的空移。 b ε q 1 q 2 q 3 a b a,b q a q 6 q 4 q 5 a b ε ε ε 图3.24 含空移的自动机 3.4 将图3.25所示NDFSA确定化和最小化。 x y q q 1 q 2 q 4 q 3 x y x y x,y x 图3.25 待确定化的NDFSA
3.5 设e、e1、e2是字母表∑上的正规表达式，试证明 ① e∣e=e；② {{e}}={e}；③ {e}=ε∣e{e}；④ {e1 e2} e1= e1{e2 e1}; ⑤ {e1∣e2}={{e1}{e2}}={{e1}∣{e2}}。 3.6 构造下面文法G[Z]的自动机，指明该自动机是不是确定的，并写出它相应的语言： G[Z]: Z→A0 A→A0∣Z1∣0 3.7 设NDFSA M=({x, y},{a, b},f, x, {y}), 其中，f(x, a)={x, y}, f(x, b)={y}, f(y, a)=?, f(y, b)={x, y}。试对此NDFSA确定化。 3.8 设文法G[〈单词〉]： 〈单词〉→〈标识符〉∣〈无符号整数〉 〈标识符〉→〈字母〉∣〈标识符〉〈字母〉∣〈标识符〉〈数字〉 〈无符号整数〉→〈数字〉∣〈无符号整数〉〈数字〉 〈字母〉→a∣b 〈数字〉→1∣2 试写出相应的有限自动机和状态图。 3.9 图3.29所示的是一个NDFSA A，试构造一个正规文法G，使得L(G)= L(A)。 A B b S a a,b C a D b 图3.29 FSA A 3.10 构造一个DFSA，它接受∑={a, b}上的符号串，符号串中的每一个b都有a直接跟在右边；然后，再构造该语言的正规文法。 参考答案 3.1 解 (1) (2) (3) 依题意，当二进制数的末尾为1时，表示此二进制数为奇数。因此自动机接收由0、1构成的一个二进制串，且串的最后一位必为1（特殊情况下，接收数字1）。构造的自动机如下: z S 1 0,1
第三章有穷自动机 1、教学目的及要求： 本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式与有穷自动机之间的相互关系。要求掌握正则文法、状态转换图、DFA、NFA、正规式和正规集的基本概念。 2、教学内容： 本章介绍有关有穷自动机的基本概念和理论以及正规文法、正规表达式与有穷自动机之间的相互关系。 3、教学重点： 状态转换图。 4、教学难点： ◇正规式的定义-如何用作单词的描述工具 ◇有穷自动机的定义和分类-如何用作单词的识别系统 ◇正规式到有穷自动机的转换算法-词法分析程序的自动构造原理 ◇正则文法、正规集、DFA、NFA的相互转化。 5、课前思考 ◇什么是有穷自动机？ ◇什么是状态转换图？ 6、章节内容 第一节有穷自动机的形式定义 第二节 NFA到DFA的转换 第三节正规文法与有穷自动机 第四节正规表达式与FA 第五节 DFA在计算机中的表示
3.1 有穷自动机的形式定义 有穷状态自动机(Finite-state Automata 或简称FA)在识别功能上与正规文法类等价，而且也等价于一个特殊类型的语言产生器——正规表达式(Regular Expression)。因此许多简单的程序语言都可由FA所识别。事实上，它是描述词法的有效工具，也是进行词法分析的主要理论基础。 为了构造词法分析程序，要研究构词法，每种词类的结构模式以及识别它的数学模型——有穷自动机。它的模拟程序可以作为词法分析程序的控制程序。 有穷自动机(也称有限自动机)作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。 有穷自动机分为两类：确定的有穷自动机(Deterministic Finite Automata)和不确定的有穷自动机(Nondeterministic Finite Automata) 。 一、确定有穷自动机的形式定义 一个确定的有穷自动机M(记作DFA M)是一个五元组Ｍ＝(K，Σ，f，S，Z)，其中(ａ) K是一个有限状态集合。 (ｂ) Σ是一个字母表，它的每个元素称为一个输入字符。 (ｃ) S∈K，S 称为初始状态，唯一。 (ｄ) Z?K，Z称为终态集合, 终态也称可接受状态或结束状态。 (ｅ) f是转换函数，是一个从K×Σ到K的单值映射。f(k i，a)＝k j（k i,k j∈Ｑ,a∈Σ）k j称为k i的一个后继状态。 确定性的体现：初始状态唯一；转换函数为单值映射。 例：设DFA M=({S，U，V，Q}，{a，b}，f，S，｛Q｝)其中 f（S，a）＝U，f（S，b）＝V f（U，a）＝Q，f（U，b）＝V f（V，a）＝U，f（V，b）＝Q f（Q，a）＝Q，f（Q，b）＝Q 因为（1）初始状态唯一是S，（2）每个转换函数均为单值映射。所以该FA为确定有穷自动机。 二、状态转换表 DFA的映射关系可以由一个矩阵表示，矩阵的行标表示状态，列标表示输入字符，矩阵元素表示f(s,a)的值，这个矩阵称为状态转换表。 例：
第三章作业答案 1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068) (1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。 S q q 1 图3－18 两个不同的DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1; (2)考虑到用形式语言表示,用自然语言似乎不是那么容易, 所以用图上作业法把它们用正则表达式来描述: M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} ******************************************************************************* 2．构造下列语言的DFA ( 文婧 02282085 ) （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,且x≠0时，x的首字符为1 } 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进入 陷阱状态 2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以 5余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t
编译原理作业集-第三章-修 订版 -标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII
第三章词法分析 本章要点 １．词法分析器设计， ２．正规表达式与有限自动机， ３．词法分析器自动生成。 本章目标： １．理解对词法分析器的任务，掌握词法分析器的设计； ２．掌握正规表达式与有限自动机； ３．掌握词法分析器的自动产生。 本章重点： 1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。 2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。 （1）非形式描述的语言正规式 （2）正规式 NFA（非确定的有限自动机） （3）NFA DFA（确定的有限自动机） （4）DFA 最简DFA 本章难点 （1）非形式描述的语言正规式 （2）正规式 NFA（非确定的有限自动机） （3） NFA DFA（确定的有限自动机） （4） DFA 最简DFA
作业题 一、单项选择题 （按照组卷方案，至少15道） 1. 程序语言下面的单词符号中，一般不需要超前搜索 a. 关键字 b. 标识符 c. 常数 d. 算符和界符 2. 在状态转换图的实现中，一般对应一个循环语句 a. 不含回路的分叉结点 b. 含回路的状态结点 c. 终态结点 d. 都不是 3. 用了表示字母，d表示数字， ={l，d}，则定义标识符的正则表达式可以是：。 (a)ld* (b)ll* (c)l(l | d)* (d)ll* | d* 4. 正规表达式(ε|a|b)2表示的集合是 (a){ε，ab，ba，aa，bb} (b){ab，ba，aa，bb} (c){a，b，ab，aa，ba，bb} (d){ε，a，b，aa，bb，ab，ba} 5. 有限状态自动机可用五元组（V T，Q，δ，q0，Q f）来描述，设有一有限状态自动机M的定义如下： V T={0， 1}，Q={q0， q1， q2}，Q f={q2}，δ的定义为： δ（q0，0）=q1δ（q1，0）=q2 δ（q2，1）=q2δ（q2，0）=q2
第三章作业答案 1 已知 DFA M1与M2如图3- 18所示。 (1) 请分别给出它们在处理字符串 (2) 请给出它们的形式描述。 图3- 18 两个不同的DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为 M2在处理1011001的过程中经过的状态序列为 q °q 2q 3q 1q 3q 2q 3q 1； ⑵考虑到用形式语言表示，用自然语言似乎不是那么容易，所 以用图上作业法把它们用正则 表达式来描述 M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01 + 1+000){(01)*+[(001 + 11)(01 + 1+000)]*} ******************************************************************************* 2. 构造下列语言的 DFA (陶文婧 02282085 ) (1) {0 , 1} (3) {x|x {0, 1}+ 且x 中不含00的串} (设置一个陷阱状态，一旦发现有 00的子串，就进入陷阱状态) 0 * 1 0 0 1 0 0 1 0 1 1 0 1 (敖雪峰 02282068) 1011001的过程中经过的状态序列。 q o q 3q 1q 3q 2q 3q 1q 3； (2) 0, 1 + {0 , 1}
(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,且x=0 时，x 的 首字符为1 } 1. 以0开头的串不被接受，故设置陷阱状态，当 DFA 在启动状态读入的符号为 0,则进 入陷阱状态 2. 设置7个状态：开始状态q s ,q °:除以5余0的等价类，除以5余1的等价类口2:除以5 余2的等价类，q 3：除以5余3的等价类，q 4：除以5余4的等价类，接受状态 q t 状态 0 1 q 0 q 1 q 2 q 1 q 3 q 2 q 2 q 0 q 4 q 3 q 1 q 2 1
第3章习题解答： 1. 解答： (1) √(2) √ (3) ×(4) ×(5) √(6)√ 2. [分析] 有限自动机分为确定有限自动机和非确定有限自动机。确定有限自动机的确定性表现在映射δ：Q×V T-->q是单值函数，也就是说，对任何状态 q∈Q和输入字符串a∈V T，δ(q,a)唯一确定下一个状态。显然，本题给出的是一个确定的有限自动机，它的状态转换图是C 中的②。 它所接受的语言可以用正则表达式表示为00(0|1)*，表示的含义为由两个0开始的后跟任意个（包含0个）0或1组成的符号串的集合。 2. 解答：A:④ B:③ C:② D:② E: ④ 3，4．解答：略！ 5．解答： 6．解答： (1) (0|1)*01 (2) ((1|2|…|9)(0|1|2|…|9)*| ε)(0|5) (3) (0|1)*(011)(0|1)* (4) 1*|1*0(0|10)*(1|ε) (5) a*b*c*…z* (6) (0|10*1)*1 (7) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* (8) [分析] 设S是符合要求的串，|S|=2k+1 (k≥0）。 则 S→S10|S21，|S1|=2k (k>0），|S2|=2k (k≥0）。 且S1是{0,1}上的串，含有奇数个0和奇数个1。 S2是{0,1}上的串，含有偶数个0和偶数个1。 考虑有一个自动机M1接受S1，那么自动机M1如下： 和L(M1)等价的正规式，即S1为： ((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)* 类似的考虑有一个自动机M2接受S2，那么自动机M2如下：
第3章习题解答 1.构造正规式1(0|1)*101相应的DFA. [答案] 先构造NFA ============================================================== 2.将下图确定化：
[答案] 重新命名，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。 ================================================================ 3.把下图最小化： [答案] （1）初始分划得Π0：终态组{0}，非终态组{1,2,3,4,5}
对非终态组进行审查： {1,2,3,4,5}a {0,1,3,5} 而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5} ∵{4} a {0}，所以得新分划 （2）Π1：{0}，{4}，{1,2,3,5} 对{1,2,3,5}进行审查： ∵{1,5} b {4} {2,3} b {1,2,3,5}，故得新分划 （3）Π2：{0}，{4}，{1, 5}，{2,3} {1, 5} a {1, 5} {2,3} a {1,3}，故状态2和状态3不等价，得新分划 （3）Π3：{0}，{2}，{3}，{4}，{1, 5} 这是最后分划了 （4）最小DFA ： ======================================= 4.构造一个DFA ，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式和正规文法。 [答案] 按题意相应的正规表达式是0*(100*)*0* 构造相应的DFA ，首先构造NFA 为 用子集法确定化 可最小化，终态组为G1={C, D}，非终态组为G2={S, A, B} 对于G2分析：f(S,0)=A, f(A,0)=A, 后继状态均属于G2 而f(B,0)=C, 后继状态属于G1 将G2分割成G21={S ，A}， G22={B}
第四次作业： P74 2. 什么叫超前搜索？扫描缓冲区的作用是什么？ 词法分析程序在识别单词的时候，为进一步判明情况，确定下一步要做什么，一般采用超前读字符的方法，称超前搜索，扫描缓冲区的作用是为了识别单词符号。 P74 4. 画出下列文法的状态图： Z：：=Be B：：=Af A：：=e|Ae 并使用该状态图检查下列句子是否该文法的合法句子：f, eeff, eefe。 由状态图可知只有eefe是该文法的合法句子。 P74 5. 设右线性文法G=({S, A, B}, {a, b}, S, P)，其中P组成如下： S：：=bA A：：=bB A：：=aA A：：=b B：：=a 画出该文法的状态转换图。 第五次作业： P74 6. 构造下述文法G[Z]的自动机，该自动机是确定的吗？它相应的语言是什么？ Z：：=A0 A：：=A0|Z1|0 解1：将左线性文法转换为右线性文法，由于在规则中出现了识别符号出现在规则右部的情形，因此不能直接使用书上的左右线性文法对应规则，可以引入非终结符号B，将左线性文法变为Z：：=A0 A：：=A0|B1|0 B：：=A0，具体为： A := Z1 A := B1 A := A01 Z := A0 B := A0
将所得的新左线性文法转换成右线性文法： 此时利用书上规则，其对应的右线性文法为：A ：：=0A|0B|0 Z ：：=0A B ：：=1A 解2：先画出该文法状态转换图： NFA=（{S ，A ，Z}，{0，1}，M ，{S}，{Z}） 其中M ： M （S ，0）={A} M （S ，1）=? M （A ，0）={A ，Z} M （A ，1）=? M （Z ，0）=? M （Z ，1）={A} 显然该文法的自动机是非确定的；它相应的语言为：{0，1}上所有满足以00开头以0结尾且每个1必有0直接跟在其后的字符串的集合；也可以通过求解正规表达式得到A=0(0|01)*，Z=0(0|01)*0 ) P74 7. 构造一个DFA ，它接受{0，1}上所有满足下述条件的字符串，其条件是：字符串中每个1都有0直接跟在右边，然后，再构造该语言的正规文法。【其它解法可参考P41-26题】 解(一)：其状态转换图为 (状态S 表示空串开始，状态A 表明串的末尾是1，状态Z 表示串的末尾是0) DFA=（{S ，A ，Z}，{0，1}，M ，S ，{Z}） 其中M ： M （S ，0）=Z M （S ，1）= A M （A ，0）=Z M （Z ，0）=Z M （Z ，1）=A
第3章文法和语言 第1题 文法G＝({A,B,S},{a,b,c},P,S)其中P为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 答案： L(G[S])={abc} 第2题 文法G[N]为： N→D|ND D→0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ 答案: G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D 或者：允许0开头的非负整数？ 第３题 为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。答案： G[S]: S->S+D|S-D|D D->0|1|2|3|4|5|6|7|8|9 第4题 已知文法G[Z]： Z→aZb|ab 写出L(G[Z])的全部元素。 答案： Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={a n b n |n>=1} 第5题 写一文法，使其语言是偶正整数的集合。要求： (1) 允许0打头； (2)不允许0打头。 答案： (1)允许0开头的偶正整数集合的文法E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 (2)不允许0开头的偶正整数集合的文法E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6题
已知文法G： <表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i 试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i
一:有语言L={w|w∈{0,1}*，并且w中至少有两个1，又在任何两个1之间有偶数个0 }，试写出该语言的正规表达式。 对于语言L，w中至少有两个1，且任意两个1之间必须有偶数个0；也即在第一个1之前和最后一个1之后，对0的个数没有要求。据此我们求出L的正规式为0*1(00(00)*1)*00(00)*10* 二：设语言L是满足下述条件的符号串构成的语言：若出现 a ，则其后至少紧跟两个 c ；请给出识别L 的正规表达式。其中字母表为{a,b,c} (acc|b|c)* 三：写出下面NFA识别的正规式 (a|b)ab* 三：已知文法G1: S→aB|ε B→bC|bD C→cB|c D→d 试构造其对应的最小DFA,并给出状态转换图和构造过程。 确定化：
最小化： {1，5，4} {2，3} {1}{5}{4}{2}{3} 上图即为最小DFA 四:设有L(G)={a 2n+1b 2m a 2p+1| n ≥0,p ≥0,m ≥1}。 (1) 给出描述该语言的正规表达式； (2) 构造识别该语言的确定有限自动机(可直接用状态图形式给出)并化简。 该语言对应的正规表达式为a(aa)*bb(bb)*a(aa)*，正规表达式对应的NFA 如图： 确定化：（按照定义，上图已经是DFA ，所以下面确定化不做也是可以的，直接最小化） 由最小化方法得到 {0,2} {1} {3,5} {4,6} {7} 最简的DFA ： a 重新命名
五： 将图所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)并化简。其中，X 为初态，Y 为终态。然后根据最小DFA ，写出对应的正规文法（右线性） b 重新命名
概率论与数理统计第三章习题 0.7一射手对某目标进行了三次独立射击，现将观察这些次射击是否命中作为试验，试写出此试验的样本空间；试在样本空间上定义一个函数以指示射手在这三次独立射击中命中目标的次数；设已知射手每次射击目标的命中率为，试写出命中次数的概率分布。 1231231231231231231231231234567812345671,2,3 {(,,),(,,),(,,),(,,),(,,), (,,),(,,),(,,)}{,,,,,,,}()3()()()2()()()1 i A i i A A A A A A A A A A A A A A A A A A A A A A A A ωωωωωωωωξξωξωξωξωξωξωξωξ==Ω=========解：设“第次射中”，则令代表击中目标的次数，则 ，，83112323412356712338123()0 (3)()()(0.7)0.343(2)()()()3() 30.70.7(10.7)0.441 (1)()()()3() 30.7(10.7)(10.7)0.189 (0)(0)()(10.7)0.0P P P A A A P P P P P A A A P P P P P A A A P P P A A A ωξωξωωωξωωωξω========++==???-===++==??-?-======-=270 123.0.0270.1890.4410.343ξ?? ??? 所以，的分布列为 ξ 服从~(3,0.7)B ξ，在Excel 依次输入： =binomdist （0，3，0.7，0）， =binomdist （1，3，0.7，0）， =binomdist （2，3，0.7，0）， =binomdist （3，3，0.7，0）， 2.9311一批零件中有个合格品、个废品，安装机器时从这批零件中任取个来使用，若取得废品就不再放回而再取个，求在取得合格品之前已取出的废品数的概率分布。
形式语言与自动机理论-蒋宗礼-第三章参考答案
第三章作业答案 1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068) (1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。 10 10 S q q q 2 q 3 1 11 q 2 q 3 1 1 图3－18 两个不同的 DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3;
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 ( 陶文婧 02282085 ) （1）{0，1}* ，1 （2）{0，1}+ 0，1 0，1 S （3）{x|x {0，1}+且x中不含00的串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态）
1 1 S 01 0,1 （4）{ x|x∈{0，1}*且x中不含00的串} （可接受空字符串，所以初始状态也是接受状态） 1 1 S 01 0,1 （5）{x|x∈{0，1}+且x中含形如10110的子串} 1 S 010 0,1 101 （6）{x|x∈{0，1}+且x中不含形如10110的子串} （设置一个陷阱状态，一旦发现有00的子串，就进入陷阱状态） 1 010 0,1 ,101 1 （7）{x|x∈{0，1}+且当把x看成二进制时，x模
形式语言与自动机 第二章 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→yB B→y B→yC C→y C→yD D→y 6．构造上下文无关文法能够产生 L={ω/ω∈{a,b}*且ω中a的个数是b的两倍} 答：G={N,T,P,S} 其中N={S} T={a,b} P如下: S→aab S→aba S→baa S→aabS S→aaSb S→aSab S→Saab S→abaS S→abSa S→aSba S→Saba S→baaS S→baSa S→bSaa S→Sbaa 7．找出由下列各组生成式产生的语言（起始符为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) 不是正则集，用泵浦引理可以证明，具体见17题（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→B A→abS A→bB B→b B→cC C→D D→bB D→d （2）G=({S,A,B,C,D},{a,b,c,d},P,S),生成式P如下： S→aA S→B A→cC A→bB B→bB B→a C→D C→abB D→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*a 5.为下列正则集，构造右线性文法： (1){a,b}* (2)以abb结尾的由a和b组成的所有字符串的集合
第三章作业答案 1．已知DFA M1与M2如图3－18所示。 (敖雪峰 02282068) (1) 请分别给出它们在处理字符串1011001的过程中经过的状态序列。 (2) 请给出它们的形式描述。 S q q 1 图3－18 两个不同的DFA 解答：(1)M1在处理1011001的过程中经过的状态序列为q 0q 3q 1q 3q 2q 3q 1q 3; M2在处理1011001的过程中经过的状态序列为q 0q 2q 3q 1q 3q 2q 3q 1; (2)考虑到用形式语言表示,用自然语言似乎不是那么容易,所以用图上作业法把它们用正则表达式来描述: M1: [01+(00+1)(11+0)][11+(10+0)(11+0)]* M2: (01+1+000){(01)*+[(001+11)(01+1+000)]*} ******************************************************************************* 2．构造下列语言的DFA ( 陶文婧 02282085 ) （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,且x≠0时，x的首字符为1 } 1.以0开头的串不被接受，故设置陷阱状态，当DFA在启动状态读入的符号为0，则进 入陷阱状态 2.设置7个状态：开始状态q s,q0:除以5余0的等价类，q1：除以5余1的等价类,q2:除以5 余2的等价类，q3:除以5余3的等价类，q4:除以5余4的等价类，接受状态q t
第3章 文法和语言 第1题 文法G ＝({A,B,S},{a,b,c},P,S)其中P 为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 答案： L(G[S])={abc} 第2题 文法G[N]为： N →D|ND D →0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ 答案: G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D 或者：允许0开头的非负整数？ 第３题 为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。 答案： G[S]: S->S+D|S-D|D D->0|1|2|3|4|5|6|7|8|9 第4题 已知文法G[Z]： Z →aZb|ab 写出L(G[Z])的全部元素。 答案： Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={a n b n |n>=1} 第5题 写一文法，使其语言是偶正整数的集合。 要求： (1) 允许0打头； (2)不允许0打头。 答案： (1)允许0开头的偶正整数集合的文法 E→NT|D T→NT|D N→D|1|3|5|7|9 D→0|2|4|6|8 (2)不允许0开头的偶正整数集合的文法 E→NT|D T→FT|G N→D|1|3|5|7|9 D→2|4|6|8 F→N|0 G→D|0 第6题
已知文法G： <表达式>::=<项>｜<表达式>＋<项> <项>::=<因子>｜<项>*<因子> <因子>::=（<表达式>）｜i 试给出下述表达式的推导及语法树。 （５）i+(i+i) （６）i+i*i