第三章
******************************************************* ************************
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,且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
（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是十进制非负数}
5，6
，7，8，9
4，
9
（13）Φ
（14）ε
******************************************************************************* 2.
(1){{0,1}00}
x x x
+
∈且中不含形如的子串
(2){{0,1}10110}
x x x
+
∈且中含形如的子串
(3){{0,1}}
x x x
+
∈且中不含形如10110的子串
(4){{0,1}10101}
x x x
+
∈和的倒数第个字符是，且以结尾
1 (5){{0,1}01}
x x x
+
∈且以开头以结尾
(6){{0,1}}
x x x
+
∈且中至少含有两个1
0，1
0，1
*
(7){{0,1}
} x x x
∈且如果以1结尾，则它的长度为偶数；
如果以0结尾，则它的长度为奇数(8){{0,1}}
x x x
+
∈且的首字符和尾字符相等
(9){,{0,1}}T x x x ωω+∈
******************************************************************************* 3.根据下列给定文法，构造相应的FA 。 （敖雪峰 02282068）
(1) 文法G1的产生式集合如下： G1: S →a|Aa
A →a|Aa|cA|Bb
B →a|b|c|aB|Bb|Cb
(2) 文法G2的产生式集合如下： G2: S →a|Aa
A →a|Aa|Ac|Bb
B →a|b|c|Ba|Bb|Bc
解答: 文法G1对应的FA 如下所示
a,c
a,b,c
B
文法G2对应的FA
形式语言与自动机课后习题答案 第二章 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 →y C C →y C →y D 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) / (4) 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={a 2n+1 /n ≥0} 第三章 1． 下列集合是否为正则集，若是正则集写出其正则式。 （1） 含有偶数个a 和奇数个b 的{a,b}*上的字符串集合 （2） 含有相同个数a 和b 的字符串集合 （3） < （4） 不含子串aba 的{a,b}*上的字符串集合 答：（1）是正则集，自动机如下 a
a (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 ⑥
形式语言与自动机理论试题答案解析 一、按要求完成下列填空 1.给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集（2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2.设∑={0,1},请给出∑上的下列语言的文法（2x5'） (1)所有包含子串01011的串 S→X01011Y X→ε|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时，进入陷阱状态） (2) {x|x∈{0，1}+且x的第十个字符为1} （设置一个陷阱状态，一旦发现x的第十个字符为0，进入陷阱状态）
二、判断（正确的写T ，错误的写F ） 5x2' 1.设1R 和2R 是集合{a,b,c,d,e}上的二元关系，则 3231321)(R R R R R R R I I ? ( T ) 任取(x.,y),其中x,y },,,,{e d c b a ∈，使得321)(),(R R R y x I ∈。 )),(),((321R y z R R z x z ∈∧∈??I },,,,{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 I ∈? 2.对于任一非空集合A ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 I 2型语言 I 1型语言 I 0型语言 ( F ) 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分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc
编译原理作业三 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 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
第三章 ******************************************************* ************************ 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是十进制非负数}
形式语言与自动机课后作业答案 第二章 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．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。应重点掌握词法分析器的任务与设计，状态转换图等内容。 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所对应的状态转换图为。
形式语言与自动机理论试题答案解析 一、按要求完成下列填空 1. 给出集合{Φ,{Φ}}和集合{ε,0,00}的幂集 （2x4'） (1) {Φ,{Φ},{{Φ}},{Φ,{Φ}}} (2) {Φ,{ε},{0},{00},{ε,0},{ε,00},{0,00},{ε,0,00}} 2. 设∑={0,1},请给出∑上的下列语言的文法 （2x5'） (1)所有包含子串01011的串 S →X01011Y X →ε|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时，进入陷阱状态） 1 S 1 1 0,10 (2) {x|x ∈{0，1} + 且x 的第十个字符为1} （设置一个陷阱状态，一旦发现x 的第十个字符为0，进入陷阱状态） 1S 0,1 0,10,10,10,110,0,10,10,10,1 0,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 ，Φ?A 2 ( T ) 3.文法G ：S A|AS A a|b|c|d|e|f|g 是RG ( F ) 4.3型语言 2型语言 1型语言 0型语言 ( F ) 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分）。 aSBC aBC S |→ ab aB → bB →bb CB →BC bC →bc cC →cc
第三章习题参考解答 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.1请用列举法给出下列集合。（吴贤珺02282047） ⑴你知道的各种颜色。 解：{红，橙，黄，绿，青，蓝，紫} ⑵大学教师中的各种职称。 解：{助教，讲师，副教授，教授} ⑶你所学过的课程。 解：{语文，数学，英语，物理，化学，生物，历史，地理，政治} ⑷你的家庭成员。 解：{父亲，母亲，妹妹，我} ⑸你知道的所有交通工具。 解：{汽车，火车，飞机，轮船，马车} ⑹字母表{a , b}上长度小于4的串的集合。 解：{a,b,aa,bb,ab,ba,aaa,aab,aba,abb,baa,bab,bba,bbb} ⑺集合{1,2,3,4}的幂集。 解：{Φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4}, {1,3,4},{2,3,4},{1,2,3,4} } ⑻所有的非负奇数。 解：{1,3,5,7,…} ⑼0～100的所有正整数。 解：{1,2,3, (100) (10) 1～10之间的和为10的整数集合的集合。 解：设所求的集合为A，集合A中的元素为A i（i=1,2,3,…），A i也是集合，A i中的元素在1～10之间，并且和为10。根据集合元素的彼此可区分性，可以计算出A i中元素的最多个数，方法是：把1开始的正整数逐个相加，直到等于10（即10=1+2+3+4），这样， A i中最多有4个元素。原因是：从最小的1开始，每次加入新的元素都只依次增加1， 这样相加的和最小，要加到10，元素个数就最多。 求出最大的∣A i∣＝4后，再求出元素个数为3，2，1的集合就可以了。 故A={{10},{1,9},{2,8},{3,7},{4,6},{1,2,7},{1,3,6},{1,4,5},{2,3,5},{1,2,3,4}} 1.2 请用命题法给出下列集合
北京邮电大学——形式语言与自动机课后作业答案 第二章 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组成的所有字符串的集合
编译原理作业集-第三章-修 订版 -标准化文件发布号：（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
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 V P ∈∈→δγβα则称γαδ在G 中推导出了γβδ。 ? 归约：文法G = {V ，T ，P ，S}，如果,)(,,* T V P ∈∈→δγβα则称γβδ在G 中归约到γαδ。 ? 这他们的定义，我个人理解两个概念从不同角度看待文法中的产生式，推导是自上而下 （从产生式的左边到右边），而归约是自下而上（从产生式的右边到左边），体现到具体实际中，如编译中语法分析时语法树的建立，递归下降，LL （1）等分析法采用自开始符号向下推导识别输入代码生成语法树，对应的LR （1），LALR 等分析法则是采用自输入代码（相当于文法中语言的句子）自底向上归约到开始符号建立语法树，各有优劣。 （5）为什么要求定义语言的字母表上的语言为一个非空有穷集合？ ? 非空：根据字母表幂的定义：εε,}{0∑=为字母表中０个字符组成的。这样，当字母 表中没有字符的情况，字母表也有一个元素，字母表为空就没有意义，而且，如果字母表为空，将无法定义其上的语言，使得理论体系不严密。 ? 有穷：我们将语言抽象成形式语言的目的就是为了有穷的表示无限的语言，在此基础上 我们才定义了字母表和语言，如果字母表为无穷的，他就违背了我们研究问题的初衷，这也使得研究失去意义
第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如下：
形式语言与自动机作业参考答案（仅供参考） 第四章 2．最左推导：E→E+T→T+T→E+T→b+T→b+T/F→b+F/F→b+b/F→b+b/b 最右推导：E→E+T→E+T/F→E+T/b→E+F/b→E+b/b→T+b/b→F+b/b→b+b/b 8.(1)由题：S,D,E为有用非终结符，删去有关C的生成式，得：G1:S→ED,D→a,E→b (2)由题：S,D,E为有用非终结符，删去有关C的生成式，得：G2:S→D,D→bS|b,E→DS|b. 又E不可达，删去有关E得生成式，得：G2:S→D,D→bS|b 9．由题：N’={S,C,D,E},因为S∈N’，所以P1中加入生成式:S1→S|ε,变换后的无ε生成式的等价文法为：G1={N1,T,P1,S1} N1={S1,S,C,D,E} P1:S1→S|ε S→DCE,D→CC,C→EE|b,E→DD|a 10.把下列文法变换为无ε生成式、无单生成式和没有无用符号的等价文法： S →A1 | A2 , A1→A3 | A4 , A2→A4 | A5 , A3→S | b |ε, A4→S | a，A5→S | d |ε 解: ⑴由算法3，变换为无ε生成式： N’ = { S, A1,A2,A3,A4,A5 } G1 = ( { S1,S, A1,A2,A3,A4,A5 } , { a,b,d }, P1 , S1 ) ,其中生成式P1如下： S1→ε| S , S →A1 | A2 , A1→A3 | A4 , A2→A4 | A5 , A3→S | b , A4→S | a , A5→S | d , ⑵由算法4，消单生成式： N S1 = { S1,S,A1,A2,A3,A4, A5 } , N S = N A1 = N A2 = N A3 = N A4 = N A5 = { S, A1,A2,A3,A4, A5 } , 运用算法4，则P1变为： S1 →a | b | d |ε, S →a | b | d , A1→a | b | d , A2→a | b | d , A3→a | b | d , A4→a | b | d , A5→a | b | d ⑶由算法1和算法2，消除无用符号，得到符合题目要求的等价文法： G1 = ( { S1 } , { a,b,d } , P1 , S1 ) ，其中生成式P1为：S1→a | b | d |ε. 11. 设2型文法G = ( { S,A,B,C,D,E,F } , { a,b,c } , P , S ) ,其中P： S →ASB |ε; A →aAS | a ; B →SBS | A | bb 试将G变换为无ε生成式,无单生成式,没有无用符号的文法,再将其转换为Chomsky 范式. 解: ⑴由算法3，变换为无ε生成式：