第四章
Chomsky文法体系及语言之间的运算
? 在第一章中已指出对于程序的语法分析和自然
语言的处理，形式化的文法描述方式起了重要
的作用。本章介绍 Chomsky的文法体系，语言
的运算和运算的封闭性。
? 4.1 Chomsky的文法体系
? 4.1.1 文法的分类及文法之间的关系
? 对于一般的短语结构文法 PSG=(∑,V,S,P)，
产生式的形式是 v→w,其中,v∈ (∑UV)+，且
至少包含一个非终结符； w∈ （ ∑ U V） * 。
? 定义 4-1 右线性文法的定义
? 对于文法 G=(∑,V,S,P)，若它的每个产生式
都是下列形式之一：
? A→xC 或者 A→y ；
? 其中,A,C∈ V,x∈ ∑*,y∈ ∑+；
? 则文法 G是右线性文法（也称为正则文法 RG）。
? 如果一个语言 L可以由右线性文法产生，则该语
言是右线性语言。
? 定义 4-2 上下文无关文法的定义
? 对于文法 G，如果对于 G中的任意产生式 ν→ω,
而 ν只是一个非终结符，即 A→ω, A∈ V,ω∈
（ ∑ U V） *，则称文法 G为上下文无关文法
CFG（简称无关文法）。
? 如果一个语言能由一个无关文法产生，则称这
个语言是上下文无关语言（简称无关语言）。
? 定义 4-3 上下文相关文法的定义
? 对于文法 G，如果 G的每个产生式形如 u→v,且
0<|u|≤|v|；但若 ε∈ L(G)，则允许有 S→ε,且 S不出
现在任何产生式的右边；则称文法 G为上下文相关文
法 CSG（简称相关文法）。
? 如果一个语言能由一个相关文法产生，则称这个语言
是上下文相关语言（简称相关语言）。
? 根据以上的两个定义，可以看出，一个无关的文法不
一定是相关的文法，主要是空串产生式的情况。
? 某些文法不满足上述 3类文法的要求；如
? S→AB1
? AB→0
? 该文法不是右线性文法，不是无关文法，也不是
相关文法，只能属于短语结构文法。
? Chomsky将文法分为四类，关系为：
? 任意一个右线性文法本身是一个无关文法；本身
不一定是相关文法；
? 任意一个无关文法本身不一定是相关文法；
? 设文法 G=(∑,V,S,P)，则判断 G是哪类文法的方法如下：
? 1,G是短语结构文法；
? 2、如果所有产生式都有右边部分长度大于等于左边部分，那么
G是上下文有关文法；
? 3、如果如果所有产生式的左边部分都是单个非终极符号，那么
G是上下文无关文法；
? 4、如果所有产生式的右边部分都是以终极符号开始、含有至多
一个非终极符号、如果有非终极符号则出现在最右边，那么 G
是正则文法。
? 4.1.2语言之间的关系
? 下面讨论语言之间的关系。
? 任意一个右线性语言文法本身是一个无关语言；
? 一个上下文无关语言是不是一个上下文相关语言呢？
? 从第二章可知：一个无关文法
? ①没有任何空串产生式，或者
? ②仅有一个空串产生式 S→ε,且 S不出现在任何产生式的右
边
? 则该文法本身就是一个相关文法；它产生的无关语言也就是
一个相关语言；那么，如果一个无关文法中有一般的空串产
生式（如 A→ε, A是一个非终结符，且不是开始符号），它
产生的无关语言是不是相关语言呢？
? 根据空串定理：
? G是一个上下文无关文法，存在一般的空串产生式 A→ε,则
存在另一个上下文无关文法 G′使得：
? ⑴ L(G)=L(G′)；
? ⑵若 ε！ ∈ L(G)，则 G′中没有任何空串产生式；
? ⑶若 ε∈ L(G)，则 G′中有一个空串产生式,S′→ε,且 S′不出
现在 G′的其它任何产生式的右边；（ S′是 G′开始符号）
? 实际上,G’是一个无关文法。也是一个相关文法。
? 即：任意一个无关文法都可以改造为等价的一个相关文法，
所以，任意一个无关语言也是一个相关语言。
? 结论 4-4 Chomsky的文法体系：
? 对于文法 G=（ ∑,V,S,P），根据对产生式
的不同限制,Chomsky将文法分为四类：
? 文法 G是 3型文法，即右线性文法；
? 文法 G是 2型文法，即上下文无关文法；
? 文法 G是 1型文法，即上下文相关文法；
? 文法 G是 0型文法，文法对产生式没有任何限制；
? 语言的分类是根据产生该语言的文法的分类进行的。若一个
语言 L由某个 i型文法产生，则它是 i型语言。 i=0,1,2,3。即
? 语言 L是 3型语言，即右线性语言；若 L能由某个 3型文法产
生。
? 语言 L是 2型语言，即上下文无关语言；若 L能由某个 2型文
法产生。
? 语言 L是 1型语言，即上下文相关语言；若 L能由某个 1型文
法产生。
? 语言 L是 0型语言，即短语结构语言 (PSL)或递归可枚举集，
若 L能由某个 0型文法产生。
? 定义 4-5 文法分类定义
? 用 Ψi（语言类）的概念来定义所有的 i型语言；对
于 0≤i≤3
? Ψ i ={LС∑*|L=L（ G）,G是 i型文法 }。
? 定理 4-6 语言分类定理
? Chomsky将语言分为四类，且有包含关系（真子集
关系）：
? Ψ3СΨ2СΨ1 СΨ0
? 4.2 Chomsky的文法体系另一种描述
? 目前，国内普遍对 Chomsky的文法体系存在另外
一种描述方式，该方式限制了一般的空串产生式
的使用。
? 对于一般的短语结构文法,G=(∑,V,S,P)：
? G称为 0型文法，或短语结构文法 (PSG)。对应的
L(G)叫作 0型语言或者短语结构语言 (PSL)、递归
可枚举集。
? 如果对于任意 ????P，均有 |?|≥|?|成立，则称 G为 1型文法，
或上下文有关文法 (CSG)。对应的 L(G)叫作 1型语言或者上下
文有关语言 (CSL)。
? 如果对于任意 ????P，均有 |?|≥|?|且 ??V成立，则称 G为 2
型文法，或上下文无关文法 (CFG)。对应的 L(G)叫作 2型语言
或者上下文无关语言 (CFL)。
? 如果对于任意 ????P,???均具有形式 A?w,A?wB,其中，
A,B?V,w?T+，则称 G为 3型文法，也可称为正则文法 (RG)
或正规文法。对应的 L(G)叫作 3型语言，也可称为正则语言
或正规语言 (RL)。
? 正规语言类包含于上下文无关语言类，上下文无关
语言类包含于上下文相关语言类，上下文相关语言
类包含于递归可枚举语言类。这里的包含都是集合
的真包含关系，也就是说：存在递归可枚举语言不
属于上下文相关语言类，存在上下文相关语言不属
于上下文无关语言类，存在上下文无关语言不属于
正规语言类。
? 四类文法和对应的四类语言之间都有包含关系。
? 定理 4-7
? L 是 RL 的充要条件是存在一个文法，该文法产生语言
L,并且它的产生式要么是形如 A?a 的产生式，要么
是形如 A?aB 的产生式，其中 A,B 为语法变量,a
为终极符号。
? 证明：
? 参考定理 2-15的证明。
? 定义 4-8 线性文法的定义。
? 设文法 G=(∑,V,S,P)。如果对于 ?????P,???均具有
如下形式,A?w,A?wBx，其中,A,B?V,w,x?T*，则称 G
为线性文法。对应地,L(G)叫作线性语言。
? 设文法 G=(∑,V,S,P)。如果对于 ?????P,???均具有
如下形式,A?w,A?wB，其中,A,B?V,w?T+，则称 G为
右线性文法。对应地,L(G)叫作右线性语言。
? 设文法 G=(∑,V,S,P)。如果对于 ?????P,???均具有
如下形式,A?w,A?Bw，其中,A,B?V,w?T+，则称 G为
左线性文法。对应地,L(G)叫作左线性语言。
? 定理 4-9 L 是一个左线性语言的充要条件是存在文
法 G,G 中的产生式要么是形如 A?a 的产生式，
要么是形如 A?Ba 的产生式，且 L(G)=L。 其中 A、
B 为语法变量,a 为终极符号。
? 证明：
? 读者自行完成。
? 定理 4-10 左线性文法与右线性文法等价。
? 证明：
? 读者自行完成。
? 结论：
? 对于任意右线性文法 G，能够构造出对应
的左线性文法 G’,使得 L(G’)=L(G)。
? 对于任意左线性文法 G，能够构造出对应
的右线性文法 G’,使得 L(G’)=L(G)。
? 定义：形如 A??的产生式叫作空产生式，也可叫作 ?产生式。
? 根据文法分类的定义，在 RG,CFG,CSG中，都不能含有
空产生式，所以任何 CSL中都不包含空语句 ?。
? 空语句 ?在一个语言中的存在并不影响该语言有穷描述的存
在，因为除了为生成空语句 ?外，空产生式可以不被用于语
言中其他任何句子的推导中。
? 当允许 CSL,CFL,RL包含空语句后，还会为问题的处理提
供一些方便。
? 假设允许 RG,CFG,CSG中含有空产生式，也就允许
CSL,CFL,RL中包含空语句 ?。
? 空语句不影响文法的类型。
? 定义 4-11 设 G=(V,T,P,S)为一个文法，如果 S不出现
在任何产生式的右部，则
? (1)如果 G是 CSG，则仍然称 G=(V,T,P∪ {S??},S)为
CSG； G产生的语言仍然称为 CSL。
? (2)如果 G是 CFG，则仍然称 G=(V,T,P∪ {S??},S)为
CFG； G产生的语言仍然称为 CFL。
? (3)如果 G是 RG，则仍然称 G=(V,T,P∪ {S??},S)为
RG； G产生的语言仍然称为 RL。
? 限制条件, S不出现在任何产生式的右部, 的作用
是什么呢？
? 设正则文法 G,S?ab|aS，那么 L(G)={a+b}。加
入 S??后,L(G’)={a+b,?,a}。不仅产生了空语句
?，还产生了语句 a。
? 定理 4-12
? 设 G=(∑,V,S,P)为一个文法，则存在与 G同
类型的文法 G’=(∑’,V’,S’ P’),使得 L(G)=L(G’)，
但 G’的开始符号 S’不出现在 G’的任何产生式的
右部。
? 证明：
? 先根据 G构造满足条件的 G’，然后证明两者等价。
? 取 G’=(∑,V∪ {S’},S’,P’)，其中
P’=P∪ {S’??|S???P},G’与 G有相同的类型。
? 如果 S不出现在 P中任何产生式的右边，那么效果相当于
仅仅用 S’代换 S,P’中产生式实际上与 P中完全相同。
? 先证 L(G’)?L(G)。对 ?x?L(G’)，在 G’中存在如下推导：
S’???x，那么在 G中存在如下推导：
? S???x，故 x?L(G)。
? 再证 L(G)?L(G’)。对 ?x?L(G)，在 G中存在如
下推导,S???x，那么在 G’中存在如下推导：
S’???x，故 x?L(G)。
? 综上所述,L(G)=L(G’)。
? 结论：
? 加入空语句不影响语言的类型
? 定理 4-13 下列命题成立
? (1)如果 L是 CSL，则 L∪ {?}仍然是 CSL。
? (2)如果 L是 CFL，则 L∪ {?}仍然是 CFL。
? (3)如果 L是 RL，则 L∪ {?}仍然是 RL。
? 证明：
? 证明第 (1)个定理,(2)(3)同理可证。
? 设 L是 CSL，则存在一个 CSG=(∑,V,S,P)，使得 L(G)=L。由前
面的预备定理，不妨设 S不出现在 G的任何产生式的右部。取
G’=(∑,V,S,P∪ {S??})，则 G’也是 CSG。
? 由于 S不出现在 G中任何产生式的右部，所以 S??不可能出现在任
何长度不为 0的句子的推导中，因此 L(G’)=L(G)∪ {?}。
? 因此 L(G)∪ {?}是 CSL。证毕。
? 结论：
? 去掉空语句不影响语言的类型。
? 定理 4-14 下列命题成立
? (1)如果 L是 CSL，则 L-{?}仍然是 CSL。
? (2)如果 L是 CFL，则 L-{?}仍然是 CFL。
? (3)如果 L是 RL，则 L-{?}仍然是 RL。
? 证明：
? 证明第 (1)个定理,(2)(3)同理可证。
? 设 L是 CSL，则存在一个 CSG=(∑,V,S,P)，使得 L(G)=L。如果 ??L，
则 L-{?}=L，所以 L-{?}仍然是 CSL。
? 由前面的定理，不妨设 S不出现在 G的任何产生式的右部。取 G’=(V,T,P-
{S??},S)，则 G’也是 CSG。
? 由于 S不出现在 G中任何产生式的右部，所以 S??不可能出现在任何长度
不为 0的句子的推导中，因此 L(G’)=L(G)-{?}。
? 因此 L(G)-{?}是 CSL。证毕。
? 4.3 语言之间的运算及运算的封闭性
? 产生复杂语言的方法之一是对简单的语言进行
语言的运算。
? 4.3.1 语言之间的基本运算
? 定义 4-15 语言的运算的定义
? 若语言 L1和 L2是同一字母表 ∑上的两个语言，定
义
? 语言 L1和 L2的联合运算为：
? L1UL2={w|w∈ L1或者 w∈ L2}
? 语言 L1和 L2的连接运算为：
? L1L2={w|w=w1w2,w1∈ L1,w2∈ L2}
? 语言 L1的迭代运算（或者星运算，闭包运算）
为：
? L1*={w|w=w1w2w3… wm,wi∈ L1，
m≥0 }
? =UL1n 对 n≥0
? 其中：
? L10={ε}
? L11 =L1
? L1n+1= L1L1n 对 n≥1
? 注意,
? 语言 L1={an|n>0},L2={bn|n>0}，则 L1L2是
{anbm|n,m>0}；而不是是 {anbn|n>0}。
? 封闭性：如果任意的、属于某一语言类的语言在某一特
定运算下所得到的结果仍然是该类语言，则称该语言类
对此运算具有封闭性 (closure property)。
? 有效封闭性：给定一个语言类的若干个语言的描述。如
果存在一个算法，它可以构造出这些语言在给定运算下
所获得的运算结果的相应形式的语言描述，则称此语言
类对相应的运算是有效封闭的，并称此语言类对相应的
运算具有有效封闭性 (valid closure property)。
? 语言的封闭性可以用于证明某些语言属于某类语言，以
及可以从简单的某类语言构造复杂的某类语言。
? 4.3.2 语言之间的运算的封闭性
? 定义 4-16 语言的对运算的封闭定义
? 给定字母表 ∑,Ψ是 ∑上的一类语言，语言 L1，
L2СΨ，令 α是语言上的二元运算：
? (L1,L2)→α(L1, L2)； β是语言上的一元运算：
L1→β(L1) ；若对于 Ψ的任意语言 L1和 L2,α(L1，
L2)也是 Ψ的语言，则称 Ψ对于运算 α是封闭的；若对
于 Ψ的任意语言 L1,β(L1)也是 Ψ的语言，则称 Ψ对
于运算 β是封闭的。
? 定理 4-17
? 每个 i（ i=0,1,2,3）型语言对联合，连接和
迭代运算是封闭的。
? 证明：
?
? 已知同一字母表 ∑ 上的语言 L1和 L2，产生 L1的
文法 G1=（ ∑,V1,S1,P1），产生 L2的文法
G2=（ ∑,V2,S2,P2），假定 V1∩V2=Ф,S！
∈ V1,S！ ∈ V2，设置 V=V1UV2U{S}。
? 对于联合运算：
? 构造 G3=（ ∑,V,S,P3），其中 P3={ S→S1}
U{ S→S2}U P1 U P2,对于 i=0,1,2,若 G1
和 G2是 i型文法，则 G3也是；从 S开始，使用
S→S1,得到 L(G1)，或者使用 S→S2,得到
L(G2)，显然,L(G3)=L(G1)UL(G2)，所以，对
于 i=0,1,2,Ψi对于联合封闭。
? 如果 G1和 G2是右线性文法，则 G3不是，构造文
法 G4=（ ∑,V,S,P4），其中 P4为：
? {S→w1|S1→w1 在 P1中 }U {S→w2|S2→w2
在 P2中 }U P1U P2；
? 则 G4是右线性文法，且 L(G4)=L(G1)UL(G2)。
? 对于连接运算：
? 构造 G5=（ ∑,V,S,P5），其中
P5={ S→S1S2 }U P1 U P2,若 G1和 G2是上下
文无关文法,则 G5也是上下文无关文法；且
S1=>*w1,S2=>*w2,S=>S1S2=>* w1w2，所
以 L(G5)=L(G1)L(G2)；所以 2型语言对连接封
闭。
? 若 G1和 G2是 0型或者 1型文法，文法 G5可能会有问题，
例如：文法 G1为,S1→b,文法 G2为,S2→c,
bS2→bb ；则 L(G1)={b},L(G2)={c}； L1L2={bc}；而对
于,S=>S1S2=>bS2=>bc；或 S=>S1S2=>bS2=>bb；
即文法 G5产生的语言为 {bc,bb}，它不是语言 L1和 L2的
连接。
? 该问题产生的原因是 S1和 S2产生的串发生了串道，即
S1产生的串可能将 S2产生的串作为下文,S2产生的串
可能将 S1产生的串作为上文； 为解决这个问题，将 ∑复
制为 ∑′和 ∑″，令 ∑′={x′|x∈ ∑},∑″={x″|x∈ ∑}，将 P1中
的 x用相应的 x′代替，得到 P′，将 P2中的 x用相应的 x″代
替，得到 P″，构造 G6=（ ∑,V U ∑′U ∑″,S,P6），其
中 P6为：
? { S→S1S2 } U P1′ U P2″U {x′→x|x ∈ ∑}U{x″→x |x ∈ ∑}
? 则 L(G6)=L(G1)L(G2)；所以 0型和 1型语言对连接封闭。
? 对于右线性文法,S→S1S2 不适应，构造 G7=
（ ∑,V,S1,P7），其中 P7为：
? {A→bB| A→bB 在 P1中 }U{ A→bS2 |A→b 在 P1中 }
? （注意：若 P1中有空串产生式，则要先消除空
串产生式）
? L(G7)=L(G1)L(G2)；所以 3型语言对连接封闭。
? 对于迭代运算：
? 考虑文法
? S→ε|S′
? S′→S1|S1S′
? 则 S推导出 ε和 S1n(n≥1)。
? 构造 G8=（ ∑,V1U{S,S′},S,P8），其中 P8为：
? { S→ε|S′} U {S′→S1|S1S′} U P1
? 若 G1是上下文无关文法，则 G8也是上下文无关文法；
且 S=>*L(G1)*，所以 2型语言对迭代封闭。若
? G1是 0型或者 1型文法，文法 G8会有同样的串道问题。首先,消除 G1
中的空串产生式，将 ∑复制为 ∑′和 ∑″,令 ∑′={x′|x∈ ∑},∑″={x″|x∈ ∑}，
将 P1中的 x用相应的 x′代替,得到 P1′,将 P1中的 x用相应的 x″代替，得
到 P1″，构造 G1′=（ ∑,V1 U ∑′U{S1},S1,P1′）； G1″=（ ∑，
V1U ∑″U{S2},S2,P1″）；构造 G9=（ ∑,V1 U ∑′U ∑″ U {S,S1，
S1′,S2,S2′},S,P9）；其中 P9为：
? {S→ε|S1′|S2′}U{S1′→S1|S1S2′}U{ S2′→S2| S2S1′}UP1′UP1″
? U{x′→x|x ∈ ∑}U{x″→x |x ∈ ∑}；
? 则 L(G9)=L(G1)*；所以 0型和 1型语言对迭代封闭。
? 对于右线性文法，引入新的开始符号 S和 S→ε 来产生空串 ε（若在
P1中有
? S1→ε,则删除 S1→ε ），增加 S→w （其中 w是 P1中的 S1→w ），
以便开始推导，然后，对于每个形如 A→b 的产生式，增加 A→bS
（不删除 A→b ），这样，从 S开始，可以推导出形如 w1w2… wj′A的
串，其中,w1,w2,…, wj = wj′b都在 L1中，我们可以在推导出
w1w2… wj时停止，也可以从 w1w2… wjS开始推导出另一个更长的
串，直至 L(G1)*；所以，若 G1是右线性文法，则 G=（ ∑,V1U{S}，
S,P10），其中 P10为：
? {S→ε} U （ P-{S1→ε} ） U {A→bS| 若 A→b 在 P1中 } U { S→w|
S1→wP1 中 }
? 也是右线性的文法，且 L(G10)=L(G1)*；所以 3型语言对迭代封闭。
证毕。
? 定理 4-18 右线性语言对于补和交运算是封闭的。
? 证明：
? 该定理的证明需要使用自动机的知识，留待
今后证明。
? 定理 4-19 上下文无关语言对于补和交运算不是
封闭的。
? 证明：
? 举一个反例即可。
? 上下文无关语言 L1={anbncm|n,m>0}；上下文
无关语言 L2={aibkck|i,k>0}它们的交集为
L={anbncn|n>0},而该语言不是上下文无关语言，
是一个上下文相关语言。证毕。
? 对于语言，还有一个有用的运算 -----置换。
? 定义 4-20 置换的定义
? 一个映射 g,∑*→ Y*( ∑和 Y是两个字母表 )，若 g(ε)={ε}，且
对 n≥1； g(w1w2… wn)=g(w1)g(w2)… g(wn)；则 g是一个
置换映射。特别地，若 g(a)只包含 Y*的一个元素，则 g称为
同态。直观上看，同态仅仅只改变了构成串的成分的名字，
除非同态把元素 a映射成为 ε或则是一个串。
? 若 L是字母表 ∑上的一个语言，则 g(L)=Ug(w)，其中 w∈ L。
? 且 g(a*)=g(a)g(a)… g(a)=(g(a))*。
? 例 4-21 ∑={a,b},g(a)=0*,g(b)=1；
? 若语言 L=(aba)*，则 g(L)=(0*10*)*。
? 定理 4-22
? 上下文无关语言对于（上下文无关）置换映射是封闭的。
? 证明：
? 上下文无关文法 G=（ ∑,V,S,P），产生无关语言 L,g是一个
置换映射,g(x)=L∑，其中 x∈ ∑，将文法 G改造为 G′=（ Y,V U ∑′，
S,P′）；方法是将 G中的每个产生式的右边的终结符 x替换为 x′，
增加产生式某些产生式，使得 x′=>+ L∑，文法 G产生串 x1x2… xn，
而文法 G′产生串 x1′x2′… xn′，再得到串 L∑1L∑2… L∑n。所以文法
G′产生语言 g(L)，也是上下文无关的语言。证毕。
? 定理 4-23
? 右线性语言对于（上下文无关）置换映射是封闭的。
? 证明：类似上下文无关语言的证明，略。
? 4.4 正则表达式和正则集
? 计算学科讨论的是什么能够被有效地自动化，而实现有
效自动化的基础首先是实现对问题恰当的形式化描述。
? 在形式语言中，有时使用表达式的形式来代表一个语言。
对于正则的语言，可以使用正则表达式来表示；正则表
达式对正则语言的表示具有特殊的优势：它更简单，更
方便，更容易进行处理；而且，这种表达形式还更接近
语言的集合表示和语言的计算机表示。语言的集合表示
形式使得它本身更容理解和使用；而适合计算机的表示
形式又使得它更容易被计算机系统处理。
? 本节介绍正则的表达式和它表示的正则集。
? 定义 4-24 正则集的定义
? L是字母表 ∑上的语言，若语言 L是有限的，则语言
L是正则的；或者语言 L能够由下列运算递归地产生：
? 若 L1和 L2是正则的，且 L=L1UL2；
? 若 L1和 L2是正则的，且 L=L1L2；
? 若 L1是正则的，且 L=L1*；
? 则 L也是正则的。
? 若一个语言是正则，该语言也叫作正则集。
? 例如，下列语言是正则的：
? 空集 φ和空串的集合 {ε}，因为它们是有限的；
? 语言 {ab,a}*也是正则的，因为是正则的语
言经过运算得到的。
? 定义 4-25 正则表达式的定义
? 正则表达式 R和它所表达的正则集 S(R)的定义
? φ是一个正则表达式,S(φ)=φ；
? ε是一个正则表达式,S(ε)={ε}；
? 若 a∈ ∑，则 a是一个正则表达式,S(a)={a}；
? 若 R1和 R2是正则表达式，则 R1+R2是正则表达式，
S(R1+R2)=S(R1)US(R2)
? 若 R1和 R2是正则表达式，则 R1R2是正则表达式，
S(R1R2)=S(R1)S(R2)
? 若 R是正则表达式，则（ R） *是正则表达式,S((R*))=(S(R))*；
? 例 4-26表达式（ a+b） *代表
? 正则集,{a,b}*；
? 表达式 a(b+c) *d代表
? 正则集,{w|w以 a开头，中间是 b和 c组成的任意串，最后以
d结尾 }。
? 对于每个正则集，至少能够找到表示该正则集的一个正则表
达式。
? 对于每个正则表达式，都唯一地表示一个正则集。
? 若两个正则表达式 R1和 R2均表示同一个正则集，则称这两
个正则表达式相等，记为 R1=R2。即若 S(R1)=S(R2)，则
R1=R2。
? 对于正则表达式，有下列基本的代数性质：
? 若 α,β和 γ是正则表达式，则：
? 结合律：
? α(βγ)= (αβ)γ；
? α+(β+γ)=(α+β)+γ；
? 分配律：
? α(β+γ)=αβ+αγ；
? (α+β)γ=αγ+βγ；
? 交换律：
? α+β=β+α；
? 幂等律：
? α+α=α；
? 加法运算零元素：
? α+Ф=α；
? 乘法运算单位元：
? αε=εα=α；
? 其他的代数性质：
? Ф*=ε；
? α*=α+α*；
? (α*)*= α*；
? αФ=Фα=Ф；
? 例 4-27
? 对于正则表达式（ b*+(ab) *）构造一个右线性文法 G，使之
产生语言（正则集）
? L={ b*,(ab) *}。
? 解：利用右线性语言对连接、联合和迭代运算是封闭的原理，
构造右线性文法。
? 产生 b*的文法：
? S1→ε|bS1
? 产生 ab的文法：
? S2→aB2
? B2→b
? 产生 (ab) *的文法：
? S2→ε
? S2→aB2
? B2→bS2
? B2→b
? 产生 { b*,(ab)*}的文法：
? S→bS1|ε|aB2
? S1→bS1|ε
? S2→aB2|ε
? B2→bS2|b
? 例 4-28
? 正则表达式 (a+b)(a+b)代表语言 {aa,ab,ba,bb}
? 例 4-29
? 语言 L={ w| w∈ {a,b,c}+,且 w中最后一个字母与第一
个字母相同； }的正则表达式为,
? a(a+b+c)*a+b(a+b+c)*b+c(a+b+c)*c
? 例 4-30
? 语言 L={ w| w∈ {a,b,c}+,且 w中倒数第二个字母肯定
在前面出现过 }的正则表达式为,
?
(a+b+c)*a(a+b+c)*a(a+b+c)+(a+b+c)*b(a+b+c)*b(a
+b+c)+(a+b+c)*c(a+b+c)*c(a+b+c)
? 即 (a+b+c)*(a(a+b+c)*a+ b(a+b+c)*b+ c(a+b+c)*c）
(a+b+c)
Chomsky文法体系及语言之间的运算
? 在第一章中已指出对于程序的语法分析和自然
语言的处理，形式化的文法描述方式起了重要
的作用。本章介绍 Chomsky的文法体系，语言
的运算和运算的封闭性。
? 4.1 Chomsky的文法体系
? 4.1.1 文法的分类及文法之间的关系
? 对于一般的短语结构文法 PSG=(∑,V,S,P)，
产生式的形式是 v→w,其中,v∈ (∑UV)+，且
至少包含一个非终结符； w∈ （ ∑ U V） * 。
? 定义 4-1 右线性文法的定义
? 对于文法 G=(∑,V,S,P)，若它的每个产生式
都是下列形式之一：
? A→xC 或者 A→y ；
? 其中,A,C∈ V,x∈ ∑*,y∈ ∑+；
? 则文法 G是右线性文法（也称为正则文法 RG）。
? 如果一个语言 L可以由右线性文法产生，则该语
言是右线性语言。
? 定义 4-2 上下文无关文法的定义
? 对于文法 G，如果对于 G中的任意产生式 ν→ω,
而 ν只是一个非终结符，即 A→ω, A∈ V,ω∈
（ ∑ U V） *，则称文法 G为上下文无关文法
CFG（简称无关文法）。
? 如果一个语言能由一个无关文法产生，则称这
个语言是上下文无关语言（简称无关语言）。
? 定义 4-3 上下文相关文法的定义
? 对于文法 G，如果 G的每个产生式形如 u→v,且
0<|u|≤|v|；但若 ε∈ L(G)，则允许有 S→ε,且 S不出
现在任何产生式的右边；则称文法 G为上下文相关文
法 CSG（简称相关文法）。
? 如果一个语言能由一个相关文法产生，则称这个语言
是上下文相关语言（简称相关语言）。
? 根据以上的两个定义，可以看出，一个无关的文法不
一定是相关的文法，主要是空串产生式的情况。
? 某些文法不满足上述 3类文法的要求；如
? S→AB1
? AB→0
? 该文法不是右线性文法，不是无关文法，也不是
相关文法，只能属于短语结构文法。
? Chomsky将文法分为四类，关系为：
? 任意一个右线性文法本身是一个无关文法；本身
不一定是相关文法；
? 任意一个无关文法本身不一定是相关文法；
? 设文法 G=(∑,V,S,P)，则判断 G是哪类文法的方法如下：
? 1,G是短语结构文法；
? 2、如果所有产生式都有右边部分长度大于等于左边部分，那么
G是上下文有关文法；
? 3、如果如果所有产生式的左边部分都是单个非终极符号，那么
G是上下文无关文法；
? 4、如果所有产生式的右边部分都是以终极符号开始、含有至多
一个非终极符号、如果有非终极符号则出现在最右边，那么 G
是正则文法。
? 4.1.2语言之间的关系
? 下面讨论语言之间的关系。
? 任意一个右线性语言文法本身是一个无关语言；
? 一个上下文无关语言是不是一个上下文相关语言呢？
? 从第二章可知：一个无关文法
? ①没有任何空串产生式，或者
? ②仅有一个空串产生式 S→ε,且 S不出现在任何产生式的右
边
? 则该文法本身就是一个相关文法；它产生的无关语言也就是
一个相关语言；那么，如果一个无关文法中有一般的空串产
生式（如 A→ε, A是一个非终结符，且不是开始符号），它
产生的无关语言是不是相关语言呢？
? 根据空串定理：
? G是一个上下文无关文法，存在一般的空串产生式 A→ε,则
存在另一个上下文无关文法 G′使得：
? ⑴ L(G)=L(G′)；
? ⑵若 ε！ ∈ L(G)，则 G′中没有任何空串产生式；
? ⑶若 ε∈ L(G)，则 G′中有一个空串产生式,S′→ε,且 S′不出
现在 G′的其它任何产生式的右边；（ S′是 G′开始符号）
? 实际上,G’是一个无关文法。也是一个相关文法。
? 即：任意一个无关文法都可以改造为等价的一个相关文法，
所以，任意一个无关语言也是一个相关语言。
? 结论 4-4 Chomsky的文法体系：
? 对于文法 G=（ ∑,V,S,P），根据对产生式
的不同限制,Chomsky将文法分为四类：
? 文法 G是 3型文法，即右线性文法；
? 文法 G是 2型文法，即上下文无关文法；
? 文法 G是 1型文法，即上下文相关文法；
? 文法 G是 0型文法，文法对产生式没有任何限制；
? 语言的分类是根据产生该语言的文法的分类进行的。若一个
语言 L由某个 i型文法产生，则它是 i型语言。 i=0,1,2,3。即
? 语言 L是 3型语言，即右线性语言；若 L能由某个 3型文法产
生。
? 语言 L是 2型语言，即上下文无关语言；若 L能由某个 2型文
法产生。
? 语言 L是 1型语言，即上下文相关语言；若 L能由某个 1型文
法产生。
? 语言 L是 0型语言，即短语结构语言 (PSL)或递归可枚举集，
若 L能由某个 0型文法产生。
? 定义 4-5 文法分类定义
? 用 Ψi（语言类）的概念来定义所有的 i型语言；对
于 0≤i≤3
? Ψ i ={LС∑*|L=L（ G）,G是 i型文法 }。
? 定理 4-6 语言分类定理
? Chomsky将语言分为四类，且有包含关系（真子集
关系）：
? Ψ3СΨ2СΨ1 СΨ0
? 4.2 Chomsky的文法体系另一种描述
? 目前，国内普遍对 Chomsky的文法体系存在另外
一种描述方式，该方式限制了一般的空串产生式
的使用。
? 对于一般的短语结构文法,G=(∑,V,S,P)：
? G称为 0型文法，或短语结构文法 (PSG)。对应的
L(G)叫作 0型语言或者短语结构语言 (PSL)、递归
可枚举集。
? 如果对于任意 ????P，均有 |?|≥|?|成立，则称 G为 1型文法，
或上下文有关文法 (CSG)。对应的 L(G)叫作 1型语言或者上下
文有关语言 (CSL)。
? 如果对于任意 ????P，均有 |?|≥|?|且 ??V成立，则称 G为 2
型文法，或上下文无关文法 (CFG)。对应的 L(G)叫作 2型语言
或者上下文无关语言 (CFL)。
? 如果对于任意 ????P,???均具有形式 A?w,A?wB,其中，
A,B?V,w?T+，则称 G为 3型文法，也可称为正则文法 (RG)
或正规文法。对应的 L(G)叫作 3型语言，也可称为正则语言
或正规语言 (RL)。
? 正规语言类包含于上下文无关语言类，上下文无关
语言类包含于上下文相关语言类，上下文相关语言
类包含于递归可枚举语言类。这里的包含都是集合
的真包含关系，也就是说：存在递归可枚举语言不
属于上下文相关语言类，存在上下文相关语言不属
于上下文无关语言类，存在上下文无关语言不属于
正规语言类。
? 四类文法和对应的四类语言之间都有包含关系。
? 定理 4-7
? L 是 RL 的充要条件是存在一个文法，该文法产生语言
L,并且它的产生式要么是形如 A?a 的产生式，要么
是形如 A?aB 的产生式，其中 A,B 为语法变量,a
为终极符号。
? 证明：
? 参考定理 2-15的证明。
? 定义 4-8 线性文法的定义。
? 设文法 G=(∑,V,S,P)。如果对于 ?????P,???均具有
如下形式,A?w,A?wBx，其中,A,B?V,w,x?T*，则称 G
为线性文法。对应地,L(G)叫作线性语言。
? 设文法 G=(∑,V,S,P)。如果对于 ?????P,???均具有
如下形式,A?w,A?wB，其中,A,B?V,w?T+，则称 G为
右线性文法。对应地,L(G)叫作右线性语言。
? 设文法 G=(∑,V,S,P)。如果对于 ?????P,???均具有
如下形式,A?w,A?Bw，其中,A,B?V,w?T+，则称 G为
左线性文法。对应地,L(G)叫作左线性语言。
? 定理 4-9 L 是一个左线性语言的充要条件是存在文
法 G,G 中的产生式要么是形如 A?a 的产生式，
要么是形如 A?Ba 的产生式，且 L(G)=L。 其中 A、
B 为语法变量,a 为终极符号。
? 证明：
? 读者自行完成。
? 定理 4-10 左线性文法与右线性文法等价。
? 证明：
? 读者自行完成。
? 结论：
? 对于任意右线性文法 G，能够构造出对应
的左线性文法 G’,使得 L(G’)=L(G)。
? 对于任意左线性文法 G，能够构造出对应
的右线性文法 G’,使得 L(G’)=L(G)。
? 定义：形如 A??的产生式叫作空产生式，也可叫作 ?产生式。
? 根据文法分类的定义，在 RG,CFG,CSG中，都不能含有
空产生式，所以任何 CSL中都不包含空语句 ?。
? 空语句 ?在一个语言中的存在并不影响该语言有穷描述的存
在，因为除了为生成空语句 ?外，空产生式可以不被用于语
言中其他任何句子的推导中。
? 当允许 CSL,CFL,RL包含空语句后，还会为问题的处理提
供一些方便。
? 假设允许 RG,CFG,CSG中含有空产生式，也就允许
CSL,CFL,RL中包含空语句 ?。
? 空语句不影响文法的类型。
? 定义 4-11 设 G=(V,T,P,S)为一个文法，如果 S不出现
在任何产生式的右部，则
? (1)如果 G是 CSG，则仍然称 G=(V,T,P∪ {S??},S)为
CSG； G产生的语言仍然称为 CSL。
? (2)如果 G是 CFG，则仍然称 G=(V,T,P∪ {S??},S)为
CFG； G产生的语言仍然称为 CFL。
? (3)如果 G是 RG，则仍然称 G=(V,T,P∪ {S??},S)为
RG； G产生的语言仍然称为 RL。
? 限制条件, S不出现在任何产生式的右部, 的作用
是什么呢？
? 设正则文法 G,S?ab|aS，那么 L(G)={a+b}。加
入 S??后,L(G’)={a+b,?,a}。不仅产生了空语句
?，还产生了语句 a。
? 定理 4-12
? 设 G=(∑,V,S,P)为一个文法，则存在与 G同
类型的文法 G’=(∑’,V’,S’ P’),使得 L(G)=L(G’)，
但 G’的开始符号 S’不出现在 G’的任何产生式的
右部。
? 证明：
? 先根据 G构造满足条件的 G’，然后证明两者等价。
? 取 G’=(∑,V∪ {S’},S’,P’)，其中
P’=P∪ {S’??|S???P},G’与 G有相同的类型。
? 如果 S不出现在 P中任何产生式的右边，那么效果相当于
仅仅用 S’代换 S,P’中产生式实际上与 P中完全相同。
? 先证 L(G’)?L(G)。对 ?x?L(G’)，在 G’中存在如下推导：
S’???x，那么在 G中存在如下推导：
? S???x，故 x?L(G)。
? 再证 L(G)?L(G’)。对 ?x?L(G)，在 G中存在如
下推导,S???x，那么在 G’中存在如下推导：
S’???x，故 x?L(G)。
? 综上所述,L(G)=L(G’)。
? 结论：
? 加入空语句不影响语言的类型
? 定理 4-13 下列命题成立
? (1)如果 L是 CSL，则 L∪ {?}仍然是 CSL。
? (2)如果 L是 CFL，则 L∪ {?}仍然是 CFL。
? (3)如果 L是 RL，则 L∪ {?}仍然是 RL。
? 证明：
? 证明第 (1)个定理,(2)(3)同理可证。
? 设 L是 CSL，则存在一个 CSG=(∑,V,S,P)，使得 L(G)=L。由前
面的预备定理，不妨设 S不出现在 G的任何产生式的右部。取
G’=(∑,V,S,P∪ {S??})，则 G’也是 CSG。
? 由于 S不出现在 G中任何产生式的右部，所以 S??不可能出现在任
何长度不为 0的句子的推导中，因此 L(G’)=L(G)∪ {?}。
? 因此 L(G)∪ {?}是 CSL。证毕。
? 结论：
? 去掉空语句不影响语言的类型。
? 定理 4-14 下列命题成立
? (1)如果 L是 CSL，则 L-{?}仍然是 CSL。
? (2)如果 L是 CFL，则 L-{?}仍然是 CFL。
? (3)如果 L是 RL，则 L-{?}仍然是 RL。
? 证明：
? 证明第 (1)个定理,(2)(3)同理可证。
? 设 L是 CSL，则存在一个 CSG=(∑,V,S,P)，使得 L(G)=L。如果 ??L，
则 L-{?}=L，所以 L-{?}仍然是 CSL。
? 由前面的定理，不妨设 S不出现在 G的任何产生式的右部。取 G’=(V,T,P-
{S??},S)，则 G’也是 CSG。
? 由于 S不出现在 G中任何产生式的右部，所以 S??不可能出现在任何长度
不为 0的句子的推导中，因此 L(G’)=L(G)-{?}。
? 因此 L(G)-{?}是 CSL。证毕。
? 4.3 语言之间的运算及运算的封闭性
? 产生复杂语言的方法之一是对简单的语言进行
语言的运算。
? 4.3.1 语言之间的基本运算
? 定义 4-15 语言的运算的定义
? 若语言 L1和 L2是同一字母表 ∑上的两个语言，定
义
? 语言 L1和 L2的联合运算为：
? L1UL2={w|w∈ L1或者 w∈ L2}
? 语言 L1和 L2的连接运算为：
? L1L2={w|w=w1w2,w1∈ L1,w2∈ L2}
? 语言 L1的迭代运算（或者星运算，闭包运算）
为：
? L1*={w|w=w1w2w3… wm,wi∈ L1，
m≥0 }
? =UL1n 对 n≥0
? 其中：
? L10={ε}
? L11 =L1
? L1n+1= L1L1n 对 n≥1
? 注意,
? 语言 L1={an|n>0},L2={bn|n>0}，则 L1L2是
{anbm|n,m>0}；而不是是 {anbn|n>0}。
? 封闭性：如果任意的、属于某一语言类的语言在某一特
定运算下所得到的结果仍然是该类语言，则称该语言类
对此运算具有封闭性 (closure property)。
? 有效封闭性：给定一个语言类的若干个语言的描述。如
果存在一个算法，它可以构造出这些语言在给定运算下
所获得的运算结果的相应形式的语言描述，则称此语言
类对相应的运算是有效封闭的，并称此语言类对相应的
运算具有有效封闭性 (valid closure property)。
? 语言的封闭性可以用于证明某些语言属于某类语言，以
及可以从简单的某类语言构造复杂的某类语言。
? 4.3.2 语言之间的运算的封闭性
? 定义 4-16 语言的对运算的封闭定义
? 给定字母表 ∑,Ψ是 ∑上的一类语言，语言 L1，
L2СΨ，令 α是语言上的二元运算：
? (L1,L2)→α(L1, L2)； β是语言上的一元运算：
L1→β(L1) ；若对于 Ψ的任意语言 L1和 L2,α(L1，
L2)也是 Ψ的语言，则称 Ψ对于运算 α是封闭的；若对
于 Ψ的任意语言 L1,β(L1)也是 Ψ的语言，则称 Ψ对
于运算 β是封闭的。
? 定理 4-17
? 每个 i（ i=0,1,2,3）型语言对联合，连接和
迭代运算是封闭的。
? 证明：
?
? 已知同一字母表 ∑ 上的语言 L1和 L2，产生 L1的
文法 G1=（ ∑,V1,S1,P1），产生 L2的文法
G2=（ ∑,V2,S2,P2），假定 V1∩V2=Ф,S！
∈ V1,S！ ∈ V2，设置 V=V1UV2U{S}。
? 对于联合运算：
? 构造 G3=（ ∑,V,S,P3），其中 P3={ S→S1}
U{ S→S2}U P1 U P2,对于 i=0,1,2,若 G1
和 G2是 i型文法，则 G3也是；从 S开始，使用
S→S1,得到 L(G1)，或者使用 S→S2,得到
L(G2)，显然,L(G3)=L(G1)UL(G2)，所以，对
于 i=0,1,2,Ψi对于联合封闭。
? 如果 G1和 G2是右线性文法，则 G3不是，构造文
法 G4=（ ∑,V,S,P4），其中 P4为：
? {S→w1|S1→w1 在 P1中 }U {S→w2|S2→w2
在 P2中 }U P1U P2；
? 则 G4是右线性文法，且 L(G4)=L(G1)UL(G2)。
? 对于连接运算：
? 构造 G5=（ ∑,V,S,P5），其中
P5={ S→S1S2 }U P1 U P2,若 G1和 G2是上下
文无关文法,则 G5也是上下文无关文法；且
S1=>*w1,S2=>*w2,S=>S1S2=>* w1w2，所
以 L(G5)=L(G1)L(G2)；所以 2型语言对连接封
闭。
? 若 G1和 G2是 0型或者 1型文法，文法 G5可能会有问题，
例如：文法 G1为,S1→b,文法 G2为,S2→c,
bS2→bb ；则 L(G1)={b},L(G2)={c}； L1L2={bc}；而对
于,S=>S1S2=>bS2=>bc；或 S=>S1S2=>bS2=>bb；
即文法 G5产生的语言为 {bc,bb}，它不是语言 L1和 L2的
连接。
? 该问题产生的原因是 S1和 S2产生的串发生了串道，即
S1产生的串可能将 S2产生的串作为下文,S2产生的串
可能将 S1产生的串作为上文； 为解决这个问题，将 ∑复
制为 ∑′和 ∑″，令 ∑′={x′|x∈ ∑},∑″={x″|x∈ ∑}，将 P1中
的 x用相应的 x′代替，得到 P′，将 P2中的 x用相应的 x″代
替，得到 P″，构造 G6=（ ∑,V U ∑′U ∑″,S,P6），其
中 P6为：
? { S→S1S2 } U P1′ U P2″U {x′→x|x ∈ ∑}U{x″→x |x ∈ ∑}
? 则 L(G6)=L(G1)L(G2)；所以 0型和 1型语言对连接封闭。
? 对于右线性文法,S→S1S2 不适应，构造 G7=
（ ∑,V,S1,P7），其中 P7为：
? {A→bB| A→bB 在 P1中 }U{ A→bS2 |A→b 在 P1中 }
? （注意：若 P1中有空串产生式，则要先消除空
串产生式）
? L(G7)=L(G1)L(G2)；所以 3型语言对连接封闭。
? 对于迭代运算：
? 考虑文法
? S→ε|S′
? S′→S1|S1S′
? 则 S推导出 ε和 S1n(n≥1)。
? 构造 G8=（ ∑,V1U{S,S′},S,P8），其中 P8为：
? { S→ε|S′} U {S′→S1|S1S′} U P1
? 若 G1是上下文无关文法，则 G8也是上下文无关文法；
且 S=>*L(G1)*，所以 2型语言对迭代封闭。若
? G1是 0型或者 1型文法，文法 G8会有同样的串道问题。首先,消除 G1
中的空串产生式，将 ∑复制为 ∑′和 ∑″,令 ∑′={x′|x∈ ∑},∑″={x″|x∈ ∑}，
将 P1中的 x用相应的 x′代替,得到 P1′,将 P1中的 x用相应的 x″代替，得
到 P1″，构造 G1′=（ ∑,V1 U ∑′U{S1},S1,P1′）； G1″=（ ∑，
V1U ∑″U{S2},S2,P1″）；构造 G9=（ ∑,V1 U ∑′U ∑″ U {S,S1，
S1′,S2,S2′},S,P9）；其中 P9为：
? {S→ε|S1′|S2′}U{S1′→S1|S1S2′}U{ S2′→S2| S2S1′}UP1′UP1″
? U{x′→x|x ∈ ∑}U{x″→x |x ∈ ∑}；
? 则 L(G9)=L(G1)*；所以 0型和 1型语言对迭代封闭。
? 对于右线性文法，引入新的开始符号 S和 S→ε 来产生空串 ε（若在
P1中有
? S1→ε,则删除 S1→ε ），增加 S→w （其中 w是 P1中的 S1→w ），
以便开始推导，然后，对于每个形如 A→b 的产生式，增加 A→bS
（不删除 A→b ），这样，从 S开始，可以推导出形如 w1w2… wj′A的
串，其中,w1,w2,…, wj = wj′b都在 L1中，我们可以在推导出
w1w2… wj时停止，也可以从 w1w2… wjS开始推导出另一个更长的
串，直至 L(G1)*；所以，若 G1是右线性文法，则 G=（ ∑,V1U{S}，
S,P10），其中 P10为：
? {S→ε} U （ P-{S1→ε} ） U {A→bS| 若 A→b 在 P1中 } U { S→w|
S1→wP1 中 }
? 也是右线性的文法，且 L(G10)=L(G1)*；所以 3型语言对迭代封闭。
证毕。
? 定理 4-18 右线性语言对于补和交运算是封闭的。
? 证明：
? 该定理的证明需要使用自动机的知识，留待
今后证明。
? 定理 4-19 上下文无关语言对于补和交运算不是
封闭的。
? 证明：
? 举一个反例即可。
? 上下文无关语言 L1={anbncm|n,m>0}；上下文
无关语言 L2={aibkck|i,k>0}它们的交集为
L={anbncn|n>0},而该语言不是上下文无关语言，
是一个上下文相关语言。证毕。
? 对于语言，还有一个有用的运算 -----置换。
? 定义 4-20 置换的定义
? 一个映射 g,∑*→ Y*( ∑和 Y是两个字母表 )，若 g(ε)={ε}，且
对 n≥1； g(w1w2… wn)=g(w1)g(w2)… g(wn)；则 g是一个
置换映射。特别地，若 g(a)只包含 Y*的一个元素，则 g称为
同态。直观上看，同态仅仅只改变了构成串的成分的名字，
除非同态把元素 a映射成为 ε或则是一个串。
? 若 L是字母表 ∑上的一个语言，则 g(L)=Ug(w)，其中 w∈ L。
? 且 g(a*)=g(a)g(a)… g(a)=(g(a))*。
? 例 4-21 ∑={a,b},g(a)=0*,g(b)=1；
? 若语言 L=(aba)*，则 g(L)=(0*10*)*。
? 定理 4-22
? 上下文无关语言对于（上下文无关）置换映射是封闭的。
? 证明：
? 上下文无关文法 G=（ ∑,V,S,P），产生无关语言 L,g是一个
置换映射,g(x)=L∑，其中 x∈ ∑，将文法 G改造为 G′=（ Y,V U ∑′，
S,P′）；方法是将 G中的每个产生式的右边的终结符 x替换为 x′，
增加产生式某些产生式，使得 x′=>+ L∑，文法 G产生串 x1x2… xn，
而文法 G′产生串 x1′x2′… xn′，再得到串 L∑1L∑2… L∑n。所以文法
G′产生语言 g(L)，也是上下文无关的语言。证毕。
? 定理 4-23
? 右线性语言对于（上下文无关）置换映射是封闭的。
? 证明：类似上下文无关语言的证明，略。
? 4.4 正则表达式和正则集
? 计算学科讨论的是什么能够被有效地自动化，而实现有
效自动化的基础首先是实现对问题恰当的形式化描述。
? 在形式语言中，有时使用表达式的形式来代表一个语言。
对于正则的语言，可以使用正则表达式来表示；正则表
达式对正则语言的表示具有特殊的优势：它更简单，更
方便，更容易进行处理；而且，这种表达形式还更接近
语言的集合表示和语言的计算机表示。语言的集合表示
形式使得它本身更容理解和使用；而适合计算机的表示
形式又使得它更容易被计算机系统处理。
? 本节介绍正则的表达式和它表示的正则集。
? 定义 4-24 正则集的定义
? L是字母表 ∑上的语言，若语言 L是有限的，则语言
L是正则的；或者语言 L能够由下列运算递归地产生：
? 若 L1和 L2是正则的，且 L=L1UL2；
? 若 L1和 L2是正则的，且 L=L1L2；
? 若 L1是正则的，且 L=L1*；
? 则 L也是正则的。
? 若一个语言是正则，该语言也叫作正则集。
? 例如，下列语言是正则的：
? 空集 φ和空串的集合 {ε}，因为它们是有限的；
? 语言 {ab,a}*也是正则的，因为是正则的语
言经过运算得到的。
? 定义 4-25 正则表达式的定义
? 正则表达式 R和它所表达的正则集 S(R)的定义
? φ是一个正则表达式,S(φ)=φ；
? ε是一个正则表达式,S(ε)={ε}；
? 若 a∈ ∑，则 a是一个正则表达式,S(a)={a}；
? 若 R1和 R2是正则表达式，则 R1+R2是正则表达式，
S(R1+R2)=S(R1)US(R2)
? 若 R1和 R2是正则表达式，则 R1R2是正则表达式，
S(R1R2)=S(R1)S(R2)
? 若 R是正则表达式，则（ R） *是正则表达式,S((R*))=(S(R))*；
? 例 4-26表达式（ a+b） *代表
? 正则集,{a,b}*；
? 表达式 a(b+c) *d代表
? 正则集,{w|w以 a开头，中间是 b和 c组成的任意串，最后以
d结尾 }。
? 对于每个正则集，至少能够找到表示该正则集的一个正则表
达式。
? 对于每个正则表达式，都唯一地表示一个正则集。
? 若两个正则表达式 R1和 R2均表示同一个正则集，则称这两
个正则表达式相等，记为 R1=R2。即若 S(R1)=S(R2)，则
R1=R2。
? 对于正则表达式，有下列基本的代数性质：
? 若 α,β和 γ是正则表达式，则：
? 结合律：
? α(βγ)= (αβ)γ；
? α+(β+γ)=(α+β)+γ；
? 分配律：
? α(β+γ)=αβ+αγ；
? (α+β)γ=αγ+βγ；
? 交换律：
? α+β=β+α；
? 幂等律：
? α+α=α；
? 加法运算零元素：
? α+Ф=α；
? 乘法运算单位元：
? αε=εα=α；
? 其他的代数性质：
? Ф*=ε；
? α*=α+α*；
? (α*)*= α*；
? αФ=Фα=Ф；
? 例 4-27
? 对于正则表达式（ b*+(ab) *）构造一个右线性文法 G，使之
产生语言（正则集）
? L={ b*,(ab) *}。
? 解：利用右线性语言对连接、联合和迭代运算是封闭的原理，
构造右线性文法。
? 产生 b*的文法：
? S1→ε|bS1
? 产生 ab的文法：
? S2→aB2
? B2→b
? 产生 (ab) *的文法：
? S2→ε
? S2→aB2
? B2→bS2
? B2→b
? 产生 { b*,(ab)*}的文法：
? S→bS1|ε|aB2
? S1→bS1|ε
? S2→aB2|ε
? B2→bS2|b
? 例 4-28
? 正则表达式 (a+b)(a+b)代表语言 {aa,ab,ba,bb}
? 例 4-29
? 语言 L={ w| w∈ {a,b,c}+,且 w中最后一个字母与第一
个字母相同； }的正则表达式为,
? a(a+b+c)*a+b(a+b+c)*b+c(a+b+c)*c
? 例 4-30
? 语言 L={ w| w∈ {a,b,c}+,且 w中倒数第二个字母肯定
在前面出现过 }的正则表达式为,
?
(a+b+c)*a(a+b+c)*a(a+b+c)+(a+b+c)*b(a+b+c)*b(a
+b+c)+(a+b+c)*c(a+b+c)*c(a+b+c)
? 即 (a+b+c)*(a(a+b+c)*a+ b(a+b+c)*b+ c(a+b+c)*c）
(a+b+c)
