第二章 文法与语言
? 一个语言的定义可以从两个方面进行：
? 从语言产生的角度；（形式语言）
? 从接收 (识别 )语言的角度。（自动机）
?设 ?是一个字母表,?L ? ?*,L称为
字母表 ?上的一个 语言 (language),
?x ? L,x叫做 L的一个 句子 。
2.1 例子语言
?例 1：括号匹配的语言 (该语言是指
所有的左、右括号相匹配的串的集
合 )。
?问题：如何产生该语言？即如何生
成该集合中的所有的串？
?自然语言的描述方式, 采用如下的
递归规则：
① ( )是合法的该语言的最基本的串；
② 若 S是一个合法的串,则 (S)是合法串；
③ 若 S是一个合法的串,则 SS是合法串；
?这些规则称为形成规则，根据这些规
则，可以
?(1)产生任意合法（即符合规则）的该
集合中的串；
?(2)判断某个串是否是合法的该集合的
串（即合法的句子）。
?例如,可以产生串（（））；
而推断串
（（）））
不是合法的串。
?规则 (的个数 )是有限的，但可
以产生无限个串和无限长度
的串；
?因为规则是递归的。
? 巴科斯和诺尔采用的巴科斯 -诺尔范式 （ BNF--
Backus-Naur Form） 描述规则：
? <括号匹配串 >::= ( )
? <括号匹配串 >::= <括号匹配串 > <括号匹配串 >
? <括号匹配串 >::=(<括号匹配串 >)
? 使用尖括号, <”和, >”包括起来的部分, 作
为一个整体来看待, 表示某个语法成分, 最
终, 需要使用字母表中的字母来定义 。
? 符号,,:=”是 BNF本身的符号 （ 元符号 ）,
代表, 定义为, 或, 就是, 。
? 符号, (,和, )”是字母表的元素 。
?Chomsky采用的符号化 (形式化 )的
描述方式, 运用如下的规则 （ 这些规
则被称为产生式 ）,
① S→( )
② S→(S)
③ S→SS
?→,读作, 定义为, 或者, 是,,它
的左边和右边分别称为该产生式的左
边和右边；
?根据这些规则，也可以生
成任意合法的串；可以判
断一个串是否为合法的串。
?产生串的过程为：从 S开始，反
复利用产生式的右边代替产生
式的左边（称之为推导过程），
最后，可以得到匹配的（）组
成的串。
例,串 (( ))(( )( ))的产生过程
?S=>SS=>(S)S=>(( ))S
=>(( ))(S)=>(( ))(SS)
=>(( ))(( )S)
=> (( ))(( )( ))
?其中：, =>”表示单步推导过程 。
?虽然产生式的个数是有限的，
但是规则是递归的，因而，所
有的小括号匹配的串（有无限
个）均可以由它们产生，它们
组成的集合就称为一个语言。
?S称为非终结符，在推导过程中，可
以被代替的符号。
?(和 )称为终结符，在推导过程中，不
可以被代替的符号。
?→ 是产生式系统的元符号，不属于
非终结符，也不属于非终结符。
?例 2-2：由偶数个 0组成的串的语言。
?自然语言的描述方式：
① 00是合法的该语言的基本的串；
② 若 S是合法的串,则 SS是合法的串；
?形式化的描述方式,
① S→ 00
② S→SS
问题：
?将产生式 S→SS 换成
S→ 0S0或者 S→ 00S，
是否还产生相同的语言？
?同一个语言，可以使用不同的产
生式组合来产生。
?考虑：
由奇数个 1组成串的语言的产生。
?例 2-3：包含有 +,-,*,/、
（ ） 的算术表达式的语言 。
自然语言的描述方式
① 单个变量是合法的最基本的串；
② 若 S是一个合法的串, 则 SAS是一
个合法的串 （ 其中 A代表运算符 +、
-,*,/）
③ 若 S是一个合法的串, 则 (S)是合法
的串；
形式语言的描述方式
① S→ i （ i代表单个变量 ）
② S→SAS
③ S→( S )
④ A→+
⑤ A→ -
⑥ A→*
⑦ A→/
?其中,
?A→+, A→ -,A→*, A→/ 四个产生
式的左边是相同的符号, 可以合并
为
A→+| -|*|/
+,-,*,/ 称为 A的侯选式 。
注意：
?这组产生式没有表示出运
算符的优先级 。
?表示出运算符的优先级的产生
式：
E→E+T|E -T|T
T→T*F|T/F|F
F→(E)|i
?其中,E代表表达式, T代表项, F代
表因子, (E)代表的是带小括号的表
达式 。 该组产生式表示出先算因子,
再 *,/,最后 +,-。
?如果使用 %代表模运算 (即取余数运
算 ),使用 ^代表指数运算, 则有
? E→E+T|E -T|T
?T→T*F|T/F|T %F|A
? A→F^A|F
? F→(E)|i
?注意：
?还需要考虑 ^运算的结合性,^是右结
合的 。
?例 2-4 标识符 (以字母开头的字母、
数字的串 )的产生 (仅考虑小写字母 )。
? I→L
I→IL
I→ID
L→a |b|c| … |z
D→0|1|2| … |9
将 I的定义加入到表达式中：
E→E+T|E -T|T
T→T*F |T/F|F
F →(E)|I
I→L|IL|ID
L→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|
t|u|v|w|x|y|z
D→0|1|2|3|4|5|6|7|8|9
?考虑：其他类型的表达式
（如关系表达式等）的定
义
例 2-5
?C语言中简单变量的说明语句的定义 。
C语言中的说明语句形式为：
?TYPE 变量名表；
?TYPE 变量名表；
?…
?TYPE 变量名表；
产生式为：
S→SS|P
P→T V；
T→int|char|float
V→V,V|I
I→L|IL|ID
L→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|
q|r|s|t|u|v|w|x|y|z
D→ 0|1|2|3|4|5|6|7|8|9
?其中,S代表简单变量的说明语句 (可
以由一个或多个的单个说明语句构
成 ),P代表单个的说明语句, T代表
类型, V代表变量名表 (由 ‘, ’ 隔开
的多个变量 ),I代表单个变量 。
?思考：
? PASCAL语言的简单变量的说明语
句的形成 。
2.2 文法和语言的关系
?介绍语言的定义。
?介绍文法的定义。
?介绍文法与语言的关系。
? 语言就是某个字母表上的字符串组成的一
个集合 。 语言中的字符串称为句子 。
? 文法的作用就是产生一个语言 。
? 有穷语言的表示较容易, 即使语言中的句
子的组成没有什么规律, 也可以使用枚举
的方式列出语言中的所有句子 。
? 对于无穷语言, 使用有穷描述的方式表达 。
需要从语言包含的句子的一般构成规律去
考虑问题 。 这种从语言的有穷描述来表达
语言的方法对一般的语言都是有效的 。 尤
其在使用计算机判断一个字符串是否是某
个语言的句子时, 从句子和语言的结构特
征上着手是非常重要的 。
?对于一类语言, 可以在字母表上, 按
照一定的构成规则, 根据语言的结构
特点, 定义一个文法 。 使用文法作为
相应语言的有穷描述, 不仅可以描述
出语言的结构特征, 而且可以产生这
个语言的所有句子 。
短语结构文法 (文法 )的定义
文法 G是一个四元式 (由四个部分组成 )，
即 G=(∑,V,S,P)；
?∑是一个有限字符的集合 (字母表 )，
它的元素称为字母或者终结符；
?V是一个有限字符的集合, 叫做非终
结符集合, 它的元素称为变量或者非
终结符；
?S∈ V,称为文法的开始符号；
?P是有序偶对 (α,β)的集合, 其中 α是集
合 (∑UV)上的字符串, 但至少包含一个
非终结符； β是集合 (∑UV)*的元素 。 一
般, 将有序偶对 (α,β)记为 α→β, 称为
产生式；
?如果有 α → ε,称之为空串产生
式或者 ε 产生式。
?如果有 A→B,称之为单产生式。
?一个产生式的左边可能不只一
个符号；第一个产生式的左边
只能有一个符号，就是开始符
号 S。
?文法的作用就是产
生一个语言。
约定：如果没有特别说明
第一个产生式左边的符号，就是
开始符号，可以不为 S；
大写的英文字母代表非终结符；
推导（派生）的定义 2-2
?给定文法 G,α和 β是集合 (∑UV)上的
串, 若 α,β分别可以写成 pvr 和
pur(p和 r可能同时为空串 ),而 v→u 是
文法 G的一个产生式,则称串 α可以直
接推导出串 β，
记为 α=>β, 或 pvr =>pur。
?推导的实质是用产生式的右边代
替产生式的左边。 (非终结符代表
在推导的过程中可以被替代的符
号，而终结符代表在推导的过程
中不可以被替代的符号 )。
?推导的逆过程称为归约。
?用符号 y=>*z表示 y可以经
过任意步 （ 包括 0步 ） 推导
出 z,即
? ① y=z；或者
?② 存在一个序列
α1,α2, α3, …, αn
?有 y=α1,z=αn,且
αi=>αi+1； 对所有 i≥1。
?用符号 y=>+z表示 y可以经
过多步 (至少一步 ),推导
出 z,即
?存在一个序列
α1,α2, α3, …, αn 有 y=α1，
z=αn，且 αi=>αi+1； 对所有 i≥1。
思考：
?对于任意文法 G：
?S=>*S 和
?S=>+S
?一定都成立吗？
?如果在推导的过程中，每一步都是将
推导产生的串的最左边的非终结符代
替掉，称之为最左推导，如果每一步
都是将推导产生的串的最右边的非终
结符代替掉，称之为最右推导 (也称
之为规范推导 )，
?当然，还有其它方式的推
导过程（例如混合），而
最左推导和最右推导是比
较常用的推导方式。
?对于文法 G，如果 S=>*ω，则
称 ω是文法的一个句型，若 ω
中包含的字符全是终结符，称
ω是句子。
语言的定义
?给定文法 G,有开始符号 S,则把 S
可以推导出的所有的终结符串的集
合 （ 即所有句子的集合 ）, 称为由
文法产生的语言, 记为 L(G),即
?L(G)={ω|S=>*ω,且 ω∈ ∑*}。
? 例如：产生括号匹配的语言的文法是：
G=({(,)},{S},S,{ S→( ),S→(S),S→SS })
? 一般，对于文法 G，可以只给出它的产生式的
集合即可。上述文法可以简写为：
S→( )
S→(S)
S→SS
?对于文法和语言，可以从一个文
法得到该文法产生的语言；也可
以根据语言，写出产生该语言的
某个文法；还可以判断一个语言
是否由某一个文法产生。
?考虑：
文法 S→aSa|bSb|c|ε
产生的语言是什么？
考虑：
?产生语言 L的文法，
?L= {wwT|w∈ {a,b,c}+}
?其中,wT是 w的逆（反序）。
考虑：
?产生下列语言的文法：
L1={anbn|n>=0}；
L2={anbn|n>0}；
?文法
S→ 0B|1A
A→ 0|0S|1AA
B→ 1|1S|0BB
?产生的语言是
?{0,1}上包含相等个数 0和 1的串的
语言；即
L(G)={ω|ω∈ {0,1}+，
且 ω中有相同多的 0和 1}。
?一个文法确实产生语言 L(G),必须
确定两个命题：
?① 该文法推导出的串都在语言中；
?②所有语言中的串都可以由该文法
产生。
?注意：一个语言可能由多个不同
的文法产生。
?如果文法 G1和文法 G2产生同一个
语言，则称文法 G1和 G2是等价的
文法。记为 L(G1)= L(G2)。
? 例 2-9 构造文法 G，使 L(G)={0,1,00,11}。
? G1：
S→0|1|00|11
? G2：
S→A|B|AA|BB
A→0
B→1
?G3：
S→0|1|0A|1B
A→0
B→1
?有 {0,1,00,11}=L(G1)=L(G2)=L(G3)
?注意：
? 两个文法 G1和 G2等价和两个文法
G1和 G2相同的区别。
2.3Chomsky对文法的分类
? 本节介绍 Chomsky对文法和语言进行的分类 。
? 语言是由文法产生的, 对语言的分类, 是根
据产生语言的文法的分类而进行的 。
短语结构文法
? 对于一般的短语结构文法 PSG,G=(∑, V，
S,P),产生式的形式是 v→w, 其中：
v∈(∑∪V) +,且至少包含一个非终结符；
w∈(∑∪V) *。
? 如果一个语言 L可以由短语结构文法产生,
则该语言是短语结构语言 PSL。
定义 2-4：右线性文法的定义
?对于文法 G=(∑, V,S,P),若它的
每个产生式都是下列形式之一：
?A→bC 或者 A→a ；
?其中,A,C∈V, a∈XU{ ε },b∈ ∑ ；
则文法 G是右线性文法 （ RLG,也称为
正则文法 RG） 。
?如果一个语言 L可以由右线性文法
产生, 则该语言是右线性语言
（ RLL或 RL） 。
?右线性文法自然地对应于句子的
推导过程。
左线性文法
?对于文法 G,若每个产生式都是,：
?A→Cb 或者 A→a ；其中 A,C∈V,
a∈XU{ ε },b∈X ；则文法 G是左
线性文法 。 如果一个语言 L可以由
左线性文法产生, 则该语言是左
线形语言 。
?左线性文法自然地对应于句子的
归约过程。
?例 2,右线性文法
? S→ ε |0|0S|1|1S
?产生右线性语言 L={0,1}*。
?例 3：右线性文法
S→ ε |0S|1T
T→ 0T|1S
?产生语言 L={w|w∈{ 0,1}*且 w
中 1的个数为偶数 }。
定理 2-1
?左线性文法与右线性文法是等价的 。
?证明：
?略 。
? 例 2-12 产生语言 L={12345}的文法为：
? 右线性文法,左线性文法：
? S→ 1A S→A 5
? A→ 2B A→B 4
? B→ 3C B→C 3
? C→ 4D C→D 2
? D→ 5 D→ 1
? 注意：
? 左线性文法的产生式与右线性文法的产生
式混用所得到的文法不是 RG。
? 例如文法 G,S→0A
A→S1|1
? 产生语言 L(G)={0n1n|n≥ 1}。 该文法是无
关文法 。
? 例 2-8 右线性文法
? S→ ε |0|0S|1|1S
? 产生右线性语言 L={0,1}*。
? 例 2-9 右线性文法
? S→ ε |0S|1T
? T→ 0T|1S
? 产生语言 L={w|w∈{ 0,1}*且 w中 1的个数为偶数 }。
? 以上右线性文法的定义是标准的形式 。 下面介
绍右线性文法的另一种形式；
右线性文法的另一个定义
?设文法 G，若它的产生式都是形式：
A→wB 或 A→v
其中,w∈X +,B∈V,v∈X *
则该文法产生的语言是右线性语言。
G也是右线性文法。
证明：
?对于文法 G的任意产生式：
A→wB ；
?将 w记为 a1a2a3… an,则
A→a 1a2a3… anB,在原来非终结符集
合 V的基础上, 增加 n-1个新的非终结
符 A1,A2,…, An-1，
?并将 A→a 1a2a3… anB改造
为以下的产生式：
A →a 1A1
A1→a 2A2
A2→a 3A3
…
An-1→a nB (或 An-1→a n)
?以上的产生式的功能和 A→a 1a2a3… anB
是一样的, 且它们都满足右线性文法
产生式的严格定义 。 将 G的所有产生
式都进行改造, 得到文法 G’,而且 G’
是 右线性文法 。 所以, G和 G’ 产生的
语言是同一个语言 (右线性语言 )。
定义 2-5 上下文无关文法的定义
? 给定文法 G,如果对于 G中的任意产生式
ν → ω, 而 ν 只是一个非终结符, 即
A→ ω,A∈V, ω∈(∑ ∪ V)*,则称文
法 G为上下文无关文法 (简称无关文法 CFG)。
? 如果一个语言能由一个无关文法产生, 则
称这个语言是上下文无关语言 (简称无关
语言 CFL)。
定义 2-6 上下文相关文法的定义
?给定文法 G,如果对于 G中的每个产生
式 ν → ω是下面两种形式之一, 则称
文法 G是上下文相关文法 (简称相关文
法 CSG)：
?① yAz→y ωz
?其中,A是一个非终结符, y,z∈(∑
∪ V)*,ω∈(∑ ∪ V)+；
?② S→ ε, 且 S不出现在任何产生式
的右边 。
?如果一个语言能由相关文法产生, 则
称这个语言是上下文相关语言 (简称
相关语言 CSL)。
?注意：
?yAz→y ωz表示只有当 A的前面是 y，
后面是 z的时候, 才能将 A替换 ω。
?而 A→ ω表示可以随意将 A替换 ω。
?根据以上的两个定义, 可以看出, 一
个无关的文法不一定是相关的文法,
主要是空串产生式的情况 。
? 例如：产生语言 L={0n1n|n≥ 0}的文法可以为
? G1：
S→ 0S1
S→ ε
? 是无关文法, 不是相关文法 。
? G2：
S→ ε
S→ 01
S→ 0A1
A→ 0A1
A→ 01
? 是无关文法, 也是相关文法 。
? G3：
S→ ε
S→ 01
S→ 0A1
0A→ 00A1
A→ 01
? 不是无关文法, 是相关文法 。
? 它们都产生语言 L={0n1n|n≥ 0},根据语言的定
义, 它是无关语言, 也是相关语言 。
? 根据文法的定义, 还可以看出, 一个无关文法,
如果
? ① 没有任何空串产生式, 或者
? ② 仅有一个空串产生式 S→ ε, 且 S不出现在任
何产生式的右边
? 则该文法本身就是一个相关文法 。
2.4文法产生语言
? 例 2-18 文法
S→ 0S
S→ 0
? 该文法产生语言 L={0n|n>0}。
? 分析：
? 如果开始使用第 2个产生式 S→ 0,则 S=>0,就
不能再往下进行推导了, 产生串 0；
? 如果开始使用第 1个产生式 S→ 0S,n-1次后,
则 S=>0S=>00S=>000S=>* 0n-1S,最后, 再使
用第 2个产生式 S→ 0,则 S=>*0n,这对于任何
n>1 都是成立的；总之, 该文法产生语言
L={0n|n>0}。
自嵌套 (递归 )的文法的定义 2-19
? 一个上下文无关文法 G,如果 A ∈ V,有
A =>+αAβ, 则该文法称为自嵌套的文法；
而 A称为自嵌套的非终结符 。
? 自嵌套也称为递归 。
? 如果是 A =>αAβ,则 A称为直接的自嵌套
的非终结符 。
? 直接的自嵌套可以从产生式判断, 而非直
接的自嵌套需要根据推导过程才能进行判
断 。
? 注意：
? 对于 A→A 形式的产生式, 该类产生式
是递归的, 可以反复利用任意多次, 但对
于无穷语言的产生, 没有任何作用 。
? 一个无关文法的产生式的个数总是有限的,
但如果该文法是自嵌套的文法, 则该文法
就能够产生一个无穷的语言 。
? 若一个无关文法不是自嵌套的文法, 则该
文法一定产生一个有穷的语言 。
? 定义 2-20 空串产生式的定义
形如 A→ ε 的产生式, 称为空串产生式,
或 ε 产生式 。 其中,A∈V 。
? 空串产生式的作用就是在推导的过程中,
对于某个句型, 省略掉能够产生 ε 的非终
结符号 。
? 若某个文法有空串产生式 S→ ε (S为文法
的开始符号 ),则该文法产生的语言一定
包含空串 ε 。
? 例 2-21 文法
S→ 0S
S→ ε
? 该文法产生语言 L={0n|n≥ 0}。
? 分析：如果开始使用第 2个产生式 S→ ε,
则 S=>ε, 就不能再往下进行推导了, 产
生空串 ε ；如果开始使用第 1个产生式
S→ 0S,n次后, 则 S=>0S=>00S=>000S=>*
0nS,最后, 再使用第 2个产生式 S→ ε,
则 S=>*0n,这对于任何 n≥ 1都是成立的；
总之, 该文法产生语言 L={0n|n≥ 0}。
?例 2-22 文法
S→aSb
S→ab
?该文法产生语言 L={anbn|n>0}。
? 分析：如果开始使用第 2个产生式 S→ab,
则 S=>ab,就不能再往下进行推导了, 产
生串 ab；如果开始使用第 1个产生式
S→aSb, n-1 次后, 则
S=>aSb=>aaSbb=>aaaSbbb=>* an-1Sbn-1，
最后, 再使用第 2个产生式 S→ab, 则
S=>*anbn,这对于任何 n>1都是成立的；
总之, 该文法产生语言 L={anbn|n>0}。
?例 2-23 文法
S→aS
S→bS
S→ε
?该文法产生语言 L={a,b}*。
?例 2-24字母表 {a,b}上所有对称的串
(没有中心点 )组成的语言 。
?构造文法产生该语言 。
? 分析,aa和 bb是最基本合法的串 。
? 如果 x代表合法的串, 则 axa和 bxb是合法的串；
? 得到文法：
S→aSa
S→bSb
S→aa
S→bb
? 思考：
? (1)文法
S→aSa
S→bSb
S→a
S→b
? 产生的语言是什么？
?(2)
S→aSa
S→bSb
S→ ε
? 产生的语言是什么？
?(3) 产生语言 L 的 文 法,
L={wdwT|w∈{a,b,c} +}
?其中,wT是 w的逆 。
?(4) 产生下列语言的文法：
?L={anbn|n>=0}；
? 一般地,
? 对任意的 a,b∈∑ +,可以使用 A→ab|aAb
来产生 {anbn|n>0}；
? 对任意的 a,b∈∑ +,可以使用 A→ ε |aAb
来产生 {anbn|n≥ 0}；
? 对任意的 a,b∈∑ +,可以使用 A→ ε |aA
|bA来产生 ∑ *；
? 对 任 意 的 a, b∈∑ +, 可 以 使 用
A→a|b|aS|bS 来产生 ∑ +；
? 对任意的 a∈∑ +,可以使用 A→ ε |aA来产
生 {an|n≥ 0}；
? (对任意的 a∈∑ +,也可以使用 A→ ε |Aa来
产生 {an|n≥ 0}； )
? 对任意的 a∈∑ +,可以使用 A→a|aA 来产生
{an|n>0}；
?( 对任意的 a∈∑ +, 也 可 以 使 用
A→a|aA 来产生 {an|n>0}； )
?对任意的 a, b∈∑ +, 可 以 使 用
A→aAa|bAb 来产生 {wAwT|}；
注意：
? 不能使用
? A→a 2
? 来代表
? A→aa
? 不能使用
? A→a n(n≥ 1)
? 来代表
? A可以产生任意多个 a
思考：当字母表为 {0,1}时，语言
? （ 1） {x | x=xT,x ? ?}。
? （ 2） {x | x=xT,x ? ?+}
? （ 3） {xxT | x ? ?+}。
? （ 4） {xxT | x ? ?*}。
? （ 5） {x0xT | x ? ?+}
? （ 6） {xwxT | x,w ? ?+}。
? （ 7） {xxTw | x,w ? ?+}。
? 的特性及产生语言的文法 。
? 例 2-25 构造文法 G,产生语言 { w | w 是
实数 }；
? 分析：
? 实数包括有符号实数和无符号实数, 使用
S代表实数, R代表无符号实数, 则有
? S→R|+R| -R|0
?按照无符号 实数 的结构, 它又可以划
分成无符号整数, 无符号小数和无符
号纯小数, 分别使用 N,B和 P表示,
因此, 有
?R→N|B|P
? 无符号小数由小数点,,”隔开的整数部分
和小数部分组成, 其中的整数部分就是无
符号整数；小数部分使用 D代表, 则有
? B→N,D
? 无符号纯小数的结构为,,0”后跟小数
点,,”再跟小数部分；有
? P→ 0.D
?现在需要解决的是无符号整数 N和小
数部分 D的定义 。
?无符号整数是由 {0,1,2,3,4,5，
6,7,8,9}中的 10个数字符号组成
的, 但不允许以 0开始的符号串, 因
此,
? N→AM
? A→ 1|2|3|4|5|6|7|8|9
? M→ ε |0M|1M|2M|3M|4M|5M|6M|7M|8M|9M
? 小数部分由 {0,1,2,3,4,5,6,7,8，
9}中的 10个数字符号组成的, 但不允许以
0结束的符号串, 因此,
? D→ 0|MA
得到整个文法：
? S→R|+R| -R
? R→N|B|P
? B→N,D
? P→ 0.D
? N→AM
? D→ 0|MA
? A→ 1|2|3|4|5|6|7|8|9
? M→ ε |0M|1M|2M|3M|4M|5M|6M|7M|8M|9M
? 例 2-26 文法
? S→ 0B|1A
? A→ 0|0S|1AA
? B→ 1|1S|0BB
? 证明：该文法产生的是 {0,1}上包含相等个数 0
和 1的串的语言；即
? L(G)={ω|ω∈{ 0,1}+,且 ω 中有相同多的 0和
1}。
?思路：为证明该文法确实产生语言
L(G),必须证明两个命题：
?① 该文法确实只能推导出包含相同多
0和 1的串；
?② 所有包含相同多 0和 1的串都可以由
该文法产生 。
?先证明 ① 。
?证明：
?使用归纳法, 要证明三个断言：
?a)S仅能推导出包含相同多 0和 1的串；
?b)A仅能推导出 0比 1多一个的串；
?c)B仅能推导出 1比 0多一个的串；
?基础：当串的长度为 1时,b和 c成立
?当串的长度为 2时,a 成立
?假设：当串的长度小于 n时, a,b和 c
成立；
?推理：则当串 ω 的长度等于 n时, 如
果 S=>*ω, 则第一步推导使用的产生
式是 S→ 0B或者是
? S→ 1A, 假设使用的产生式是 S→ 0B,注
意到 S=>0B=>*ω,所以 B推出的串长度小于
n(为 n-1),而根据假设, B仅能推导出 1比
0多一个的串, 故 S=>0B=>*ω,ω中包含相
同多 0和 1的串；如果第一步推导使用的产
生式是 S→ 1A,亦然 。 b和 c的证明类似 。
? 命题 ② 的证明也使用归纳法, 略 。
例 2-27 文法
? S→aSBC ①
? S→aBC ②
? CB→BC ③
? aB→ab ④
? bB→bb ⑤
? bC→bc ⑥
? cC→cc ⑦
? 产生的语言为 L(G)={anbncn|n>0}。
? 注意到下面的事实, 可以得出这个结论：
? 使用 n-1次第 ① 个产生式, 有
S=>*an-1S(BC)n-1
? 使用 1次第 ② 个产生式, 有
an-1S(BC)n-1=>an(BC)n
? 使用 n*(n-1)/2次第 ③ 个产生式, 有
an(BC)n =>*anBnCn
?使用 1次第 ④ 个产生式, 有
anBnCn =>anbBn-1Cn
?使用 n-1次第 ⑤ 个产生式, 有
anbBn-1Cn =>*anbnCn
?使用 1次第 ⑥ 个产生式, 有
anbnCn =>anbnc Cn-1
?使用 n-1次第 ⑦ 个产生式, 有
anbnc Cn-1=>*anbncn
? 下面证明, 从 S开始只能推导出形如 anbncn
的串 。
? 这是因为, 从 S开始, 先使用产生式
S→aSBC, 得到 S=>aSBC=>aaSBCBC
=>*anS(BC)n,使用第 2个产生式 S→aBC, 则
S=>*an(BC)n,此时, 如果使用第 4个产生式
aB→ab 和第 6个产生式 bC→bc, 则
? aa… aBCBCBC… BC=>aa… abCBCBC… BC=>aa
… abcBCBC… BC
?不管后面的推导过程怎样, 始终有 c
和 B的连续出现, 而无法最终产生终
结符串 。 所以, 该文法从 S开始, 只
能按照上述的顺序, 推导出形如
anbncn的串 。
思考：
? 上述文法的后 3个产生式
? bB→bb
? bC→bc
? cC→cc
? 是否可以改为
? B→b
? C→c
?
?上例还可以简化为：
?S→abc|aSBc
?cB→Bc
bB→bb
思考：
? 补充文法 G，使得 L（ G） = {anbncn|n>0}
?S→aBSc
?S→aBc
?Ba→?
?…
?上例是到目前为止，产生式的
左边有多个符号的文法。
?构造文法 G，使得
L(G)={anb2n|n>=1}。
?构造文法 G，使得 L(G)=
{am+1b2m+1|m>=0}。
?构造文法 G，
使得 L(G)={anb2n-1|n>=1}。
?定理 2-30 每个上下文无关语言能够
由文法 G产生, 其中 G的产生式或者是
A→ α, 或者是 A→w 。 其中 A ∈ V，
α ∈ V+,w∈∑ * 。
证明：
? 对于产生式右边全是非终结符或全是终结
符的产生式, 已经满足定理的要求；考虑
文法中产生式的右边同时包含有终结符和
非终结符的产生式,A→B 1B2… Bm,m≥ 2，
对于 B1B2… Bm中的每个终结符 Bi,使用 V中
没有的非终结符 Bi′ 来代替 Bi,并增加产
生式 Bi′ →B i,使得该产生式的右边全为
非终结符 。 证毕 。
? 例如：文法 G：
? S→ ε
? S→AB
? S→ 0A1
? A→ 0A1
? A→ 01
? B→ 10
? 产生的语言是字母表 {0,1}上的 。
?
? 可以改造为等价的文法：
? S→ ε
? S→AB
? S→ 0′ A1′
? A→ 1′ A0′
? A→ 0′ 1′
? B→ 1′ 0′
? 产生的语言是字母表 {0′, 1′ }上的 。
?还原为原来的字母表需要将 0′和 1′当
作非终结符, 产生 0和 1。 即
?0′ → 0
?1′ → 1
则得
? S→ ε
? S→AB
? S→ 0′ A1′
? A→ 1′ A0′
? A→ 0′ 1′
? B→ 1′ 0′
? 0′ → 0
? 1′ → 1
? 补充定理：
? 每个上下文无关语言能够由文法 G产生,
其中 G的产生式或者是 A→ α, 或者是 A→w 。
其中 A ∈ V,α ∈ V+,w∈∑∪{ ε }。
甚至, α 可以为仅有两个非终结符的串 。
? 证明：
? 留给读者完成。
?定理 2-31 每个上下文相关语言能够
由文法 G产生, 其中 G的产生式或者是
α → β, 且 |α |≤| β |,或者是 A→w ；
如果 ε ∈L, 则仅有一个空串产生式
S→ ε, 且 S不出现在任何产生式的右
边 。
?其中,α,β ∈V +,A∈V, w∈∑ 。
? 证明：
? 任意一个上下文相关语言能够由上下
文相关文法 G′ 产生, 文法 G′ 中的每个产
生式 ν → ω是下面两种形式之一：
? yAz→y ωz
? 其中,A是一个非终结符, y,z∈(∑ ∪
V)*,ω∈(∑ ∪ V)+；
? 或
? S→ ε, 且 S不出现在任何产生式的右边 。
? 显然,|yAz|≤|y ωz|,可以对 yAz→y ωz
形式的产生式进行改造：
? 将 y,z,ω和 z中的所有终结符 a全部改造
为对应的非终结符 a′ ；增加 a′ →a ；
? 即可得到文法 G。 证毕 。
?定理 2-32
?对于相关文法 CSG=(∑,V, S,P),则
存在一个与它等价的上下文相关文法
CSG1,即 L(G)=L(G1),但 G1的开始符
号 S1不会出现在 G1的任何产生式的右
边 。
? 证明：
? 方法：设 S1为一个不在文法 G中的符号 (即
它不是文法 G的非终结符或终结符 ),构造
文法 G1=(∑,V∪{S 1},S1,P1),其中 P1
为文法 G的 P加上 S1 → α 形式的所有产生
式, 其中 S → α 在 P中, 因为 S1是新增加
的非终结符, 它不会出现在 P1的任何产生
式的右边 。
?现证明 L(G)=L(G1),
?(1) 对于文法 G:有 S=>α =>*w
? 对于文法 G1:则有 S1=>α =>*w
?即, S可以产生的句子, S1也能够产
生, 即 L(G)是 L (G1)的子集 。
?(2) 对于文法 G1:有 S1=>α =>*w,而
S1不会出现在 P1的任何产生式的右边,
因此, α 中没有 S1,在 α =>*w的所有
句型中也不会有 S1,而 S =>α =>*w，
所以 L(G1)是 L(G)的子集 。 证毕 。
?如果 G为 CFG,也能找到一个等价的
CFG1。
? 定理 2-33
? 如果语言 L是 CFL(或 CSL),那么 L∪{ ε }和
L-{ε }也是 CFL(或 CSL)。
? 证明：
? 方法：在产生语言 L的文法 G的产生式中增
加或删除 S → ε 产生式即可 (S为 G的开始
符号 )。
?定理 2-34 语言 L是上下文相关语言,
当且仅当存在文法 G,使得 L=L(G)； G
的每个产生式形如 u→v, 且
0<|u|≤|v| ；但若 ε ∈L(G), 则允许
有 S→ ε, 且 S不出现在任何产生式的
右边 。
?证明：
?仅当：若 G是上下文相关文法, 根据
定义, 文法的产生式形如,yAz→ywz
(其中 A是一个非终结符, y,z∈(∑
∪ V)*, w∈(∑ ∪ V)+), 有
0<|yAz|≤|ywz| ；或者 S→ ε, 且 S不
出现在任何产生式的右边 。
?当：若 G的标准产生式形如 u→v, 且
0<|u|≤|v|, 即
A1A2A3… Am→B 1B2B3… Bn,且 m≤n,
?
?Ai,Bi∈(∑ ∪ V)；假设 Ai都是非终
结符 (若不是, 则在 V中增加非终结符
Ai’和产生式
?Ai’ → Ai),对文法 G进行改造,(注
意, 不止下面一种方法 )。
?设 C1,C2,C3,…, Cm,是 G中没有的
非终结符, 对 于 产 生 式
A1A2A3… Am→B 1B2B3… Bn,变换为
? A1A2A3… Am→C 1A2A3… Am
? C1A2A3… Am→C 1C2A3… Am
? …
? C1C2C3… Cm-1Am→C 1C2C3… Cm-1BmBm+1Bm+2… Bn
? C1C2C3… Cm-1BmBm+1Bm+2… Bn→C 1C2C3… Bm-
1BmBm+1Bm+2… Bn
? …
? C1B2B3… Bn→B 1B2B3… Bn
?上述的产生式都是相关文法的标准产
生式, 将文法 G的每个形如 u→v, 且
0<|u|≤|v| 的产生式都进行改造, 得
到文法 G’ 是相关文法, 且
L=L(G)=L(G’)。 证毕 。
? 思考：
? 产生式的改造可以采用下面的方法吗？
(即不使用新增加的符号 )
? A1A2A3… Am→B 1A2A3… Am
? B1A2A3… Am→B 1B2A3… Am
? …
? B1B2B3… Bm-1Am→B 1B2… Bm-1BmBm+1Bm+2… Bn
? 一个语言的定义可以从两个方面进行：
? 从语言产生的角度；（形式语言）
? 从接收 (识别 )语言的角度。（自动机）
?设 ?是一个字母表,?L ? ?*,L称为
字母表 ?上的一个 语言 (language),
?x ? L,x叫做 L的一个 句子 。
2.1 例子语言
?例 1：括号匹配的语言 (该语言是指
所有的左、右括号相匹配的串的集
合 )。
?问题：如何产生该语言？即如何生
成该集合中的所有的串？
?自然语言的描述方式, 采用如下的
递归规则：
① ( )是合法的该语言的最基本的串；
② 若 S是一个合法的串,则 (S)是合法串；
③ 若 S是一个合法的串,则 SS是合法串；
?这些规则称为形成规则，根据这些规
则，可以
?(1)产生任意合法（即符合规则）的该
集合中的串；
?(2)判断某个串是否是合法的该集合的
串（即合法的句子）。
?例如,可以产生串（（））；
而推断串
（（）））
不是合法的串。
?规则 (的个数 )是有限的，但可
以产生无限个串和无限长度
的串；
?因为规则是递归的。
? 巴科斯和诺尔采用的巴科斯 -诺尔范式 （ BNF--
Backus-Naur Form） 描述规则：
? <括号匹配串 >::= ( )
? <括号匹配串 >::= <括号匹配串 > <括号匹配串 >
? <括号匹配串 >::=(<括号匹配串 >)
? 使用尖括号, <”和, >”包括起来的部分, 作
为一个整体来看待, 表示某个语法成分, 最
终, 需要使用字母表中的字母来定义 。
? 符号,,:=”是 BNF本身的符号 （ 元符号 ）,
代表, 定义为, 或, 就是, 。
? 符号, (,和, )”是字母表的元素 。
?Chomsky采用的符号化 (形式化 )的
描述方式, 运用如下的规则 （ 这些规
则被称为产生式 ）,
① S→( )
② S→(S)
③ S→SS
?→,读作, 定义为, 或者, 是,,它
的左边和右边分别称为该产生式的左
边和右边；
?根据这些规则，也可以生
成任意合法的串；可以判
断一个串是否为合法的串。
?产生串的过程为：从 S开始，反
复利用产生式的右边代替产生
式的左边（称之为推导过程），
最后，可以得到匹配的（）组
成的串。
例,串 (( ))(( )( ))的产生过程
?S=>SS=>(S)S=>(( ))S
=>(( ))(S)=>(( ))(SS)
=>(( ))(( )S)
=> (( ))(( )( ))
?其中：, =>”表示单步推导过程 。
?虽然产生式的个数是有限的，
但是规则是递归的，因而，所
有的小括号匹配的串（有无限
个）均可以由它们产生，它们
组成的集合就称为一个语言。
?S称为非终结符，在推导过程中，可
以被代替的符号。
?(和 )称为终结符，在推导过程中，不
可以被代替的符号。
?→ 是产生式系统的元符号，不属于
非终结符，也不属于非终结符。
?例 2-2：由偶数个 0组成的串的语言。
?自然语言的描述方式：
① 00是合法的该语言的基本的串；
② 若 S是合法的串,则 SS是合法的串；
?形式化的描述方式,
① S→ 00
② S→SS
问题：
?将产生式 S→SS 换成
S→ 0S0或者 S→ 00S，
是否还产生相同的语言？
?同一个语言，可以使用不同的产
生式组合来产生。
?考虑：
由奇数个 1组成串的语言的产生。
?例 2-3：包含有 +,-,*,/、
（ ） 的算术表达式的语言 。
自然语言的描述方式
① 单个变量是合法的最基本的串；
② 若 S是一个合法的串, 则 SAS是一
个合法的串 （ 其中 A代表运算符 +、
-,*,/）
③ 若 S是一个合法的串, 则 (S)是合法
的串；
形式语言的描述方式
① S→ i （ i代表单个变量 ）
② S→SAS
③ S→( S )
④ A→+
⑤ A→ -
⑥ A→*
⑦ A→/
?其中,
?A→+, A→ -,A→*, A→/ 四个产生
式的左边是相同的符号, 可以合并
为
A→+| -|*|/
+,-,*,/ 称为 A的侯选式 。
注意：
?这组产生式没有表示出运
算符的优先级 。
?表示出运算符的优先级的产生
式：
E→E+T|E -T|T
T→T*F|T/F|F
F→(E)|i
?其中,E代表表达式, T代表项, F代
表因子, (E)代表的是带小括号的表
达式 。 该组产生式表示出先算因子,
再 *,/,最后 +,-。
?如果使用 %代表模运算 (即取余数运
算 ),使用 ^代表指数运算, 则有
? E→E+T|E -T|T
?T→T*F|T/F|T %F|A
? A→F^A|F
? F→(E)|i
?注意：
?还需要考虑 ^运算的结合性,^是右结
合的 。
?例 2-4 标识符 (以字母开头的字母、
数字的串 )的产生 (仅考虑小写字母 )。
? I→L
I→IL
I→ID
L→a |b|c| … |z
D→0|1|2| … |9
将 I的定义加入到表达式中：
E→E+T|E -T|T
T→T*F |T/F|F
F →(E)|I
I→L|IL|ID
L→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|
t|u|v|w|x|y|z
D→0|1|2|3|4|5|6|7|8|9
?考虑：其他类型的表达式
（如关系表达式等）的定
义
例 2-5
?C语言中简单变量的说明语句的定义 。
C语言中的说明语句形式为：
?TYPE 变量名表；
?TYPE 变量名表；
?…
?TYPE 变量名表；
产生式为：
S→SS|P
P→T V；
T→int|char|float
V→V,V|I
I→L|IL|ID
L→a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|
q|r|s|t|u|v|w|x|y|z
D→ 0|1|2|3|4|5|6|7|8|9
?其中,S代表简单变量的说明语句 (可
以由一个或多个的单个说明语句构
成 ),P代表单个的说明语句, T代表
类型, V代表变量名表 (由 ‘, ’ 隔开
的多个变量 ),I代表单个变量 。
?思考：
? PASCAL语言的简单变量的说明语
句的形成 。
2.2 文法和语言的关系
?介绍语言的定义。
?介绍文法的定义。
?介绍文法与语言的关系。
? 语言就是某个字母表上的字符串组成的一
个集合 。 语言中的字符串称为句子 。
? 文法的作用就是产生一个语言 。
? 有穷语言的表示较容易, 即使语言中的句
子的组成没有什么规律, 也可以使用枚举
的方式列出语言中的所有句子 。
? 对于无穷语言, 使用有穷描述的方式表达 。
需要从语言包含的句子的一般构成规律去
考虑问题 。 这种从语言的有穷描述来表达
语言的方法对一般的语言都是有效的 。 尤
其在使用计算机判断一个字符串是否是某
个语言的句子时, 从句子和语言的结构特
征上着手是非常重要的 。
?对于一类语言, 可以在字母表上, 按
照一定的构成规则, 根据语言的结构
特点, 定义一个文法 。 使用文法作为
相应语言的有穷描述, 不仅可以描述
出语言的结构特征, 而且可以产生这
个语言的所有句子 。
短语结构文法 (文法 )的定义
文法 G是一个四元式 (由四个部分组成 )，
即 G=(∑,V,S,P)；
?∑是一个有限字符的集合 (字母表 )，
它的元素称为字母或者终结符；
?V是一个有限字符的集合, 叫做非终
结符集合, 它的元素称为变量或者非
终结符；
?S∈ V,称为文法的开始符号；
?P是有序偶对 (α,β)的集合, 其中 α是集
合 (∑UV)上的字符串, 但至少包含一个
非终结符； β是集合 (∑UV)*的元素 。 一
般, 将有序偶对 (α,β)记为 α→β, 称为
产生式；
?如果有 α → ε,称之为空串产生
式或者 ε 产生式。
?如果有 A→B,称之为单产生式。
?一个产生式的左边可能不只一
个符号；第一个产生式的左边
只能有一个符号，就是开始符
号 S。
?文法的作用就是产
生一个语言。
约定：如果没有特别说明
第一个产生式左边的符号，就是
开始符号，可以不为 S；
大写的英文字母代表非终结符；
推导（派生）的定义 2-2
?给定文法 G,α和 β是集合 (∑UV)上的
串, 若 α,β分别可以写成 pvr 和
pur(p和 r可能同时为空串 ),而 v→u 是
文法 G的一个产生式,则称串 α可以直
接推导出串 β，
记为 α=>β, 或 pvr =>pur。
?推导的实质是用产生式的右边代
替产生式的左边。 (非终结符代表
在推导的过程中可以被替代的符
号，而终结符代表在推导的过程
中不可以被替代的符号 )。
?推导的逆过程称为归约。
?用符号 y=>*z表示 y可以经
过任意步 （ 包括 0步 ） 推导
出 z,即
? ① y=z；或者
?② 存在一个序列
α1,α2, α3, …, αn
?有 y=α1,z=αn,且
αi=>αi+1； 对所有 i≥1。
?用符号 y=>+z表示 y可以经
过多步 (至少一步 ),推导
出 z,即
?存在一个序列
α1,α2, α3, …, αn 有 y=α1，
z=αn，且 αi=>αi+1； 对所有 i≥1。
思考：
?对于任意文法 G：
?S=>*S 和
?S=>+S
?一定都成立吗？
?如果在推导的过程中，每一步都是将
推导产生的串的最左边的非终结符代
替掉，称之为最左推导，如果每一步
都是将推导产生的串的最右边的非终
结符代替掉，称之为最右推导 (也称
之为规范推导 )，
?当然，还有其它方式的推
导过程（例如混合），而
最左推导和最右推导是比
较常用的推导方式。
?对于文法 G，如果 S=>*ω，则
称 ω是文法的一个句型，若 ω
中包含的字符全是终结符，称
ω是句子。
语言的定义
?给定文法 G,有开始符号 S,则把 S
可以推导出的所有的终结符串的集
合 （ 即所有句子的集合 ）, 称为由
文法产生的语言, 记为 L(G),即
?L(G)={ω|S=>*ω,且 ω∈ ∑*}。
? 例如：产生括号匹配的语言的文法是：
G=({(,)},{S},S,{ S→( ),S→(S),S→SS })
? 一般，对于文法 G，可以只给出它的产生式的
集合即可。上述文法可以简写为：
S→( )
S→(S)
S→SS
?对于文法和语言，可以从一个文
法得到该文法产生的语言；也可
以根据语言，写出产生该语言的
某个文法；还可以判断一个语言
是否由某一个文法产生。
?考虑：
文法 S→aSa|bSb|c|ε
产生的语言是什么？
考虑：
?产生语言 L的文法，
?L= {wwT|w∈ {a,b,c}+}
?其中,wT是 w的逆（反序）。
考虑：
?产生下列语言的文法：
L1={anbn|n>=0}；
L2={anbn|n>0}；
?文法
S→ 0B|1A
A→ 0|0S|1AA
B→ 1|1S|0BB
?产生的语言是
?{0,1}上包含相等个数 0和 1的串的
语言；即
L(G)={ω|ω∈ {0,1}+，
且 ω中有相同多的 0和 1}。
?一个文法确实产生语言 L(G),必须
确定两个命题：
?① 该文法推导出的串都在语言中；
?②所有语言中的串都可以由该文法
产生。
?注意：一个语言可能由多个不同
的文法产生。
?如果文法 G1和文法 G2产生同一个
语言，则称文法 G1和 G2是等价的
文法。记为 L(G1)= L(G2)。
? 例 2-9 构造文法 G，使 L(G)={0,1,00,11}。
? G1：
S→0|1|00|11
? G2：
S→A|B|AA|BB
A→0
B→1
?G3：
S→0|1|0A|1B
A→0
B→1
?有 {0,1,00,11}=L(G1)=L(G2)=L(G3)
?注意：
? 两个文法 G1和 G2等价和两个文法
G1和 G2相同的区别。
2.3Chomsky对文法的分类
? 本节介绍 Chomsky对文法和语言进行的分类 。
? 语言是由文法产生的, 对语言的分类, 是根
据产生语言的文法的分类而进行的 。
短语结构文法
? 对于一般的短语结构文法 PSG,G=(∑, V，
S,P),产生式的形式是 v→w, 其中：
v∈(∑∪V) +,且至少包含一个非终结符；
w∈(∑∪V) *。
? 如果一个语言 L可以由短语结构文法产生,
则该语言是短语结构语言 PSL。
定义 2-4：右线性文法的定义
?对于文法 G=(∑, V,S,P),若它的
每个产生式都是下列形式之一：
?A→bC 或者 A→a ；
?其中,A,C∈V, a∈XU{ ε },b∈ ∑ ；
则文法 G是右线性文法 （ RLG,也称为
正则文法 RG） 。
?如果一个语言 L可以由右线性文法
产生, 则该语言是右线性语言
（ RLL或 RL） 。
?右线性文法自然地对应于句子的
推导过程。
左线性文法
?对于文法 G,若每个产生式都是,：
?A→Cb 或者 A→a ；其中 A,C∈V,
a∈XU{ ε },b∈X ；则文法 G是左
线性文法 。 如果一个语言 L可以由
左线性文法产生, 则该语言是左
线形语言 。
?左线性文法自然地对应于句子的
归约过程。
?例 2,右线性文法
? S→ ε |0|0S|1|1S
?产生右线性语言 L={0,1}*。
?例 3：右线性文法
S→ ε |0S|1T
T→ 0T|1S
?产生语言 L={w|w∈{ 0,1}*且 w
中 1的个数为偶数 }。
定理 2-1
?左线性文法与右线性文法是等价的 。
?证明：
?略 。
? 例 2-12 产生语言 L={12345}的文法为：
? 右线性文法,左线性文法：
? S→ 1A S→A 5
? A→ 2B A→B 4
? B→ 3C B→C 3
? C→ 4D C→D 2
? D→ 5 D→ 1
? 注意：
? 左线性文法的产生式与右线性文法的产生
式混用所得到的文法不是 RG。
? 例如文法 G,S→0A
A→S1|1
? 产生语言 L(G)={0n1n|n≥ 1}。 该文法是无
关文法 。
? 例 2-8 右线性文法
? S→ ε |0|0S|1|1S
? 产生右线性语言 L={0,1}*。
? 例 2-9 右线性文法
? S→ ε |0S|1T
? T→ 0T|1S
? 产生语言 L={w|w∈{ 0,1}*且 w中 1的个数为偶数 }。
? 以上右线性文法的定义是标准的形式 。 下面介
绍右线性文法的另一种形式；
右线性文法的另一个定义
?设文法 G，若它的产生式都是形式：
A→wB 或 A→v
其中,w∈X +,B∈V,v∈X *
则该文法产生的语言是右线性语言。
G也是右线性文法。
证明：
?对于文法 G的任意产生式：
A→wB ；
?将 w记为 a1a2a3… an,则
A→a 1a2a3… anB,在原来非终结符集
合 V的基础上, 增加 n-1个新的非终结
符 A1,A2,…, An-1，
?并将 A→a 1a2a3… anB改造
为以下的产生式：
A →a 1A1
A1→a 2A2
A2→a 3A3
…
An-1→a nB (或 An-1→a n)
?以上的产生式的功能和 A→a 1a2a3… anB
是一样的, 且它们都满足右线性文法
产生式的严格定义 。 将 G的所有产生
式都进行改造, 得到文法 G’,而且 G’
是 右线性文法 。 所以, G和 G’ 产生的
语言是同一个语言 (右线性语言 )。
定义 2-5 上下文无关文法的定义
? 给定文法 G,如果对于 G中的任意产生式
ν → ω, 而 ν 只是一个非终结符, 即
A→ ω,A∈V, ω∈(∑ ∪ V)*,则称文
法 G为上下文无关文法 (简称无关文法 CFG)。
? 如果一个语言能由一个无关文法产生, 则
称这个语言是上下文无关语言 (简称无关
语言 CFL)。
定义 2-6 上下文相关文法的定义
?给定文法 G,如果对于 G中的每个产生
式 ν → ω是下面两种形式之一, 则称
文法 G是上下文相关文法 (简称相关文
法 CSG)：
?① yAz→y ωz
?其中,A是一个非终结符, y,z∈(∑
∪ V)*,ω∈(∑ ∪ V)+；
?② S→ ε, 且 S不出现在任何产生式
的右边 。
?如果一个语言能由相关文法产生, 则
称这个语言是上下文相关语言 (简称
相关语言 CSL)。
?注意：
?yAz→y ωz表示只有当 A的前面是 y，
后面是 z的时候, 才能将 A替换 ω。
?而 A→ ω表示可以随意将 A替换 ω。
?根据以上的两个定义, 可以看出, 一
个无关的文法不一定是相关的文法,
主要是空串产生式的情况 。
? 例如：产生语言 L={0n1n|n≥ 0}的文法可以为
? G1：
S→ 0S1
S→ ε
? 是无关文法, 不是相关文法 。
? G2：
S→ ε
S→ 01
S→ 0A1
A→ 0A1
A→ 01
? 是无关文法, 也是相关文法 。
? G3：
S→ ε
S→ 01
S→ 0A1
0A→ 00A1
A→ 01
? 不是无关文法, 是相关文法 。
? 它们都产生语言 L={0n1n|n≥ 0},根据语言的定
义, 它是无关语言, 也是相关语言 。
? 根据文法的定义, 还可以看出, 一个无关文法,
如果
? ① 没有任何空串产生式, 或者
? ② 仅有一个空串产生式 S→ ε, 且 S不出现在任
何产生式的右边
? 则该文法本身就是一个相关文法 。
2.4文法产生语言
? 例 2-18 文法
S→ 0S
S→ 0
? 该文法产生语言 L={0n|n>0}。
? 分析：
? 如果开始使用第 2个产生式 S→ 0,则 S=>0,就
不能再往下进行推导了, 产生串 0；
? 如果开始使用第 1个产生式 S→ 0S,n-1次后,
则 S=>0S=>00S=>000S=>* 0n-1S,最后, 再使
用第 2个产生式 S→ 0,则 S=>*0n,这对于任何
n>1 都是成立的；总之, 该文法产生语言
L={0n|n>0}。
自嵌套 (递归 )的文法的定义 2-19
? 一个上下文无关文法 G,如果 A ∈ V,有
A =>+αAβ, 则该文法称为自嵌套的文法；
而 A称为自嵌套的非终结符 。
? 自嵌套也称为递归 。
? 如果是 A =>αAβ,则 A称为直接的自嵌套
的非终结符 。
? 直接的自嵌套可以从产生式判断, 而非直
接的自嵌套需要根据推导过程才能进行判
断 。
? 注意：
? 对于 A→A 形式的产生式, 该类产生式
是递归的, 可以反复利用任意多次, 但对
于无穷语言的产生, 没有任何作用 。
? 一个无关文法的产生式的个数总是有限的,
但如果该文法是自嵌套的文法, 则该文法
就能够产生一个无穷的语言 。
? 若一个无关文法不是自嵌套的文法, 则该
文法一定产生一个有穷的语言 。
? 定义 2-20 空串产生式的定义
形如 A→ ε 的产生式, 称为空串产生式,
或 ε 产生式 。 其中,A∈V 。
? 空串产生式的作用就是在推导的过程中,
对于某个句型, 省略掉能够产生 ε 的非终
结符号 。
? 若某个文法有空串产生式 S→ ε (S为文法
的开始符号 ),则该文法产生的语言一定
包含空串 ε 。
? 例 2-21 文法
S→ 0S
S→ ε
? 该文法产生语言 L={0n|n≥ 0}。
? 分析：如果开始使用第 2个产生式 S→ ε,
则 S=>ε, 就不能再往下进行推导了, 产
生空串 ε ；如果开始使用第 1个产生式
S→ 0S,n次后, 则 S=>0S=>00S=>000S=>*
0nS,最后, 再使用第 2个产生式 S→ ε,
则 S=>*0n,这对于任何 n≥ 1都是成立的；
总之, 该文法产生语言 L={0n|n≥ 0}。
?例 2-22 文法
S→aSb
S→ab
?该文法产生语言 L={anbn|n>0}。
? 分析：如果开始使用第 2个产生式 S→ab,
则 S=>ab,就不能再往下进行推导了, 产
生串 ab；如果开始使用第 1个产生式
S→aSb, n-1 次后, 则
S=>aSb=>aaSbb=>aaaSbbb=>* an-1Sbn-1，
最后, 再使用第 2个产生式 S→ab, 则
S=>*anbn,这对于任何 n>1都是成立的；
总之, 该文法产生语言 L={anbn|n>0}。
?例 2-23 文法
S→aS
S→bS
S→ε
?该文法产生语言 L={a,b}*。
?例 2-24字母表 {a,b}上所有对称的串
(没有中心点 )组成的语言 。
?构造文法产生该语言 。
? 分析,aa和 bb是最基本合法的串 。
? 如果 x代表合法的串, 则 axa和 bxb是合法的串；
? 得到文法：
S→aSa
S→bSb
S→aa
S→bb
? 思考：
? (1)文法
S→aSa
S→bSb
S→a
S→b
? 产生的语言是什么？
?(2)
S→aSa
S→bSb
S→ ε
? 产生的语言是什么？
?(3) 产生语言 L 的 文 法,
L={wdwT|w∈{a,b,c} +}
?其中,wT是 w的逆 。
?(4) 产生下列语言的文法：
?L={anbn|n>=0}；
? 一般地,
? 对任意的 a,b∈∑ +,可以使用 A→ab|aAb
来产生 {anbn|n>0}；
? 对任意的 a,b∈∑ +,可以使用 A→ ε |aAb
来产生 {anbn|n≥ 0}；
? 对任意的 a,b∈∑ +,可以使用 A→ ε |aA
|bA来产生 ∑ *；
? 对 任 意 的 a, b∈∑ +, 可 以 使 用
A→a|b|aS|bS 来产生 ∑ +；
? 对任意的 a∈∑ +,可以使用 A→ ε |aA来产
生 {an|n≥ 0}；
? (对任意的 a∈∑ +,也可以使用 A→ ε |Aa来
产生 {an|n≥ 0}； )
? 对任意的 a∈∑ +,可以使用 A→a|aA 来产生
{an|n>0}；
?( 对任意的 a∈∑ +, 也 可 以 使 用
A→a|aA 来产生 {an|n>0}； )
?对任意的 a, b∈∑ +, 可 以 使 用
A→aAa|bAb 来产生 {wAwT|}；
注意：
? 不能使用
? A→a 2
? 来代表
? A→aa
? 不能使用
? A→a n(n≥ 1)
? 来代表
? A可以产生任意多个 a
思考：当字母表为 {0,1}时，语言
? （ 1） {x | x=xT,x ? ?}。
? （ 2） {x | x=xT,x ? ?+}
? （ 3） {xxT | x ? ?+}。
? （ 4） {xxT | x ? ?*}。
? （ 5） {x0xT | x ? ?+}
? （ 6） {xwxT | x,w ? ?+}。
? （ 7） {xxTw | x,w ? ?+}。
? 的特性及产生语言的文法 。
? 例 2-25 构造文法 G,产生语言 { w | w 是
实数 }；
? 分析：
? 实数包括有符号实数和无符号实数, 使用
S代表实数, R代表无符号实数, 则有
? S→R|+R| -R|0
?按照无符号 实数 的结构, 它又可以划
分成无符号整数, 无符号小数和无符
号纯小数, 分别使用 N,B和 P表示,
因此, 有
?R→N|B|P
? 无符号小数由小数点,,”隔开的整数部分
和小数部分组成, 其中的整数部分就是无
符号整数；小数部分使用 D代表, 则有
? B→N,D
? 无符号纯小数的结构为,,0”后跟小数
点,,”再跟小数部分；有
? P→ 0.D
?现在需要解决的是无符号整数 N和小
数部分 D的定义 。
?无符号整数是由 {0,1,2,3,4,5，
6,7,8,9}中的 10个数字符号组成
的, 但不允许以 0开始的符号串, 因
此,
? N→AM
? A→ 1|2|3|4|5|6|7|8|9
? M→ ε |0M|1M|2M|3M|4M|5M|6M|7M|8M|9M
? 小数部分由 {0,1,2,3,4,5,6,7,8，
9}中的 10个数字符号组成的, 但不允许以
0结束的符号串, 因此,
? D→ 0|MA
得到整个文法：
? S→R|+R| -R
? R→N|B|P
? B→N,D
? P→ 0.D
? N→AM
? D→ 0|MA
? A→ 1|2|3|4|5|6|7|8|9
? M→ ε |0M|1M|2M|3M|4M|5M|6M|7M|8M|9M
? 例 2-26 文法
? S→ 0B|1A
? A→ 0|0S|1AA
? B→ 1|1S|0BB
? 证明：该文法产生的是 {0,1}上包含相等个数 0
和 1的串的语言；即
? L(G)={ω|ω∈{ 0,1}+,且 ω 中有相同多的 0和
1}。
?思路：为证明该文法确实产生语言
L(G),必须证明两个命题：
?① 该文法确实只能推导出包含相同多
0和 1的串；
?② 所有包含相同多 0和 1的串都可以由
该文法产生 。
?先证明 ① 。
?证明：
?使用归纳法, 要证明三个断言：
?a)S仅能推导出包含相同多 0和 1的串；
?b)A仅能推导出 0比 1多一个的串；
?c)B仅能推导出 1比 0多一个的串；
?基础：当串的长度为 1时,b和 c成立
?当串的长度为 2时,a 成立
?假设：当串的长度小于 n时, a,b和 c
成立；
?推理：则当串 ω 的长度等于 n时, 如
果 S=>*ω, 则第一步推导使用的产生
式是 S→ 0B或者是
? S→ 1A, 假设使用的产生式是 S→ 0B,注
意到 S=>0B=>*ω,所以 B推出的串长度小于
n(为 n-1),而根据假设, B仅能推导出 1比
0多一个的串, 故 S=>0B=>*ω,ω中包含相
同多 0和 1的串；如果第一步推导使用的产
生式是 S→ 1A,亦然 。 b和 c的证明类似 。
? 命题 ② 的证明也使用归纳法, 略 。
例 2-27 文法
? S→aSBC ①
? S→aBC ②
? CB→BC ③
? aB→ab ④
? bB→bb ⑤
? bC→bc ⑥
? cC→cc ⑦
? 产生的语言为 L(G)={anbncn|n>0}。
? 注意到下面的事实, 可以得出这个结论：
? 使用 n-1次第 ① 个产生式, 有
S=>*an-1S(BC)n-1
? 使用 1次第 ② 个产生式, 有
an-1S(BC)n-1=>an(BC)n
? 使用 n*(n-1)/2次第 ③ 个产生式, 有
an(BC)n =>*anBnCn
?使用 1次第 ④ 个产生式, 有
anBnCn =>anbBn-1Cn
?使用 n-1次第 ⑤ 个产生式, 有
anbBn-1Cn =>*anbnCn
?使用 1次第 ⑥ 个产生式, 有
anbnCn =>anbnc Cn-1
?使用 n-1次第 ⑦ 个产生式, 有
anbnc Cn-1=>*anbncn
? 下面证明, 从 S开始只能推导出形如 anbncn
的串 。
? 这是因为, 从 S开始, 先使用产生式
S→aSBC, 得到 S=>aSBC=>aaSBCBC
=>*anS(BC)n,使用第 2个产生式 S→aBC, 则
S=>*an(BC)n,此时, 如果使用第 4个产生式
aB→ab 和第 6个产生式 bC→bc, 则
? aa… aBCBCBC… BC=>aa… abCBCBC… BC=>aa
… abcBCBC… BC
?不管后面的推导过程怎样, 始终有 c
和 B的连续出现, 而无法最终产生终
结符串 。 所以, 该文法从 S开始, 只
能按照上述的顺序, 推导出形如
anbncn的串 。
思考：
? 上述文法的后 3个产生式
? bB→bb
? bC→bc
? cC→cc
? 是否可以改为
? B→b
? C→c
?
?上例还可以简化为：
?S→abc|aSBc
?cB→Bc
bB→bb
思考：
? 补充文法 G，使得 L（ G） = {anbncn|n>0}
?S→aBSc
?S→aBc
?Ba→?
?…
?上例是到目前为止，产生式的
左边有多个符号的文法。
?构造文法 G，使得
L(G)={anb2n|n>=1}。
?构造文法 G，使得 L(G)=
{am+1b2m+1|m>=0}。
?构造文法 G，
使得 L(G)={anb2n-1|n>=1}。
?定理 2-30 每个上下文无关语言能够
由文法 G产生, 其中 G的产生式或者是
A→ α, 或者是 A→w 。 其中 A ∈ V，
α ∈ V+,w∈∑ * 。
证明：
? 对于产生式右边全是非终结符或全是终结
符的产生式, 已经满足定理的要求；考虑
文法中产生式的右边同时包含有终结符和
非终结符的产生式,A→B 1B2… Bm,m≥ 2，
对于 B1B2… Bm中的每个终结符 Bi,使用 V中
没有的非终结符 Bi′ 来代替 Bi,并增加产
生式 Bi′ →B i,使得该产生式的右边全为
非终结符 。 证毕 。
? 例如：文法 G：
? S→ ε
? S→AB
? S→ 0A1
? A→ 0A1
? A→ 01
? B→ 10
? 产生的语言是字母表 {0,1}上的 。
?
? 可以改造为等价的文法：
? S→ ε
? S→AB
? S→ 0′ A1′
? A→ 1′ A0′
? A→ 0′ 1′
? B→ 1′ 0′
? 产生的语言是字母表 {0′, 1′ }上的 。
?还原为原来的字母表需要将 0′和 1′当
作非终结符, 产生 0和 1。 即
?0′ → 0
?1′ → 1
则得
? S→ ε
? S→AB
? S→ 0′ A1′
? A→ 1′ A0′
? A→ 0′ 1′
? B→ 1′ 0′
? 0′ → 0
? 1′ → 1
? 补充定理：
? 每个上下文无关语言能够由文法 G产生,
其中 G的产生式或者是 A→ α, 或者是 A→w 。
其中 A ∈ V,α ∈ V+,w∈∑∪{ ε }。
甚至, α 可以为仅有两个非终结符的串 。
? 证明：
? 留给读者完成。
?定理 2-31 每个上下文相关语言能够
由文法 G产生, 其中 G的产生式或者是
α → β, 且 |α |≤| β |,或者是 A→w ；
如果 ε ∈L, 则仅有一个空串产生式
S→ ε, 且 S不出现在任何产生式的右
边 。
?其中,α,β ∈V +,A∈V, w∈∑ 。
? 证明：
? 任意一个上下文相关语言能够由上下
文相关文法 G′ 产生, 文法 G′ 中的每个产
生式 ν → ω是下面两种形式之一：
? yAz→y ωz
? 其中,A是一个非终结符, y,z∈(∑ ∪
V)*,ω∈(∑ ∪ V)+；
? 或
? S→ ε, 且 S不出现在任何产生式的右边 。
? 显然,|yAz|≤|y ωz|,可以对 yAz→y ωz
形式的产生式进行改造：
? 将 y,z,ω和 z中的所有终结符 a全部改造
为对应的非终结符 a′ ；增加 a′ →a ；
? 即可得到文法 G。 证毕 。
?定理 2-32
?对于相关文法 CSG=(∑,V, S,P),则
存在一个与它等价的上下文相关文法
CSG1,即 L(G)=L(G1),但 G1的开始符
号 S1不会出现在 G1的任何产生式的右
边 。
? 证明：
? 方法：设 S1为一个不在文法 G中的符号 (即
它不是文法 G的非终结符或终结符 ),构造
文法 G1=(∑,V∪{S 1},S1,P1),其中 P1
为文法 G的 P加上 S1 → α 形式的所有产生
式, 其中 S → α 在 P中, 因为 S1是新增加
的非终结符, 它不会出现在 P1的任何产生
式的右边 。
?现证明 L(G)=L(G1),
?(1) 对于文法 G:有 S=>α =>*w
? 对于文法 G1:则有 S1=>α =>*w
?即, S可以产生的句子, S1也能够产
生, 即 L(G)是 L (G1)的子集 。
?(2) 对于文法 G1:有 S1=>α =>*w,而
S1不会出现在 P1的任何产生式的右边,
因此, α 中没有 S1,在 α =>*w的所有
句型中也不会有 S1,而 S =>α =>*w，
所以 L(G1)是 L(G)的子集 。 证毕 。
?如果 G为 CFG,也能找到一个等价的
CFG1。
? 定理 2-33
? 如果语言 L是 CFL(或 CSL),那么 L∪{ ε }和
L-{ε }也是 CFL(或 CSL)。
? 证明：
? 方法：在产生语言 L的文法 G的产生式中增
加或删除 S → ε 产生式即可 (S为 G的开始
符号 )。
?定理 2-34 语言 L是上下文相关语言,
当且仅当存在文法 G,使得 L=L(G)； G
的每个产生式形如 u→v, 且
0<|u|≤|v| ；但若 ε ∈L(G), 则允许
有 S→ ε, 且 S不出现在任何产生式的
右边 。
?证明：
?仅当：若 G是上下文相关文法, 根据
定义, 文法的产生式形如,yAz→ywz
(其中 A是一个非终结符, y,z∈(∑
∪ V)*, w∈(∑ ∪ V)+), 有
0<|yAz|≤|ywz| ；或者 S→ ε, 且 S不
出现在任何产生式的右边 。
?当：若 G的标准产生式形如 u→v, 且
0<|u|≤|v|, 即
A1A2A3… Am→B 1B2B3… Bn,且 m≤n,
?
?Ai,Bi∈(∑ ∪ V)；假设 Ai都是非终
结符 (若不是, 则在 V中增加非终结符
Ai’和产生式
?Ai’ → Ai),对文法 G进行改造,(注
意, 不止下面一种方法 )。
?设 C1,C2,C3,…, Cm,是 G中没有的
非终结符, 对 于 产 生 式
A1A2A3… Am→B 1B2B3… Bn,变换为
? A1A2A3… Am→C 1A2A3… Am
? C1A2A3… Am→C 1C2A3… Am
? …
? C1C2C3… Cm-1Am→C 1C2C3… Cm-1BmBm+1Bm+2… Bn
? C1C2C3… Cm-1BmBm+1Bm+2… Bn→C 1C2C3… Bm-
1BmBm+1Bm+2… Bn
? …
? C1B2B3… Bn→B 1B2B3… Bn
?上述的产生式都是相关文法的标准产
生式, 将文法 G的每个形如 u→v, 且
0<|u|≤|v| 的产生式都进行改造, 得
到文法 G’ 是相关文法, 且
L=L(G)=L(G’)。 证毕 。
? 思考：
? 产生式的改造可以采用下面的方法吗？
(即不使用新增加的符号 )
? A1A2A3… Am→B 1A2A3… Am
? B1A2A3… Am→B 1B2A3… Am
? …
? B1B2B3… Bm-1Am→B 1B2… Bm-1BmBm+1Bm+2… Bn
