形式语言与自动机理论蒋宗礼第三章参考答案

由于只关心0的个数的奇偶数我们可以把二进制串分成多段来考虑第为止这一段包含1个0并且0的前面有0对于剩下的二进制串按照每段包含两个0的方式去划分即以0开始以0结尾中间可以个或多个1如果一个二进制串被这样划分完后剩下的部分如果全部是全1串这些串在前面划分的串之间或最后则该二进制串就具有奇数个0所以该二进制可以这样描述
在整个分裂过程中，所有新结点均用不同的名字，保留 X 和 Y 为全图的唯一初态结点 和终态结点。至此，我们得到了一个非确定有限自动机Ｍ，
第二部分
例题与习题
重点与难点
重点：词法分析器的输入、输出，用于识别符号的状态转移图的构造，根据状态转移图实现 词法分析器。 难点：词法的正规文法表示、正规表达式表示、状态转移图表示，它们之间的转换。
l, d 初态 ① ｌ
②
其它
终态
③
例 4 叙述下面的正规式描述的语言，并画出接受该语言的最简 DFA 的状态转换图。 * * (1|01) 0 【解】描述的语言是，所有不含子串 001 的 0 和 1 的串。
例 5 给定如下正规式 0(0|1)*1 (1) 写出相应的正规文法。 (2) 画出相应的状态转移图。 【解】 （1） 引入非终结符 S, A， S → 0(0|1)*1 →0A + + A →(0|1)*1→(ε | (0|1) )1→1| (0|1) 1→1| (0|1) (0|1)*1→1| 0A|1A 得到正规文法 G[S]: S 0A A 0A|1A|1 （2） （１）中给出的是一个右线性文法。 。 按照由右线性正规文法构造状态转换图的方法,构造相应的状态转移图如图 1
则（U|V） 、 （U·V）和（U)*也都是正规式，它们所表示的正规集分别为 L（U) ∪L（V)、 L (U) L (V)（连接积）和(L (U))*（闭包） 。 仅通过有限次使用上述三步骤定义的表达式才是∑上的正规式， 仅由这些正规式所表示 的字集才是∑上的正规集。 令 U、V 和 W 均为正规式，则下述关系成立： （1）U|V=V|U（交换律） (2）U|(V|W)=(U|V)W 或 U(VW)=(UV)W （结合律） (3）U(V|W)=UV|UW 或 （V|W）U=VU|WU（分配律） (4）ε U=Uε =U 若两个正规式所表示的正规集相同，则认为二者等价。 例如：b(ab)*=(ba)*b, (a|b)*=(a*b*）*。 注意： a*b*、(a|b)* 、(ab)* 、a*|b*相互都不等价，它们表示的含义如图所示

P2
9.对应图（a）(b)的状态转换图写出正则式。（图略） （1） 由图可知 q0=aq0+bq1+a+ε
q1=aq2+bq1 q0=aq0+bq1+a =>q1=abq1+bq1+aaq0+aa =(b+ab) q1+aaq0+aa =(b+ab) *( aaq0+aa)
=>q0=aq0+b(b+ab) *( aaq0+aa ) +a+ε
(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
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
P: S→aS S→bS S→ε
(2) 右线性文法 G=({S},{a,b},P,S)
P: S→aS S→bS S→abb

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

Chapter 3 练习参考解答Exercise 3.1.1 写出下列语言的正规表达式:c） The set of strings of 0' s and1' s with at most one pair of consecutive 1' s.c）最多包含两个相继的 1 的所有0， 1 字符串的集合.参考解答：该题的翻译有二义性（Sorry ）.1）按原题意的解法对不包含相继的 1 的所有0， 1 字符串的集合，正规表达式可以为：1*（0+01）* 或（0+10 ）*1*；包含最多一对相继的1，正规表达式可以为：（0+10）*11（0+01）*；所以，结果正规表达式可以为：1*（0+01）* + （0+10 ）*11（0+01）2）若理解为11 可以出现多次的解法正规表达式可以为：1*（0+01+011 ）* 或（0+10+110）*1*；等等Exercise 3.1.2 写出下列语言的正规表达式:b） 0 的个数能够被 5 整除的所有0， 1 字符串的集合. 参考解答：该题问题不多.正规表达式可以为：（1*01*01*01*01*01* ）*Exercise 3.2.1（2）c）给出所有正规表达式R（i2j）, 并尽可能简化之.d）给出该自动机的语言的一个正规表达式.参考解答：该题问题反映较多的是关于正规表达式的简化. 本科程较侧重原理，技术方面不够细致，因此对于“最简“的正规表达式没有作明确的规定，也没有类似于命题演算中有关”范式“的讨论.同学们在做题时除了应用有关定律外， 还可以自己总结出一些规律，比如一个表达式的语言 R 是另一个表达式S 所代 表语言的一个子集，则对于 R+S 就可以消去R ，例如 +1*可以简化为1*.再 如，在已做过的习题中出现的公式，例如Exercise3.4.1(g)我们可以验证(汁R)*= R*，因此 (+1)*可以简化为1*.综合已阅过的作业，推荐以下结果：C) R (121)= 1*+1*0 ( +11*0)*11* = 1*+1*0(11*0)*11*R (1 2 = 1*0+1*0 ( ；+11*0)* ( ；+11*0) = 1*0(11*0)*R (123)= * +1*0 2+11*0)*0 = 1*0(11*0)*0R (221)= 11* + ( +11*0) ( +11*0)*11* = (11*0)*11* R (222)= +11*0 + ( +11*0) ( ；+11*0)* ( ；+11*0) = (11*0)*R (223)= 0 + ( +11*0) ( +11*0)*0 = (11*0)*0R (321) = * + 1 (<+11*0)*11* =1(11*0)*11*R (322)= 1 + 1 ( +11*0)* ( ；+11*0) =1(11*0)*R (323)= ； + 0 + 1 ( +11*0)* 0 = ； + 0 + 1(11*0)*0d)该自动机的语言的一个正规表达式为R (133) =1*0(11*0)*0 +1*0(11*0)*0 ( ； + 0 + 1(11*0)*0)* ( ； + 0 + 1(11*0)*0)=1*0(11*0)*0 (0 + 1(11*0)*0)*Exercise 3.2.3 使用状态消去技术，将如下 DFA 转化为一个正规表达式.参考解答：该题问题不多，状态消去的次序不同，结果形式上可能有所不同，但 相互之间是等价的.以下是一个解法:/1+0(01+10*11)*(00+10*10) Start 5结果正规表达式可以为：(1+0(01+10*11)*(00+10*10))* 原状态图:消去状态r :消去状态s :1Start 0Exercise 324 将下列正规表达式转化为带 &转移的NFA.b) (0+1)01 c) 00(0+1)*参考解答：若严格按照所介绍的算法构造，则结 果如下:b)Exercise 3.4.1验证下列包含正规表达式的等式 c) (RS) T = R (ST) .g)(+R)* = R* . 参考解答：c)将两个表达式具体化，将R 替换为a ，将S 替换为b.(RS)T 具体化为(ab)a ，R(ST)具体化为 a(ba)，而 L((ab)a)=L(a(ba))={abc}， 所以原等式成立；g)将两个表达式具体化，将R 替换为a.(+R)* 具体化为(；+a)*，R*具体化为 a*，而 L(( +a)*)=L(a*)={ ,a ,aa,aaa,…， (注：严格证明L(( ；+a)*)=L(a*)，可以在归纳证明：对任意k>=0，{；，a}k ={a}k 的基础上进行)，所以原等式成立;Exercise 342证明或否证下列关于正规表达式的命题 b) (RS+R)*R = R (SR+R)*.d) (R+S)*S = (R*S)* .Start参考解答：b)将两个表达式具体化，将R替换为a,将S替换为b.(RS+R)*R 具体化为(ab+a)*a，R (SR+R)*具体化为a(ba+a)*，可以证明L((ab+a)*a)=L(a(ba+a)*) (注：同上，可以先归纳证明：对任意k>=0，{ab，a}k{a}={a}{ba ，a}k，而由连接运算对-运算的分配律，—k —k 可知L((ab+a)*a)= *0,1,2, -({ab，a} {a}), L(a(ba+a)*)= k=o,1,2, ・({a}{ba，a})，由此证得L((ab+a)*a)=L(a(ba+a)*))，所以原等式成立；g)将两个表达式具体化，将R替换为a，将S替换为b.(R+S)*S 具体化为(a+b)*b，(R*S)* 具体化为(a*b)*，由于〉L((a*b)*)，而>■' L((a*b)*)，所以原等式不成立。

形式语言与自动机蒋宗礼答案形式语言与自动机蒋宗礼答案【篇一：形式语言第四章参考答案(蒋宗礼)】p> 解：所求正则表达式为：(0+1)*。

+⑵ {0, 1}。

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

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

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

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

++ +q1为终态时的正则表达式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)* q2为终态时的正则表达式：0*11*0((10)*(111*11*0)*(00*11*0)*)*q3为终态时的正则表达式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)* q4为终态时的正则表达式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)* 将以上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可以作为终态。

由题设，x=0时，│x│=1，模5是1，不符合条件，所以不必增加关于它的状态。

下面对每一个状态考虑输入0和1时的状态转移。

q: 输入1，模5是1，进入q1。

+q0: 设x=5n。

输入0，x=5n*2=10n，模5是0，故进入q0输入1，x=5n*2+1=10n+1，模5是1，故进入q1q1：设x=5n+1。

输入0，x=(5n+1)*2=10n+2，模5是2，故进入q2输入1，x=(5n+1)*2+1=10n+3，模5是3，故进入q3 q2：设x=5n+2。

形式语言与自动机答案蒋宗礼【篇一：形式语言第四章参考答案(蒋宗礼)】p> 解：所求正则表达式为：(0+1)*。

+⑵ {0, 1}。

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

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

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

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

++ +q1为终态时的正则表达式：0*1(1*(0(10)*111*1)*(0(10)*00*1)*)* q2为终态时的正则表达式：0*11*0((10)*(111*11*0)*(00*11*0)*)*q3为终态时的正则表达式：0*11*0(10)*1(11*11*0((10)*(00*11*0)*)*1)* q4为终态时的正则表达式：0*11*0(10)*11(1*(11*0((00*11*0)*(10)*)*11)*)*将以上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可以作为终态。

由题设，x=0时，│x│=1，模5是1，不符合条件，所以不必增加关于它的状态。

下面对每一个状态考虑输入0和1时的状态转移。

q: 输入1，模5是1，进入q1。

+q0: 设x=5n。

输入0，x=5n*2=10n，模5是0，故进入q0输入1，x=5n*2+1=10n+1，模5是1，故进入q1q1：设x=5n+1。

输入0，x=(5n+1)*2=10n+2，模5是2，故进入q2输入1，x=(5n+1)*2+1=10n+3，模5是3，故进入q3 q2：设x=5n+2。

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

(吴贤环02282047)(1){0, 1}*。

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

(2){0, 1}\解：所求正则表达式为:(0+1几(3){ x | xe {0, 1甘且x中不含形如00的子串}o解：根据第三章构造的FA,可得所求正则表达式为：1*(0广)*(01+0+1)。

(4){ X I xe {0, 1}*且X中不含形如00的子串}。

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

(5){ x | xG{0, 1}+且x中含形如10110的子串}。

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

(6){ x | xe {0, 1}^且x中不含形如10110的子串}。

解：根据第三章的习题，接受x的FA为：要求该FA对应的正则表达式，分别以q。

、q】、q2> q3> q(为终结状态考虑：qo为终态时的正则表达式:(0*( 11 *0( 10)*( £ +111*11*0(10)*)0)*)*qi 为终态时的正则表达式:0*1(1*(0(10)*111*1)*(0(10)*00*1)*)* q?为终态时的正则表达式:0* 11*0(( 10)*( 111*11 *0)*(00* 11 *0)*)*q3 为终态时的正则表达式:0* 11 *0( 10)* 1 (11 * 11 *0(( 10)*(00* 11 *0)*)* 1 )*q，i 为终态时的正则表达式:0* 11 *0( 10)* 11 (1 *( 11 *0((00* 11 *0)*( 10)*)* 11)*)* 将以上5个正则表达式用“ + ”号相连，就得到所要求的正则表达式。

(7){ x | xe {0, 1广且当把X看成二进制数时,x模5与3同余和X为0时，I x I =1 且xHO时,x的首字符为1}。

解：先画出状态转移图，设置5个状态q。

2.4 文法的类型 2.4.2 正规文法和正规语言
定理：L 是 RL 的充分必要条件是存在一 个文法，该文法产生语言L,并且产生式 的形式是： A→aB,A→a or A→Ba,A→a 其中 A,B∈V, a∈T.
第二章 文法
2.4 文法的类型 2.5 空语句 定义：假设G=(V,T,P,S)是一个文法。如 果 S 不出现在 G 的任何产生式的右部， 则P∪{S→ε}所形成的文法仍然是与G 等价的相应类型的文法，所产生的语言 是相应类型的语言。
第二章 文法
2.2 文法的形式定义 2.2.3 语言
定义：设文法 G = (V,T,P,S)。对 α∈(V∪T)*， 如果S(⇒)*α , 则α为文法G的一个句型； 若对w∈T*，如果 S(⇒)* w，则 w 称为由 G 产生的一个句子。 称 L(G)={w| w ∈T*, S(⇒)* w}为文法 G 产 生的语言。
第一章 绪论
1.4 语言
1.4.3 基本概念 （1）符号 （2）字母表 （3）字符串 （4）语言 Σ
①乘积运算 字母表的运算 ②幂运算 ③闭包运算
第二章 文法
2.1 文法的引入
例1 汉语中的句子：王平和李新是大学生。 它由两个短语组成： 〈主语〉 王平和李新 〈谓语〉 是大学生
该句子可以应用下列规则构成：
3.2 有限状态自动机的形式定义 （4）到达某状态的字符串集合 定义：设 FA M=(Q,∑,δ,q0,F)， 对 ∀q∈Q 能从开始状态到达所输 入的字符串集合为： set(q)={x|x∈∑*,并且δ(q0,x)= q}
第三章 有限状态自动机
3.2 有限状态自动机的形式定义 （5）有限状态自动机等价 假设 M1,M2 是 FA， 如果 L(M1)=L(M2)，则 M1 与 M2 等价。

[S] [A] [S,B]
ab
[A]
[S,B]
2
[A]
初态 : [S] 终态 : [S,B] (a) 确定化后的状态矩阵
ab
1
2
3
3
2
初态 : 1 终态 : 3 (b) 改名后的状态矩阵
a
1
2
b 3
a (c) DFA M ′的状态转换图
答案图 3-4-(3)
现将 DFA M′最小化：
( ⅰ) 初始分划由两个子集组成，即
3-3 对于如下的状态转换矩阵：
ab
S
AS
AAB
B
BB
ab S
ABA B
AB BB
( ⅰ ) 初态 : S 终态 : B
( ⅲ ) 初态 : S 终态 : B
ab
S
AB
A
CA
BBC
C
CC
ab S
ACB BBC
C
AS CC
( ⅱ ) 初态 : S 终态 : A,C
( ⅳ ) 初态 : S 终态 : C
答案图 3-3
a, b C
(2) 相应的 3 型文法为：
( ⅰ ) S →aA|bS
A→aA|bB| b
B→ aB|bB|a|b
( ⅱ) S →aA|bB| a源自A→bA|aC| a|bB→aB|bC| b
C→ aC|bC|a|b
( ⅲ) S →aA|bB| b A→aB|bA| a
B→aB| bB|a|b
**
(2) b|a(aa b) b
NFA。
3-8 构造与正规式 (a|b) *(aa|bb)(a|b) * 相应的 DFA。
第 3 章 习题答案

形式语言与自动机形式语言与自动机理论-蒋宗礼-第三章参考答案导读：就爱阅读网友为您分享以下“形式语言与自动机理论-蒋宗礼-第三章参考答案”的资讯，希望对您有所帮助，感谢您对的支持!因此我们只需要证明对任何的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&#39;?Q1且?b??,?1(q&#39;,b)=q,就构造?2（q&#39;,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章绪论11.1集合的基础知识21.1.1集合及其表示21.1.2集合之间的关系51.1.3集合的运算61.2关系121.2.1二元关系121.2.2等价关系与等价类131.2.3关系的合成141.2.4递归定义与归纳证明151.2.5关系的闭包181.3图191.3.1无向图191.3.2有向图211.3.3树231.4语言241.4.1什么是语言241.4.2形式语言与自动机理论的产生与作用25 1.4.3基本概念281.5小结35习题35第2章文法422.1启示432.2形式定义482.3文法的构造582.4文法的乔姆斯基体系682.5空语句792.6小结82习题82第3章有穷状态自动机863.1语言的识别863.2有穷状态自动机893.3不确定的有穷状态自动机1023.3.1作为对DFA的修改1023.3.2NFA的形式定义1043.3.3NFA与DFA等价1063.4带空移动的有穷状态自动机1103.5FA是正则语言的识别器1153.5.1FA与右线性文法1153.5.2FA与左线性文法1203.6FA的一些变形1223.6.1双向有穷状态自动机1223.6.2带输出的FA1233.7小结125习题126第4章正则表达式1314.1启示1314.2正则表达式的形式定义1334.3正则表达式与FA等价1354.3.1正则表达式到FA的等价变换1354.3.2正则语言可以用正则表达式表示1444.4正则语言等价模型的总结1504.5小结152习题153第5章正则语言的性质1565.1正则语言的泵引理1565.2正则语言的封闭性1625.3Myhill Nerode 定理与DFA的极小化170 5.3.1Myhill Nerode 定理1705.3.2DFA的极小化1805.4关于正则语言的判定算法1895.5小结190习题191第6章上下文无关语言1946.1上下文无关文法1956.1.1上下文无关文法的派生树1956.1.2二义性2026.1.3自顶向下的分析和自底向上的分析2056.2上下文无关文法的化简2076.2.1去无用符号2086.2.2去ε 产生式2126.2.3去单一产生式组2166.3乔姆斯基范式2196.4格雷巴赫范式2236.5自嵌套文法2296.6小结230习题230第7章下推自动机2357.1基本定义2357.2PDA与CFG等价2427.2.1PDA用空栈接受和用终止状态接受等价243 7.2.2PDA与CFG等价2467.3小结257习题257第8章上下文无关语言的性质2608.1上下文无关语言的泵引理2608.2上下文无关语言的封闭性2678.3上下文无关语言的判定算法2738.3.1L空否的判定2738.3.2L是否有穷的判定2748.3.3x是否为L的句子的判定2768.4小结278习题278第9章图灵机2809.1基本概念2819.1.1基本图灵机2829.1.2图灵机作为非负整函数的计算模型2899.1.3图灵机的构造2939.2图灵机的变形3009.2.1双向无穷带图灵机3009.2.2多带图灵机3049.2.3不确定的图灵机3069.2.4多维图灵机3089.2.5其他图灵机3109.3通用图灵机3139.4几个相关的概念3159.4.1可计算性3159.4.2P与NP相关问题3169.5小结316习题317第10章上下文有关语言32010.1图灵机与短语结构文法的等价性32010.2线性有界自动机及其与上下文有关文法的等价性323 10.3小结325习题325附录A教学设计327附录B缩写符号338词汇索引340参考文献348。

编译原理蒋宗礼课后答案
编译原理练习
一、对下列语言集合设计CFG， ={a,b}
(1)L={a n b m a2n|n,m>=0}。

(2)所有非空符号串，其首尾字符相同。

(3)所有a的个数大于b的个数的符号串。

(4)由a,b组成的回文串。

二、(1)构造一个能识别所有除以5余2的二进制数的DFA
(2)假设有一自动售货机，接收1元、2元、3元的硬币，出售2元和4元的商品，多投不找零，请构造能实现此功能有限自动机。

三、对于文法G[S]，（1）给出至少两个理由说明它不是LL(1)文法。

（2）将文法改写为LL(1)文法，并计算改造后文法的各非终结符的First和Follow集合，构造其预测分析表。

S→bAb|bBa
A→aS|CB
B→b|BC C→c|cC。

一个非确定有限自动机（NFA）M 是一个五元式：M=（Q, ∑ ,f，s0,Z） 。 在确定有限自动机的描述中，(1） 、 （2） 、(5）同确定有限自动机，而(3)为：f 是一个 * 以 Q× ∑ 到 Q 的子集的映射，即 f:S×∑*→2Q。 。 显然，一个含有 m 个状态和 n 个输入字符的非确定有限自动机可表示成一张状态图， 该图含有 m 个状态结点，每个结可射出若干条有向弧与别的结点相连接，每条弧用∑*中的 一个字（不一定要不同的字且可以是空字ε ）作标记（称为输入字） ，整个图至少含有一个 初态结点以及若干个 （可以是 0 个） 终态结点， 某些结既可以是初态结点又可以是终态结点。 注意：DFA 是 NFA 的特例。对于每个非确定有限自动机 M，存在着一个确定有限自动机 M`，使得 L（M）=L（M`） ，即两个有限自动机等价。
任何地方出现，所以本题只需要考虑一种情况，另外一种情况也可以类似求得。考虑包含奇 数个 0 的字符串：由于只关心 0 的个数的奇偶数，我们可以把二进制串分成多段来考虑，第 1 段为二进制串的开始到第 1 个 0 为止， 这一段包含 1 个 0， 并且 0 的前面有 0 个或多个 1， 对于剩下的二进制串按照每段包含两个 0 的方式去划分，即以 0 开始，以 0 结尾，中间可以 有 0 个或多个 1，如果一个二进制串被这样划分完后，剩下的部分如果全部是全 1 串（这些 全 1 串在前面划分的串之间或最后） ，则该二进制串就具有奇数个 0，所以该二进制可以这 ＊ ＊ ＊ 样描述：以第 1 段（1 ） ）开始，后面由全 1 串（1 ）以及包含两个 0 的串（01 0）组成， ＊ ＊ ＊ ＊ ＊ 所以包含奇数个 0 的正规表达式为：1 0（1｜01 0） ，本题的解答则是：1 0（1｜01 0） ＊ ＊ ＊ ＊ ｜0 1（0｜10 1） 。 例 8 语言 L 是所有由偶数个 0 和偶数个 1 组成的句子的集合，给出定义 L 的正规文法。 【解】解题思路： 这道题可以从状态转换图着手，由于每读入 1 个“0” ， “0”的个数的奇偶数就会变，每 读入 1 个“1” ， “1”的个的奇偶数也会改变，因此本题可以引入 4 个状态，分别代表偶数个 “0”和“1” 、奇数个“0”和“1” 、奇数个“1”偶数个“0”和奇数个“0”偶数个“1” ， 那么，能接受语言 L 的状态转换图如下图 3 所示。

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

3.1 语言的识别
• 相应的物理模型
一个右端无穷的输入带。 一个有穷状态控制器(finite state control,FSC) 。 一个读头。
• 系统的每一个动作由三个节拍构成：读入 读头正注视的字符；根据当前状态和读入 的字符改变有穷控制器的状态；将读头向 右移动一格。
3.1 语言的识别
• 有穷状态自动机的物理模型
3.2有穷状态自动机
• M接受(识别)的语言
对于x∈∑*如果δ(q，w)∈F，则称x被M接受， 如果δ(q，w)F，则称M不接受x。 L(M)={x| x∈∑*且δ(q，w)∈F}
称为由M接受(识别)的语言 L(M1)= L(M2)={02n|n≥1}
• 如果L(M1)=L(M2)，则称M1与M2等价。
• 状态转移图又可以叫做状态转换图。
3.2有穷状态自动机
• 例 3-3构造一个DFA，它接受的语言为 {x000|x∈{0，1}*}。
–状态q0读到的0可能是输入字符串的最后三个0 的第1个0；
–在状态q1紧接着读到的0可能是输入字符串的 最后三个0的第2个0；
–在状态q2紧接着读到的0可能是输入字符串的 最后三个0的第3个0；
3. John E Hopcroft, Jeffrey D Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publishing Company, 1979
第3章 有穷状态自动机
3.2有穷状态自动机
• 例 3-1 下面是一个有穷状态自动机
M1=({q0，q1，q2}，{0}，δ1，q0，{q2}) 其中，δ1(q0,0)= q1，δ1(q1,0)= q2，δ1(q2,0)= q1 用表3-1表示δ1。

ij求索-百度文库2.1回答下面的问题：（周期律02282067）（1）在文法中，终极符号和非终极符号各起什么作用？/终结符号是一个文法所产生的语言中句子的中出现的字符,他决上了一个文法的产生语言中字符的范围。

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

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

（4）文法中的归约和推导有什么不同？/ 推导：文法G = {V, T, P, S},如果则称gd在G中推导岀了汐5。

/ 归约：文法G={V, T, P, S},如果则称汐5在G中归约到*7》。

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

（5）为什么要求左义语言的字母表上的语言为一个非空有穷集合？/ 菲空：根据字母表幕的立义：工°={£},£为字母表中0个字符组成的。

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

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

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

Sq q1图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（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个等价类。