1College of Computer Science & Technology,BUPT
第二章 语言及文法
主要内容,
定义形式语言的术语
给出文法的定义和文法的分类
要求掌握：
语言和文法的形式定义
CHOMSKY文法体系的分类 。
2College of Computer Science & Technology,BUPT
第一节 语言的定义与运算一,语言的一些术语：
字母表,字符的有限集合，记为 T。
字符串,由字母表 T中的字符构成的序列称字母表 T上的字符串（句子）。
常记为 u,v,w,x,y,z；
常用 a,b,c,d 标识单个字符 。
3College of Computer Science & Technology,BUPT
字 母 表 （ Alphabet）
概念 形式符号的集合
记号 常用 T,? 表示
举例
英文字母表? a,b,…,z,A,B,…,Z?
英文标点符号表?,;,,? ! ’ ‘ ( ) …?
汉字表? …,自,…,动,…,机,…?
化学元素表? H,He,Li,…,?
T =? a,n,y,任,意?
4College of Computer Science & Technology,BUPT
字 符 串 （ string）
概念 字母表 T 上的一个 字符串 （简称 串 ），或称为字 （ word）,为 T 中字符构成的一个有限序列。
空串 （ empty string）,用?表示，不包含任何字符。
举例 设 T =? a,b?,则?,a,ba,bbaba 等都是串
字符串 w 的 长度,记为?w?,是包含在 w 中字符的个数举例 = 0,?bbaba? = 5
ai 表示含有 i个 a的字符串
5College of Computer Science & Technology,BUPT
连接（ concatenation）
设 x,y为串,且 x? a1a2 … a m,y? b1b2 … b n,
则 x 与 y 的连接
x y? a1a2 … a m b1b2 … b n
连接运算的性质
( x y ) z? x（ y z ）
x? x x
x yx?+?y?
关 于 字 符 串 的 运 算
6College of Computer Science & Technology,BUPT
其它 如 取头字符,取尾部,子串匹配 等
设 ω1,ω2,ω3是字母表 T上的字符串,称 ω1是字符串 ω1ω2的前缀,ω2是字符串 ω1ω2的后缀,且 ω2
是字符串 ω1ω2ω3的子串 。
空串是任何字符串的前缀,后缀及子串 。
例,
abc的前缀 a ab abc ε.
后缀 c bc abc ε.
子串 a b c ab bc abc ε,
即一个字符串可以看作是多个字符串的连接 。
关 于 字 符 串 的 运 算
7College of Computer Science & Technology,BUPT
字符串 ω的逆用 表示。 是字符串 ω的倒置。
ω= b1b2……b n
= bnbn-1……b 2b1
空串 ε的逆还是 ε
8College of Computer Science & Technology,BUPT
字 母 表 的 幂 运 算
幂运算 设 T 为字母表,n 为任意自然数，
定义（ 1） T0 =
（ 2）设 x? Tn-1,a? T,则 a x? Tn
（ 3） Tn 中的元素只能由（ 1）和 （ 2）生成
闭包 T* = T0? T1? T2? …
闭包 T+ = T1? T2? T3? …
T* = T+,T+ = T*
9College of Computer Science & Technology,BUPT
闭包的物理意义
T的星号闭包 T*,字母表 T上的所有字符串和空串的集合。
T的正闭包 T+,字母表 T上的所有字符串构成的集合。
T*= T+∪ {ε}
举例 设 T =? 0,1?,则
T0 =,T1 =? 0,1?，
T2 =? 00,01,10,11?,…
T* =,0,1,00,01,10,11,…?
T+ =? 0,1,00,01,10,11,…?
10College of Computer Science & Technology,BUPT
语 言 （ Languages）
概念 设 T 为字母表，则任何集合 L? T* 是 字母表 T上的 一个语言（ language）
举例
英文单词集?…,English,…,words,…?
C 语言程序集? …? 字母表？
汉语成语集?…,马到成功,…?
化学分子式集?…,H2O,…,NaCl,…?
any,任意?
11College of Computer Science & Technology,BUPT
语 言 （ Languages）
举例,设 T = {a,b}
则 L1 = {anbn | n≥1}
L3 = { bk | k 是质数 }
L2 ={ε} 只有一个空句子的语言
L4 = { } = Φ 空语言均为字母表 T上的语言。
由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，交，补，差。
12College of Computer Science & Technology,BUPT
语言的基本运算
语言的积：
两个语言 L1 和 L2的积 L1 L2是由 L1和 L2中的字符串连接所构成的字符串的集合。即 L1中所有字符串分别与 L2中的字符串连接得到的集合 。
设 T={a,b},L1和 L2是 T上的语言 。
L1 ={ab,ba} L2 ={aa,bb}
则 L1 L2 ={abaa,abbb,baaa,babb}
L2 L1 ={aaab,aaba,bbab,bbba}
L1 L2 ≠ L2 L1 语言的积不可交换 。
13College of Computer Science & Technology,BUPT
语言的基本运算
语言的幂：
语言的幂可归纳定义如下,
L0 = {ε}
Ln = L· Ln-1 = Ln-1 · L n ≥1
上例中，
L12 ={abab,abba,baab,baba}
L22 ={aaaa,aabb,bbaa,bbbb}
14College of Computer Science & Technology,BUPT
第二节 文法
定义,所谓文法是用来定义语言的一个数学模型
表示语言的方法,
若语言 L是有限集合,可用 列举法
若 L是无限集合 （ 集合中的每个元素有限长度 ）,
用其他方法 。
方法一：文法产生系统,由定义的文法规则产生出语言的每个句子
方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受,则这个字符串是该语言的一个句子,否则不属于该语言 。
15College of Computer Science & Technology,BUPT
元语言
定义,描述语言的语言例如：各种各样的程序设计语言
当人们要解释或讨论程序设计语言本身时,又需要一种语言,被讨论的语言叫做对象语言,即某种程序设计语言,讨论对象语言的语言称为元语言 。
16College of Computer Science & Technology,BUPT
BNF（ 巴科斯范式）
BNF范式通常被作为讨论某种程序设计语言语法的元语言
<数字 >,:= 0|1|2|……9,:=?定义为?
<字母 >,:= A|B|C|……Z|a|b|……z
<标识符 >,,=<字母 > | <标识符 ><字母 > | <标识符
><数字 >
…,
通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。
BNF定义了一种语言，其中标识符如上定义。
BNF描述它所定义的语言，为元语言。
17College of Computer Science & Technology,BUPT
例如：汉语语法中定义了句子的结构由主语,谓语,
宾语组成 。 这里主谓宾只是描述了句子的结构,并不是句子 。 而按照这种结构组成的建立在汉字上的字符串就是句子 。 如他是学生 。
文法是一种元语言,一种方法,根据文法产生出语言的句子 。
18College of Computer Science & Technology,BUPT
三,Chomsky文法体系
例如：
BNF <标识符 >::=<字母 >
<标识符 >::=<标识符 ><字母 >
<标识符 >::= <标识符 ><数字 >
<字母 >::=a|b|…… z|A|B|…… |Z
<数字 >::=0|1|…… 9
将,:= 改为 → 表示可被代替用 I,L,D分别表示标识符,字母,数字 ;
19College of Computer Science & Technology,BUPT
则上述表达式可以表示为
I→L
I→IL
I→ID
L→a|b|….|z
D→0|1|….9
这就是一个文法的生成式集合。
20College of Computer Science & Technology,BUPT
Chomsky文法体系中,任何一种文法必须包含有两个不同的有限符号的集合,即非终结符集合
N和终结符集合 T。 一个形式规则的有限集合 P
（ 生成式集合 ）,一个起始符 S。
P中的生成式是用来产生语言句子的规则,而句子则是仅由终结符组成的字符串 。 这些字符串必须从一个起始符 S开始,不断使用 P中的生成式而导出来 。
可见文法的核心是生成式的集合,它决定了语言中句子的产生 。
21College of Computer Science & Technology,BUPT
文法的形式定义
文法 G是一个四元组 G=(N,T,P,S),其中
N 非终结符的有限集合
T 终结符的有限集合 N∩T=Φ
P 形式为 α→β 的生成式的有限集合 。
且 α∈ (N∪ T)* N+ (N∪ T)* β∈ (N∪ T)*
S 起始符 且 S ∈ N。
22College of Computer Science & Technology,BUPT
将上例用文法表示
G=(N,T,P,S)
N = { I,L,D}
T = { a,b,c,… z,0,1,… 9}
P = { I,La,…,D0,…,D9}
S = { I }
文法是语言的产生系统,研究怎样构造文法能产生出符合要求的句子 。
23College of Computer Science & Technology,BUPT
四．推导与句型
1,直接推导设 G =（ N,T,P,S） 是文法,若 A→β 是 P
中的生成式,α和 γ是 （ N∪ T） *中的字符串,则有 αAγ=> αβγ称 αAγ直接推导出 αβγ,或说 αβγ是 αAγ的直接推导 。
24College of Computer Science & Technology,BUPT
设 G = (N,T,P,S) 是文法,α,α0,α1… αn,α’ 都是
（ N∪ T） *中的字符串,且 α=α0,α’ =αn,其中 αi直接推导出 αi+1 （ 0≤i≤n）,则称序列 α0=>α1=>α2=>… =>αn是长度为 n的推导序列,而 α=α0是长度为 0的推导序列 。
对 α推导出 α’记为 α α’,若推导序列长度大于 0,则记为 α α’。
推导序列的每一步,都产生一个字符串,这些字符串一般称为句型 。
2、推导序列
*G
G
25College of Computer Science & Technology,BUPT
3、句型和句子
句型字符串 α是文法 G的句型,当且仅当
S α,且 α∈ （ N∪ T） *。
句子
ω是 G的句子,当且仅当 S ω,且 ω∈ T*。 （ ω是由终结符组成的字符串 ）
例,I =>L =>a
I =>IL =>LL =>zL =>zb
句型包含句子
*G
*G
26College of Computer Science & Technology,BUPT
4．文法产生的语言由文法 G产生的语言记为 L(G)。
L(G) = {ω|ω∈ T*且 S ω}
或：
L(G)中的一个字符串,必是由终结符组成的,并且是从起始符 S推导出来的 。
*G
27College of Computer Science & Technology,BUPT
第三节 Chomsky文法体系分类
文法 G = (N,T,P,S)； P,α→β
其中 α∈ （ N∪ T） * N+（ N∪ T） *
β∈ （ N∪ T） * 属于 Chomsky文法体系
该体系对生成式的形式做了一些规定,分为四类,即 0型,1型,2型,3型文法
0型文法：无限制文法对应的语言：递归可枚举语言,与图灵机等价 。
28College of Computer Science & Technology,BUPT
1型文法
也称上下文有关文法（ CSG,Context-
sensitive Grammar)
生成式的形式为 α→β,
其中 |α|≤|β|,β∈ （ N∪ T） +，
α∈ （ N∪ T） *N+（ N∪ T） *
对应的语言：上下文有关语言（ CSL：
Context-sensitive Language)
若不考虑 ε,与线性有界自动机（ LBA,
Linear Bounded Automaton） 等价。
29College of Computer Science & Technology,BUPT
2型文法
也称上下文无关文法 （ CFG,Context-free
Grammar)
A→α,
A∈ N,且 α∈ （ N∪ T） *
对应的语言：上下文无关语言 （ CFL：
Context-free Language)。
对 应 的 自 动 机,下 推 自 动 机 （ PDA：
Pushdown Automaton)。
30College of Computer Science & Technology,BUPT
3型文法也称正则文法
右线性文法（ Right-linear Grammar）：
A→ωB 或 A→ω
A,B∈ N,ω∈ T*。
左线性文法（ Left-linear Grammar）：
A→Bω 或 A→ω
A,B∈ N,ω∈ T*。
对应的语言：正则语言
对 应 的 自 动 机,有 限 自 动 机 （ Finite
Automaton） 。
31College of Computer Science & Technology,BUPT
例 1：
G = ({A,B,C},{a,b,d},P,A)
P,A→AB ； AB→CAAB ； A→d ； B→a ； C→b
是 1型文法。
A=>d
A=>AB =>dB =>da
A=>AB =>ABB =>dBB =>daB =>daa
A=>AB =>CAAB =>bAAB =>bdAB =>bdCAAB
=>bdbAAB =>bdbdAB=>bdbddB =>bdbdda
32College of Computer Science & Technology,BUPT
例 2：
G = ({A,B,C},{a,b,c},P,A)
P,A→abc A→aBbc Bb→bB Bc→Cbcc bC→Cb
aC→aaB aC→aa 是 1型文法。
其定义的 L = {anbncn | n≥1}
A =>abc
A =>aBbc =>abBc =>abCbcc =>aCbbcc =>aabbcc
=>aaBbbcc
33College of Computer Science & Technology,BUPT
例 3：
G = ({S,B,C},{a,b},P,A)
P,S→aC ； S→bB ； B→aS ； B→bBB B→a ；
C→bS ； C→aCC ； C→b 是 2型文法
S =>aC =>ab
S => aC =>aaCC
S =>aC =>abS =>abaC =>ababS =>ababaC
=>ababab
S =>bB =>bbBB =>bbaSB =>bbaaCB
=>bbaabB =>bbaaba
34College of Computer Science & Technology,BUPT
例 4：
G = ({A,B,C},{a,b,c},P,A)
P,A→Ba ； A→c ； B→Cb ； C→c
左线性文法
L = {c,cba} 正则语言
注意：已知语言求文法,文法不是唯一的,即可以有不同的表达方法 。
35College of Computer Science & Technology,BUPT
四类文法之间的关系
只是对生成式形式加以限制
0型 无限制
1型 不允许 A→ε 形式
2型
3型 属于 2型
不含 A→ε 的 2型,3型属于 1型,1型,2
型,3型均属于 0型 。
36College of Computer Science & Technology,BUPT
作业,P47 4,6,7 题
第二章 语言及文法
主要内容,
定义形式语言的术语
给出文法的定义和文法的分类
要求掌握：
语言和文法的形式定义
CHOMSKY文法体系的分类 。
2College of Computer Science & Technology,BUPT
第一节 语言的定义与运算一,语言的一些术语：
字母表,字符的有限集合，记为 T。
字符串,由字母表 T中的字符构成的序列称字母表 T上的字符串（句子）。
常记为 u,v,w,x,y,z；
常用 a,b,c,d 标识单个字符 。
3College of Computer Science & Technology,BUPT
字 母 表 （ Alphabet）
概念 形式符号的集合
记号 常用 T,? 表示
举例
英文字母表? a,b,…,z,A,B,…,Z?
英文标点符号表?,;,,? ! ’ ‘ ( ) …?
汉字表? …,自,…,动,…,机,…?
化学元素表? H,He,Li,…,?
T =? a,n,y,任,意?
4College of Computer Science & Technology,BUPT
字 符 串 （ string）
概念 字母表 T 上的一个 字符串 （简称 串 ），或称为字 （ word）,为 T 中字符构成的一个有限序列。
空串 （ empty string）,用?表示，不包含任何字符。
举例 设 T =? a,b?,则?,a,ba,bbaba 等都是串
字符串 w 的 长度,记为?w?,是包含在 w 中字符的个数举例 = 0,?bbaba? = 5
ai 表示含有 i个 a的字符串
5College of Computer Science & Technology,BUPT
连接（ concatenation）
设 x,y为串,且 x? a1a2 … a m,y? b1b2 … b n,
则 x 与 y 的连接
x y? a1a2 … a m b1b2 … b n
连接运算的性质
( x y ) z? x（ y z ）
x? x x
x yx?+?y?
关 于 字 符 串 的 运 算
6College of Computer Science & Technology,BUPT
其它 如 取头字符,取尾部,子串匹配 等
设 ω1,ω2,ω3是字母表 T上的字符串,称 ω1是字符串 ω1ω2的前缀,ω2是字符串 ω1ω2的后缀,且 ω2
是字符串 ω1ω2ω3的子串 。
空串是任何字符串的前缀,后缀及子串 。
例,
abc的前缀 a ab abc ε.
后缀 c bc abc ε.
子串 a b c ab bc abc ε,
即一个字符串可以看作是多个字符串的连接 。
关 于 字 符 串 的 运 算
7College of Computer Science & Technology,BUPT
字符串 ω的逆用 表示。 是字符串 ω的倒置。
ω= b1b2……b n
= bnbn-1……b 2b1
空串 ε的逆还是 ε
8College of Computer Science & Technology,BUPT
字 母 表 的 幂 运 算
幂运算 设 T 为字母表,n 为任意自然数，
定义（ 1） T0 =
（ 2）设 x? Tn-1,a? T,则 a x? Tn
（ 3） Tn 中的元素只能由（ 1）和 （ 2）生成
闭包 T* = T0? T1? T2? …
闭包 T+ = T1? T2? T3? …
T* = T+,T+ = T*
9College of Computer Science & Technology,BUPT
闭包的物理意义
T的星号闭包 T*,字母表 T上的所有字符串和空串的集合。
T的正闭包 T+,字母表 T上的所有字符串构成的集合。
T*= T+∪ {ε}
举例 设 T =? 0,1?,则
T0 =,T1 =? 0,1?，
T2 =? 00,01,10,11?,…
T* =,0,1,00,01,10,11,…?
T+ =? 0,1,00,01,10,11,…?
10College of Computer Science & Technology,BUPT
语 言 （ Languages）
概念 设 T 为字母表，则任何集合 L? T* 是 字母表 T上的 一个语言（ language）
举例
英文单词集?…,English,…,words,…?
C 语言程序集? …? 字母表？
汉语成语集?…,马到成功,…?
化学分子式集?…,H2O,…,NaCl,…?
any,任意?
11College of Computer Science & Technology,BUPT
语 言 （ Languages）
举例,设 T = {a,b}
则 L1 = {anbn | n≥1}
L3 = { bk | k 是质数 }
L2 ={ε} 只有一个空句子的语言
L4 = { } = Φ 空语言均为字母表 T上的语言。
由语言的定义知语言是集合，对于集合的运算可应用于对于语言的计算。如并，交，补，差。
12College of Computer Science & Technology,BUPT
语言的基本运算
语言的积：
两个语言 L1 和 L2的积 L1 L2是由 L1和 L2中的字符串连接所构成的字符串的集合。即 L1中所有字符串分别与 L2中的字符串连接得到的集合 。
设 T={a,b},L1和 L2是 T上的语言 。
L1 ={ab,ba} L2 ={aa,bb}
则 L1 L2 ={abaa,abbb,baaa,babb}
L2 L1 ={aaab,aaba,bbab,bbba}
L1 L2 ≠ L2 L1 语言的积不可交换 。
13College of Computer Science & Technology,BUPT
语言的基本运算
语言的幂：
语言的幂可归纳定义如下,
L0 = {ε}
Ln = L· Ln-1 = Ln-1 · L n ≥1
上例中，
L12 ={abab,abba,baab,baba}
L22 ={aaaa,aabb,bbaa,bbbb}
14College of Computer Science & Technology,BUPT
第二节 文法
定义,所谓文法是用来定义语言的一个数学模型
表示语言的方法,
若语言 L是有限集合,可用 列举法
若 L是无限集合 （ 集合中的每个元素有限长度 ）,
用其他方法 。
方法一：文法产生系统,由定义的文法规则产生出语言的每个句子
方法二：机器识别系统：当一个字符串能被一个语言的识别系统接受,则这个字符串是该语言的一个句子,否则不属于该语言 。
15College of Computer Science & Technology,BUPT
元语言
定义,描述语言的语言例如：各种各样的程序设计语言
当人们要解释或讨论程序设计语言本身时,又需要一种语言,被讨论的语言叫做对象语言,即某种程序设计语言,讨论对象语言的语言称为元语言 。
16College of Computer Science & Technology,BUPT
BNF（ 巴科斯范式）
BNF范式通常被作为讨论某种程序设计语言语法的元语言
<数字 >,:= 0|1|2|……9,:=?定义为?
<字母 >,:= A|B|C|……Z|a|b|……z
<标识符 >,,=<字母 > | <标识符 ><字母 > | <标识符
><数字 >
…,
通过上述定义可知，所有以字母开头的，由字母和数字组成的字符串都是标识符。
BNF定义了一种语言，其中标识符如上定义。
BNF描述它所定义的语言，为元语言。
17College of Computer Science & Technology,BUPT
例如：汉语语法中定义了句子的结构由主语,谓语,
宾语组成 。 这里主谓宾只是描述了句子的结构,并不是句子 。 而按照这种结构组成的建立在汉字上的字符串就是句子 。 如他是学生 。
文法是一种元语言,一种方法,根据文法产生出语言的句子 。
18College of Computer Science & Technology,BUPT
三,Chomsky文法体系
例如：
BNF <标识符 >::=<字母 >
<标识符 >::=<标识符 ><字母 >
<标识符 >::= <标识符 ><数字 >
<字母 >::=a|b|…… z|A|B|…… |Z
<数字 >::=0|1|…… 9
将,:= 改为 → 表示可被代替用 I,L,D分别表示标识符,字母,数字 ;
19College of Computer Science & Technology,BUPT
则上述表达式可以表示为
I→L
I→IL
I→ID
L→a|b|….|z
D→0|1|….9
这就是一个文法的生成式集合。
20College of Computer Science & Technology,BUPT
Chomsky文法体系中,任何一种文法必须包含有两个不同的有限符号的集合,即非终结符集合
N和终结符集合 T。 一个形式规则的有限集合 P
（ 生成式集合 ）,一个起始符 S。
P中的生成式是用来产生语言句子的规则,而句子则是仅由终结符组成的字符串 。 这些字符串必须从一个起始符 S开始,不断使用 P中的生成式而导出来 。
可见文法的核心是生成式的集合,它决定了语言中句子的产生 。
21College of Computer Science & Technology,BUPT
文法的形式定义
文法 G是一个四元组 G=(N,T,P,S),其中
N 非终结符的有限集合
T 终结符的有限集合 N∩T=Φ
P 形式为 α→β 的生成式的有限集合 。
且 α∈ (N∪ T)* N+ (N∪ T)* β∈ (N∪ T)*
S 起始符 且 S ∈ N。
22College of Computer Science & Technology,BUPT
将上例用文法表示
G=(N,T,P,S)
N = { I,L,D}
T = { a,b,c,… z,0,1,… 9}
P = { I,La,…,D0,…,D9}
S = { I }
文法是语言的产生系统,研究怎样构造文法能产生出符合要求的句子 。
23College of Computer Science & Technology,BUPT
四．推导与句型
1,直接推导设 G =（ N,T,P,S） 是文法,若 A→β 是 P
中的生成式,α和 γ是 （ N∪ T） *中的字符串,则有 αAγ=> αβγ称 αAγ直接推导出 αβγ,或说 αβγ是 αAγ的直接推导 。
24College of Computer Science & Technology,BUPT
设 G = (N,T,P,S) 是文法,α,α0,α1… αn,α’ 都是
（ N∪ T） *中的字符串,且 α=α0,α’ =αn,其中 αi直接推导出 αi+1 （ 0≤i≤n）,则称序列 α0=>α1=>α2=>… =>αn是长度为 n的推导序列,而 α=α0是长度为 0的推导序列 。
对 α推导出 α’记为 α α’,若推导序列长度大于 0,则记为 α α’。
推导序列的每一步,都产生一个字符串,这些字符串一般称为句型 。
2、推导序列
*G
G
25College of Computer Science & Technology,BUPT
3、句型和句子
句型字符串 α是文法 G的句型,当且仅当
S α,且 α∈ （ N∪ T） *。
句子
ω是 G的句子,当且仅当 S ω,且 ω∈ T*。 （ ω是由终结符组成的字符串 ）
例,I =>L =>a
I =>IL =>LL =>zL =>zb
句型包含句子
*G
*G
26College of Computer Science & Technology,BUPT
4．文法产生的语言由文法 G产生的语言记为 L(G)。
L(G) = {ω|ω∈ T*且 S ω}
或：
L(G)中的一个字符串,必是由终结符组成的,并且是从起始符 S推导出来的 。
*G
27College of Computer Science & Technology,BUPT
第三节 Chomsky文法体系分类
文法 G = (N,T,P,S)； P,α→β
其中 α∈ （ N∪ T） * N+（ N∪ T） *
β∈ （ N∪ T） * 属于 Chomsky文法体系
该体系对生成式的形式做了一些规定,分为四类,即 0型,1型,2型,3型文法
0型文法：无限制文法对应的语言：递归可枚举语言,与图灵机等价 。
28College of Computer Science & Technology,BUPT
1型文法
也称上下文有关文法（ CSG,Context-
sensitive Grammar)
生成式的形式为 α→β,
其中 |α|≤|β|,β∈ （ N∪ T） +，
α∈ （ N∪ T） *N+（ N∪ T） *
对应的语言：上下文有关语言（ CSL：
Context-sensitive Language)
若不考虑 ε,与线性有界自动机（ LBA,
Linear Bounded Automaton） 等价。
29College of Computer Science & Technology,BUPT
2型文法
也称上下文无关文法 （ CFG,Context-free
Grammar)
A→α,
A∈ N,且 α∈ （ N∪ T） *
对应的语言：上下文无关语言 （ CFL：
Context-free Language)。
对 应 的 自 动 机,下 推 自 动 机 （ PDA：
Pushdown Automaton)。
30College of Computer Science & Technology,BUPT
3型文法也称正则文法
右线性文法（ Right-linear Grammar）：
A→ωB 或 A→ω
A,B∈ N,ω∈ T*。
左线性文法（ Left-linear Grammar）：
A→Bω 或 A→ω
A,B∈ N,ω∈ T*。
对应的语言：正则语言
对 应 的 自 动 机,有 限 自 动 机 （ Finite
Automaton） 。
31College of Computer Science & Technology,BUPT
例 1：
G = ({A,B,C},{a,b,d},P,A)
P,A→AB ； AB→CAAB ； A→d ； B→a ； C→b
是 1型文法。
A=>d
A=>AB =>dB =>da
A=>AB =>ABB =>dBB =>daB =>daa
A=>AB =>CAAB =>bAAB =>bdAB =>bdCAAB
=>bdbAAB =>bdbdAB=>bdbddB =>bdbdda
32College of Computer Science & Technology,BUPT
例 2：
G = ({A,B,C},{a,b,c},P,A)
P,A→abc A→aBbc Bb→bB Bc→Cbcc bC→Cb
aC→aaB aC→aa 是 1型文法。
其定义的 L = {anbncn | n≥1}
A =>abc
A =>aBbc =>abBc =>abCbcc =>aCbbcc =>aabbcc
=>aaBbbcc
33College of Computer Science & Technology,BUPT
例 3：
G = ({S,B,C},{a,b},P,A)
P,S→aC ； S→bB ； B→aS ； B→bBB B→a ；
C→bS ； C→aCC ； C→b 是 2型文法
S =>aC =>ab
S => aC =>aaCC
S =>aC =>abS =>abaC =>ababS =>ababaC
=>ababab
S =>bB =>bbBB =>bbaSB =>bbaaCB
=>bbaabB =>bbaaba
34College of Computer Science & Technology,BUPT
例 4：
G = ({A,B,C},{a,b,c},P,A)
P,A→Ba ； A→c ； B→Cb ； C→c
左线性文法
L = {c,cba} 正则语言
注意：已知语言求文法,文法不是唯一的,即可以有不同的表达方法 。
35College of Computer Science & Technology,BUPT
四类文法之间的关系
只是对生成式形式加以限制
0型 无限制
1型 不允许 A→ε 形式
2型
3型 属于 2型
不含 A→ε 的 2型,3型属于 1型,1型,2
型,3型均属于 0型 。
36College of Computer Science & Technology,BUPT
作业,P47 4,6,7 题
