第七章 句法结构模式识别形式语言概述文法推断句法分析自动机理论误差校正句法分析
§ 7-1 形式语言概述一、基本概念
1、字母表,与所研究的问题有关的符号集合。
例,V1={A,B,C,D},V2={a,b,c,d}
2、句子 (链 )：由字母表中的符号所组成的有限长度的符号串。
3、句子 (链 )的长度,所包含的符号数目。例,|a3b3c3|=9
4、语言,由字母表中的符号组成的句子集合，用 L表示。
例：字母表 V={a,b}
L1={ab,aab,abab} 有限语言
L2={anbm|n,m=0,1,2….} 无限语言
5、文法,在一种语言中，构成句子所必须遵循的规则的集合，
用 G表示。 L(G)表示由文法 G构成的语言。
6,V*:由字母表 V中的符号组成的所有句子的集合，包括空句子
λ在内。例,V*＝ {λ,01,001}
7,V＋,不包括空句子在内的句子集合，即 V＋ ＝ V*－ (λ)
8,VT,终止符，不能再分割的最简基元的集合，用小写字母表示。 VT={a,b,c}
9,VN,非终止符，由基元组成的子模式和句子的集合。用大写字母表示。 VN={A,B,C}
VT,VN的关系,VT∩ VN= Φ(空集 )
VT∪ VN= V（全部字母表）
10、产生式 (再写规则 )P：存在于终止符和非终止符间的关系式。
例,α→β,α? VN,β? VN,VT.
11、文法的数学定义,它是一个四元式，由四个参数构成。
G={VN,VT,P,S}
二,短语结构文法
1,0型文法 （ 无限制 ）
设文法 G = (VN,VT,P,S)
VN,非终止符,用大写字母表示
VT,终止符,用小写字符表示
P：产生式
S：起始符产生式 P,α→β,其中 α? V+,β? V* α,β无任何限制
( V+不包括空格,V*包括空格 )
例,0型文法 G = (VN,VT,P,S)
VN = {S,A,B}
VP = {a,b,c}
P,① S→aAbc ② Ab→bA ③ Ac→Bbcc
④ bB→Bb ⑤ aB→aaA ⑥ aB→λ(空格 )
S→Aa bc→abAc→abBbcc→aBbbcc→ bbcc
此文法可以产生,X=anbn+2cn+2 n≥0
X|n=0=bbcc
由 0型文法产生的语言称为 0型语言 。
2,1型文法 （ 上下文有关文法 ）
设文法 G = (VN,VT,P,S)
产生式 P,α1Aα2→α1βα2
其中 A? VN,β? V+,α1,α2? V*
|α1Aα2|≤|α1βα2|,或 |A|≤|B|
由上下文有关文法构成的语言称为上下文有关语言，
用 L(G1)表示,G1：上下文有关文法
① ② ③ ④ ⑥
例,G = (VN,VT,P,S)
VN = {S,B,C} VT = {a,b,c}
P,① S→aSBC ② CB→BC ③ S→abC ④ bB→bb
⑤ bC→bc ⑥ cC→cc
λ1Sλ2→λ1aSBCλ2,bBλ→bbλ
对于 S→aSBC
∵ α 1= λ,α 2= λ,A = S,B=aSBC,并且 |S|<|aSBC|
∴ 符合 1型文法规则对于 bB→bb
∵ α 1= b,α 2= λ,A = B,B=b,并且 |B| ≤ |b|
∴ 也符合 1型文法规则产生式都符合 1型文法的要求
S→aSBC→aabCBC→abbBCC→aabbCC→aabbcC→aabbcc
∴ X=a2b2c2
此文法 G可产生的语言,L(G)={anbncn|n=1,2...}
假设基元语言 L(G)可以描述不同的三角型
X= abc X= a2b2c2
a
b c
① ②③ ④ ⑥⑤
a
bc
c
c
b
b
a a
2,2型文法（上下文无关文法）
设文法 G = (VN,VT,P,S)
产生式 P,A→β 其中 A? VN（ 且是单个的非终止符 )
β? V+ (可以是终止符,非终止符,不能是空格 )
对产生式的限制比较严格由上下文无关文法构成的语言称为上下文无关语言 。
例：文法 G = (VN,VT,P,S)
VN = {S,B,C}
VT = {a,b}
P,① S→aB ② S→bA ③ A→a ④ A→aS
⑤ A→bAA ⑥ B→b ⑦ B→bS ⑧ B→aBB
aB→abS→abaB→abab
S abbA→abba
bA→baS→baaB→baab
babA→baba
例,G = (VN,VT,P,S)
VN = {S,T,F}
VT = {a,+,*,(,)}
P,① S→S+T ② S→T ③ T→T*F ④ T→F
⑤ F→(S) ⑥ F→a
S→S+T→T+T→F+T→a+T→a+T*F→a+F*F→a+a*F→a+a*a
① ⑦
③
④
③
⑥
⑥
①
①
②
②
②
① ② ④ ⑥ ⑥⑥③ ④
两种方法替换非终止符：
① 最左推导：每次替换都是先从最左边的非终止符开始，
例如上边的例子。我们经常采用最左推导。
② 最右推导：每次替换都是先从最右边的非终止符开始，
例如,S→S+T →S+F →S+a → T+a → F+a → a+a
3,3型文法 （ 有限状态文法 ）
文法 G = (VN,VT,P,S)
产生式 P,A→aB 或 A→a,（ 对产生式限制最严格 ）
其中 A,B? VN（ 且是单个字符 ）,a? V T(且是单个字符 )
由 3型文法产生的语言成为 3型语言 。
例：文法 G = ({S,A},{0,1},P,S)
P,① S→0A ② A→0A ③ A→1
S→0A→00A→000A→0001
L(G)={0n1|n=1,2...}
例：构造文法 G能产生语言 L(G) = {x|x=0n 10m | n,m>0}
解,G = (VN,VT,P,S)
VT=(0,1)
P,① S→0B ② B→0B ③ B→1S ④ B→0
∴ VN=(S,B)
四种文法的关系,
包含关系：限制不严格的文法必然包含限制严格的文法。
3型 2型
1型
0型三,图象描述语言（ PDL）
1970年,Show提出图像描述语言任何图象都可用头尾来表示定义了四种二元连接算子
1,a + b
2,a x b
3,a – b
4,a * b
t
h
a头与 b尾相连
h
ht a尾与 b尾相连,形成两个头
ht
t
a头与 b头相连，形成一头二尾
a头连 b头,a尾连 b尾，形成一头一尾
h
htt
h
t
基元 b
a b
a
b
a
b
头 头尾 尾一元算子 ~
一个基元的头或尾可以与另一基元的头或尾相连而成为模式串，并可设置一些较复杂的联结关系和进行各种运算。
例：文法 G = (VN,VT,P,S)
VT = { →,↗,↘,↓,(),+,-,x,*,~ } VN= {S,A,B,C}
P,① S→A ② S→B
③ A→(b+(C+c)) ④ B→(d+(a+(~d))*C),
⑤ C→((b+c)*a)
h
t
b
h
t
~b
a b c d
L(G) = {(b+(((b+c)*a)+c)) ; ((d+(a+(~d)))*((b+c)*a))}
b c
a
a
d ~d
b
b
c
ca
CB
S
d
b~
+
导出过程
d
a +
+ c * a
S
A
b +
c+C
b + c * a
求ＰＤＬ表达式的规则：
① 脱括号由内往外的次序进行,无括号由左向右进行
② 对于连接基元组成基元结构,必须符合规定的连接点头,尾数目例：给出一个 PDL文法
G = ({S,A,B,C,D,E},{a↗,b ↘,→,d↓,(,),+,*,~},P,S)
P,① S →(A+(B)) ② B →(C)+D
③ D →b ④ E →(a+b)
⑤ A →d ⑥ C → E*c
⑦ D → (~d) ⑧ A →a
c
可以导出手写大写字符,A‖的四种表达式
S →(A+(B)) →(a+(B)) →(a+((C)+D) ) →(a+((E*c)+D))
→(a+(((a+b)*c)+D)) →(a+(((a+b)*c)+(~d)))
(d+(((a+b)*c)+b)),? (a+(((a+b)*c)+b)),? (d+(((a+b)*c)+(~d)))
① ⑧ ② ⑥
④ ⑦
a
d
b
b
a
a
b
b
ba
~dd c~d
a
a
b
c
四,标准形式文法在句法分析和自动机的一些算法中,有时要求标准化文法,下面介绍二种标准文法 。
1,乔姆斯基 (Chomsky)范式,一种上下文无关文法如果它的每个产生式 P都符合二种形式：
A→BC (A,B,C? VN)或 A→a (A? VN,a? VT)
该文法称 Chomsky范式已知上下文无关文法 G = (VN,VT,P,S)用以下步骤产生
Chomsky范式的等价文法
G = (VN,VT,,S)
① 若Ｐ中已经是 A→BC,A→a形式放入 中
② Ｐ中其它的产生式形式为 A→ θ1θ2…,θn
其中 θi? VN 或 θi? VT
P
P
用下面的产生式集合代替：
A→Y1Y2...n
Y2...n→Y2Y3...n
…
Yn-1...n→Yn,,n-1 Yi? VN
若 θi? VN,则令 Yi=θi；若 θi? VT,再引入 Yi→θi
例：把文法 G = (VN,VT,P,S)变成 Chomsky范式
VN = {S,A,B}
VP = {a,b}
P,S→AB,A→a,A→abABa,B→b
① 把 S→AB,A→a,B→b放入 中
② A→abABa,A→θ1θ2θ3θ4θ5，
其中 θ1=θ5=a,θ2=b,θ3=A,θ4=B
A→Y1Y2345,Y2345→Y2Y345,Y345→Y3Y45,Y45→Y4Y5,
∵ θ3,θ4? VN ∴ Y345→AY45,Y45→BY5,
∵ θ1θ2θ5? VT
∴ 引入新的产生式,Y1→a,Y2→b,Y5→a
P
符合 chomsky范式文法,文法 G2 = (VN,VT,,S)
VN = { Y1Y2345,Y2Y345,Y45,Y5,S,A,B}
A→Y1Y2345,Y1→a,Y2345→Y2Y345,Y2→b,Y345→AY45,
Y45→BY5,Y5→a,
S→BA,A→a,B→b
若 x=bababa
用 G1导出,S→BA→bA→babABa→bababa,
用 G2导出,S→BA→b Y1Y2345...→baY2345→
baY2Y345→babY345→babAY45 →babaY5
→bababY5→bababa
用原文法 G1 只用四步可以导出 bababa而用标准文法 G2则用九步才导出
P
2,格雷巴赫范式 (Greibach)
若一个上下文无关文法具有 P形式：
A→aα,A? VN,a? VT,α? VN*(带空格 ) 则此文法称为
Greibach范式。
例：上下文无关文法
G = (VN,VT,P,S)
VN = {S,C},VT = {a,b,c}
P形式,S→aCbb,C→aCbb C→c
变成 Greibach范式,C→cλ即 C→c符合 Greibach范式,不变
S→aCbb,用 S→aCBB,B→b代替
C→aCbb,用 C→aCBB,B→b代替符合 Greibach范式：
P,S→aCBB,C→aCBB,C→c,B→b,
五,高维文法,上面我们介绍的都是一维链 （ 串 ） 文法,为了描述更复杂的图形,图象,需要用高维文法,包括树文法,图文法,
网文法等等 。
1,树文法：
定义：四元组 Gt = (v,r,P,S)
其中 V=VN∪ VT,r,秩 (一个节点的直接分支数 )
P形式,Ti→Tj Ti,Tj都是树由 Gt产生的语言叫树语言 。
L(Gt)={T| T? T∑,Ti→T Ti? S },T∑ 是带有 VT中结点的树集合扩展树文法,全部产生式形式其中 x1,x2..,xn? VN,x? VT,n? r(x)
具有上面产生式形式的树文法称扩展的树文法 。
Gt
X x
x1,x2… xn
例,Gt = (v,r,P,S)
V=VN∪ VT ＝（ S,A,B,K,a,b）
VT ＝ ( →,↗ ),r(a)=(2,0),r(b)=(2,0),r(k)=2
P,① S→K ② A→a ③ B→b
④ A→a ⑤ B→b
∴ S→K
a b
A B A B A B
A B
a b
①
④ ⑤
a
bk
A B
①
④⑤
S→K
a b
A B A B
④ ⑤
② ③ a
b
k
导出树导出图
b baa
例 2：在氢云室内用正粒子打击核目标碰撞发出的射线可以用树文法来描述。
树文法 Gt = (v,r,P,S),VN＝（ S,A,B）,VT ＝ (a,b)
基本定义：
P:
a
b
(凸弧 ) (凹弧 )
S → a
|
S
S → a
A B
S → a
A BBA
S → a
A BBAA B
A → a
|
A
A → a B → a
|
B
B → a
r(a)=(0,1,2,4,6),r(b)=(0,1)
射线导出树：
S → a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
b
b
b
b
b
b
b
b
b
b
b
b
b
a
a
b
射线图：
§ 7-2 文法推断根据已知 L(G)样本集导出未知文法 G的过程 。
(一 )基本定义：
1.若在产生式中至少有一个产生式存在以下形式：
Ai→αiAiβi
此文法 G = (VN,VT,P,S) 是循环文法或不确定,由它产生的语言 L(Gt)为无限的 。
2.若文法 G为不循环的,则必为确定的,且 L(G)为有限的 。
样本集 推断算法 GtSt=(x1,x2… x t)
导师
3.当 L(GA)= L(GB)时,则 GA与 GB等效,等价 。
例：有限状态文法 GA = (VN,VT,P,S),VN = {S},VT = {0,1}
P:S→0S,S→1
则 L(GA)={0n1|n=1,2,… }
上下文无关文法 GB = (VN,VT,P,S),VN = {S,A},VT = {0,1}
P:S→A1,A→AA,A→0 则 L(GB)={0n1|n=1,2,… }
∴ L(GA)= L(GB) ∴ GA与 GB等效
4.S+是 L(G)的子集,即 S+? L(G),称为正取样,是 子集,
记为 称为负取样,
5.若正取样 S+=(x1,x2…,,xi)= L(G),称为 S+是完备的,负取样
= (x1,x2…,,xi) =,称 也是完备的,
且 St=(S+,S-)=(x1,x2…,,xi)=( L(G),)也是完备的 。
S? )(GL?
)(GLS
S? )(GL? S?
)(GL?
(二 ) 有限状态文法推断状态图表示方法,文法可以用图来表示例,G = (VN,VT,P,S)
VN = {S,A,B,C}
VT = {0,1}
P,① S→0A ② A→0A
③ B→0 ④ B→0B
⑤ S→1B ⑥ A→1B
⑦ C→0C ⑧ S→1C
⑨ A→1 ⑩ C→1
T：附加状态此文法可以产生的字符串
x1=00n1,x2=0n+110m+1,
x3=10n+1,x4=10n1
A
S
CB
T
0
0 0
0
11
11
1
0
一,规范确定文法已知正取样 S+=(x1,x2…,,xn)
推断规范文法 Gc = (VN,VT,PL,S)的步骤如下：
① VT = S+中不同的终止符
② 设 xi= ai1ai2..,ain链
∴ PL,S→ai1Zi1 Zi1? VN,ai1? VT
Zi1→ai2Zi2 Zi2? VN,ai2? VT
…
ZIn-2→ain-1Zi n-1 Zin-1? VN,ain-1? VT
ZIn-1→ain ain? VT
∴ VN={S,Zi1,Zi2,..,Zin-1,}
此文法产生的语言是确定的,有限的,且有性质,L(GL)=S+
例：已知 S+=(01,100,111,0010)
① VT ={0,1}
② ∵ x1=01,∴ S→0Z1,Z1→1
x2=100,S→1Z2,Z2→0Z3,Z3→0
x3=111,S→1Z4,Z4→1Z5,Z5→1
x4=0010,S→0Z6,Z6→0Z7,Z7→1Z8,Z8→0
∴ VN={S,Z1,Z2,..,Z8 }
推断出的文法为,Gc = (VN,VT,Pc,S)
VN={S,Z1,Z2,..,Z8,},VT ={0,1}
PL,S→0Z1,Z1→1,S→1Z2,Z2→0Z3,Z3→0,S→1Z4
Z4→1Z5,Z5→1,S→0Z6,Z6→0Z7,Z7→1Z8,Z8→0,
状态图：
显然对任一有限取样都可用此法推断出规范文法，方法简单，适用计算机运算。缺点是非终止符太多，产生式也多。
S
Z1
Z2
Z3
Z4
Z5
Z6
Z7
Z8T
0
0
0
0
0
0
1
1 1
1
1 1
二,导出文法 （ 简化规范文法 ）
设,Gc为规范文法,非终止符集合 VN={S,Z1,Z2,..,Zn },把
VN分成 r个子集,VND={Bj,B1,B2..,Br} S? Bj,Zi? Bj
这些子集满足：
Bj∩B k=Ф,j≠k
∪B j = VN
定义导出文法 GD = (VND,VT,PD,Bs)是由规范文法 Gc产生的文法,导出规则如下：
① VT相同
② VND = (Bs,B1,B2,… Br)
③ Bs为起始符,Bs=S
④ PD定义,a,若 Zα→αZβ 在 Pc中,则 PD中有
Bi→αBj,Za? Bi,Zβ? Bj
b,若 Zα→a在 Pc中,则 PD中有 Bi→a,Za? Bi
r
j=s
例,S+=(01,100,111,0010)
规范文法 Gc = (VNC,VT,Pc,S)
VNC = {S,Z1,Z2,… Z8}
对 VNC分割为：
VND = {(S),(Z1,Z6,Z7),(Z2,Z3,Z8),( Z4,Z5)}={ Bs,B1,B2,B3}
对于 S→0Z1∵ S? BS,Z1? B1 ∴ PD中有 BS→0B1
对于 Z1→1 ∵ Z1? B1 ∴ PD中有 B1→1
同理,BS→1B2,B2→0B2,B2→0,
BS→1B3,B3→1B3,B3→1
BS→0B1,B1→0B1,B1→1B2,B2→0
把相同的产生式合并后有：
Pc,BS→0B1,BS→1B2,BS→1Bs,B1→1,B1→0B1，
B1→1B2,B2→0B2,B2→0,B3→1B3,B3→1
状态图导出文法等效规范文法 L(GC)=L(GD)
这种方法由于分割方式不同会导出不同的文法而分割方式又无系统理论作指导,而靠经验和试探 。
B5
B3B2B1
T
0
0
11
1
1
1
1
0
0
三,形式微商文法形式微商定义：集合 A对于符号 a? VT的形式微商是：
DaA={X|ax? A }
若 a=λ(空串 ),则 DλA=A
例,A=S+={01,100,111,0010}
则 D0A= D0S+={1,010}
D1A= D1S+={00,11}
扩展：二次微商 Da1a2A=Da2(Da1A)
n次微商,Da1a2… an－ 1anA= Dan(Da1a2… an－ 1)A
对上例,D00 S+= D0 (D0 S+) = D0 (1.010)=(10)
D11 S+= (1) D000 S+ =Φ,D100 S+={λ}
已知正取样 S+={x1,x2,...xn}T
形式微商文法 GCD = (VN,VT,P,S),定义如下：
① VT =（ S＋ 中不同的符号 ）
② VN = U=(U1,U2,… UP) 其中 Ui( i=1,2… p)是 S+的形式微商,
且令 U1=DλS＋
③ 起始符,S=U1=DλS＋
④ 令 Ui,Uj? VN
P,当 DaUi= Uj,则 Ui→aUj
当 λ? DaUi,则 Ui→a
例,S+={101,111},推断形式微商文法如下：
① VT =（ 0,1）
② DλS＋ = S＋ ={101,111}= U1=S 起始符
③ ∵ D1S＋ ={01,11}= D1S= U2 ∴ S→1U2
∵ D10S＋ = D0(D1S＋ )= D0U2={1}= U3 ∴ U2→0U3
∵ D11S＋ = D1(D1S＋ )= D1U2={1}= U3 ∴ U2→1U3
∵ D101S＋ = D1(D10S＋ )= D1U3={λ} ∴ U3→1
∵ D111S-＋ = D1(D11S＋ )= D1U3={λ} ∴ U3→1
形式微商文法为 (相同产生式合并 )：
GCD = (VN,VT,P,S)
VT =（ 0,1） VN =（ S,U2,U3）
P,S→1U2,U2→1U3,U2→0U3,U3→1
状态图为：
S
U2 U3 T
1
10.1
四,k-尾文法,对形式微商文法进行长度限制,并对等价状态进行合并
k尾定义,ф(U,A,k)={X|X? DaA |X|≤k}
形式微商文法中两个状态间的等效性的充要条件为：
ф(XiS+k)= g(XjS+k)-k尾相等利用 k尾等效把形式微商文法中的等效状态合并,
导出 k尾文法 。
例,S+={01,1001}
① 先求形式微商文法
∵ DλS+= S+={01,1001}= U1=S
D0S+={1}= U2 ∴ S→0U2
D01S+= D1(D0S+)= D1U2={λ} ∴ U2→1
D1S+={001}= U3 ∴ S→1U3
D10S-= {01}= D0U3=U4 ∴ U3→0U4
D100S+= {1}=D0U4= U5 ∴ U4→0U5
D1001S+= {λ} ∴ U5→1
② 求 k尾等效状态,|X|≤k
k=4,k=3,k=2,k=1
U1=DλS+= {01,1001},{01},{0,1},{ф}
U2=D0S+= {1},{1},{1},{1}
U3=D1S+= {001},{001},{ф},{ф}
U4=D10S+= {01},{01},{01},{ф}
U5=D100S+= {1},{1},{1},{1}
等效状态为 k=4,k=3,k=2,k=1
(U2,U5) (U1,U4) (U1,U4) (U1,U3,U4)
(U2,U5 ) (U2,U5) (U2,U5,)
③ 合并状态,导出 k尾文法
k=4时 S→0U2,U1→1,S→1U3,U3→0U4,U4→0U2
k=3,2时 S→0U2,U2→1,S→1U3,U3→0S
k=1时 S→0U2,U2→1,S→1S,S→0S
状态图讨论：推断 k－尾文法时,k尾的选择很重要,k小时文法简单，但循环产生式增多，这样就可以导出更多的 S+
以外的子串来，有时这是不允许的。
1
S S
S
T
T
T1
1
1
U2
U3
U4
U2 U3
U2
0
0
00
0
0
0,1
1
K=2,3
K=1K=4
三,树文法推断一棵树可以看成一个多枝的链 。 因此前边讲的链 （ 串 ）
文法的推断方法可以用在树文法的推断上 。 任何一个数字化的网络模板都可以用树结构来表示如下：
由下面的四种方式表示成树枝全从根开始的树 。
X11 X12,..,.,X1n
X21 X22,..,.,X2n
...,..,..,..,..
Xn1 Xn2,..,.,Xnn
树状的数字化网络模式
S 根树干
N个枝
S
树干
M个枝…..…..
① 树文法先选一个合适的树干,由树干推出一个链文法
② 再推各树枝的文法
③ 把树干文法与树枝文法合并树干树干树枝树枝根 S
S
例：已知数字化模式
L1 L2 L3 L4 L5 L6
0 0 0 1 1 1
0 0 0 1 1 1
1 1 0 0 0 0
1 1 0 0 0 0
1 1 1 1 0 0
1 1 1 0 0 0
1 1 0 0 0 0
1 0 0 0 0 0
R1 R2 R3 R4 R5 R6
树干根 S
① 先由树干推出树干文法 GA
P,S → A1
A1 → $— A2
|
|
R1
L1
A2 → $— A3
|
|
R2
L2
A3 → $— A4
|
|
R3
L3
A4 → $— A5
|
|
R4
L4
A5 → $— A6
|
|
R5
L5
A6 → $
|
|
R6
L6
② 上面推出树干文法 GA,再推出树枝文法 GL1,
GL2..,GL6,GR1,GR2,..,GR6
③ 再将树干文法与树枝文法合并 GT= GA∪G L∪G R
§ 7-3 句法分析一,用句法分析作模式识别设给定训练样本为 M类即,ω 1,ω 2,… ω M
每类有 N个样本,如 ω 1的训练样本为,S=(X1,X2,… XN)T
由这些样本可以推断出 ω 1类的文法 G1,同样方法可推断出 ω 2类的文法 G2,…,ω M类的文法 GM,对待识别句子 X进行句法分析,若 X属于由文法 Gi构成的语言 L(Gi),则
x? ω i 类 。
框图如下：
X? L{G1}
G1
X? L{G2}
G2
X? L{GM}
GM
x 判决 X? ω i
……
句法分析过程识别结果待识别句子二句法分析的主要方法
1参考匹配法：
2状态图法：适用于有限状态文法例,G = (VN,VT,P,S)
VT =（ 0,1） VN =（ S,A,B,C）
P,S→ 1A,S→ 0B,S→ 1C,A→ 0A,A→ 0
B→ 0,C→ 0C,C→ 0,C→ 1B
X? 样本链码 X1
X? L{G2}x
……
样本链码 X2
X? 样本链码 XN
判决 X?ω
i
X? Xi
S
CBA
T
1 10
0
0
1
0
由状态图可以知道此文法可以识别的句子
X1=10n+1,X2=00,
X3=10n10,X4=10n+1
未知句子：由状态图可知
x1=10010(可以识别 )
x2=10110(不可以识别 )
0
0
状态图
2,填充树图法 (适用于上下文无关文法 )：
当给定某待识别链 X及相应的文法 G时,我们建立一个以 X
为底,S为顶的三角形,按文法 G的产生式来填充此三角形,
使之成为一个分折树 。 若填充成功表明否则填充树有二种方法
① 由顶向底剖析
② 由底向顶剖析填充树图法在填充三角形时应遵守三条原则：
① 首位考察：首先考虑选用某个产生式后能导出 X的第一个字符
② 用某产生式后,不能出现 X中不包含的终止符
③ 用某产生式后,不能导致符号串变长 (变短 )
)(GLX?
)(GLX? S
X
由顶向底 (由上而下 )剖析例,G = (VN,VT,P,S) VT =（ 0,1） VN =（ S,A,B）
P,① S→ 1 ② S→B 1 ③ S→B ④ B→ 1A
⑤ B→B 1A ⑥ A→ 0A ⑦ A→ 0
设,X=1000,用由上而下剖析方法判断 X是否属于 L(G)
B B
1
0 A
A
S
B
S
1 A
S
A0
0
⑦
∴ X=1000? L(G) ⑥
⑥
③
④
由底向顶 (由下而上 )剖析例,G = (VN,VT,P,S)
VT =（ a,b,c,f,g） VN =（ S,T,I）
P:① S→T ② I→a ③ S→Tfs ④ I→b
⑤ T→IgT ⑥ I→c ⑦ T→I
设,X=afbgc
① 用 I→a
② 用 T→I
③ 用 I→b
④ 用 I→c
⑤ 用 T→I
a f b g c
↓
I
a f b g c
↓
I
↓
T
a f b g c
↓
I
↓
T
↓
I
a f b g c
↓
I
↓
T
↓
I I
↓
a f b g c
↓
I
↓
T
↓
I I
↓
↓
T
① ② ③ ④
⑤ ⑥
a f b g c
↓
I
↓
T
↓
I I
↓
↓
T
T
a f b g c
↓
I
↓
T
↓
I I
↓
↓
T
T
↓
S
a f b g c
↓
I
↓
T
↓
I I
↓
↓
T
T
S
⑥ 用 T→IgT
⑦ 用 S→T
⑧ 用 S→TfS
S
⑦ ⑧
∴ X=afbgc? L(G)
三、杨格 (Younger)法
Younger法是个较前述各方法更系统的方法，适用于任何相应于 2型文法类别的识别。下面结合一例说明此方法。
设有一代表类别的文法 G = (VN,VT,P,S)其中
VT =（ 0,1,2） VN =（ S,B）
P,① S→SBS ② B→BB ③ B→BS
④ S→ 2 ⑤ B→ 0 ⑥ B→ 1
现在要用 Younger法来识别 X=202102是否? G.
首先将上述文法化为 Chomsky标准形式 。 此形式文法的代换式只有两种形式,即非终止符 → 非终止符?非终止符 （ 双非终止符形式 ）
非终止符 → 终止符 （ 终止符形式 ）
将式上所示文法中第 1条改为 S→SA,A→BS 两条（ A为人为增加的非终止符），使整个文法成为：
① S→SA ② A→BS ③ B→BB
④ B→BS ⑤ S→ 2 ⑥ B→ 0 ⑦ B→ 1
而令 VT =（ 0,1,2） VN =（ S,A,B）便完成了 Chomsky形式的转化。 Younger法将对 Chomsky形式文法进行分析。
待识别符号串的任一,子串,都可用 i,j两个整数来指明：
所谓子串即把一符号串任一截取一段，这段符号串（包括单个符号）就叫原来符号的子串。譬如符号串 202102的子串就有 2,0,2,1,0,2（个数为 1的子串）； 20,02,21，
10,02（个数为 2的子串）； 202,021,210,102（个数为 3
的子串）； 2021,0210,2102（个数为 4的子串）； 20210，
02102（个数为 5的子串）和 202102（个数为 6的子串即原符号串）。
这 21个符号串都可由正整数 i,j表示。 i代表子串中符号的个数（即子串长度），而 j表示这子串的首位在原符号串中占第几位。如上面所举的第 1子串,2‖，即为 i=1,j=1
的子串，第 13个子串 021即是 i=3,j=2的子串。可见，任一子串都可用 i,j二数来指明。
识别表的建立，关键问题是根据给出的待识别串 X,建立一识别表。对于 202102,根据所给出的文法算得的识别表如下：
i 1 2 3
j 1 2 3 4 5 6 1 2 3 4 5 1 2 3 4
所有子串 2 0 2 1 0 2 20 02 21 10 02 202 021 210 102
所有
VN
S √? √ √ √
A √ √ √
B? √? √ √ √? √ √? √? √
4 5 6
1 2 3 1 2 1
2021 0210 2102 20210 02102 202102
√ √
√?
√ √?
表中每一位置由三个符号表示。头二个即 i和 j，而第三个是非终止符 (现为 S,A,B,见表中第一列 ).。 i＝ 1栏中第 2列
(j=2)与 B行相交的位置即为 (1,2,B),余类推。表中 (1,2,B)位置上有 √,代表对于所给文法,B可导出 i=1,j=2的子串，
即,0‖。反之，若这位置上为?，则说明 B不能导生子串
,0‖。
再举一例，第 2栏中第 2列,A行位置应该用（ 2,2,A）表示，
此位置上有 √,代表对于所给文法,B可导出 I=2,j=2的子串，即,02‖（见表）。（ ）
经分析可知，能容易地根据给出的符号串 (202102),在 i=1栏的各位置上打 √ 或?,又根据此栏结果，由一递推公式将
i=2栏各位置打上 √ 或? 。如此递推下去便可将表填满，识别表也就建成。在识别时只需检查最后一栏 ( 现为 i=6栏 ) 第一列第 S行位置 [即 (6,1,S)]上是 √ 还是?。若是 √,表示 S可导生子串 202102，故判 202102符合给出的文法。反之，即判不符合此文法。
020 SBSA
建立识别表的递推规则递推规则：将要决定 √ 或? 的位置表为 (i,j,k)通用形式。
K代表非终止符。又将 r(i,j,K)称为 (i,j,k)位置的识别值。
此值为 0或 1，分别表示 (i,j,k)位置上是 √ 或? 。计算 r(i,j,K)
(也即决定 √ 或? )的步骤是：
(i)算出其中 K1,K2代表 K→ K1K2.例如,A→ BS,K=A,K1=B,K2=S.
),1,1(),,1(
),2,2(),,2(
),1,1(),,1(
21
21
21
KijrKjir
KjirKjr
KjirKjr
（ 1）
(ii) 如果 (i,j,k)左侧是 K的代换式不只一个，譬如 K是 B时，
即有 B→ BB,B→ BS两个。这时则把 B,B叫做 K1,K2，根据它计算式 (1)中各值；此外，还需将 B,S叫做 K1’,K2’，
再按下面式算出：
对于所有 i,j,k（包括题中各个非终止符），算出式 (2)中的各值。只要其中之一值为 1，便在相应当位置上打 √,否则打? 。如此便可填满整个识别表 [若左侧为 K的代换式有三个，可按上述原则，再增加计算将 (1)式中 K1,K2改为 K1’’、
K2’’后的各值，余类推 。
),1,1(),,1(
),2,2(),,2(
),1,1(),,1(
'
2
'
1
'
2
'
1
'
2
'
1
KijrKjir
KjirKjr
KjirKjr
现作为例子用递推规则考察 (2,2,A)中的 √ 或? 。由于左侧为 A的代换式只有 A→ BS一个，故此时对于 (1)式只需计算 r(1,2,B)? r(1,3,S)=1?1=1,即 (2,2,A)应打 √ 。
此结果与前面分析得到的相符。
根据上述递推规则和给定的文法，容易编制计算机程序。当待识别串 X进入时，按此算出识别表，并检查表中最后一列 S位置上是 √ 还是?；若为 √,便判属于给定文法相应的类别，否则判为不属于此类别。
作业：对 Younger法的例题编程上机，打出识别表。
四,CYK(Cocke-Younger-Kasami)剖析 (列表法 )
条件,① 适用上下文无关文法
② 产生式应符合 Chomsky范式已知输入串 X=a1a2...an
构造三角形剖析表步骤如下：
① 令 j=1,按从 i=1到 i=n次序,求 ti1.把 X
分解为长度为 1的子串,
对子串 ai,若 p中有 A→a i,把 A填入 ti1中
② 令 j=2,按从 i=1到 i=n-1次序,求 ti2，
即第二行 。 把 X分解为长度为 2的子串,
对子串 aiai+1,若 p中有 A→BC,且有 B→a i,C→a i+1
则把 A填入 ti2中
③ 对于 j>2,1≤i≤n,已求出 tij-1,现求 tij
对于 1≤k≤j 中的任一 k,当 P中有 A→BC 且 B在 tik中,C在 ti+k,j-k中时,把 A
填入 tij中
④ 重复 ③ 直至完成此表,或整行都是空 (拒识 )当且仅当 S在 tin中,
X?L(G),即由 G可导出 X
分析一个长度为 n的串,所用的存储量正比于 n2,运算次数正比于 n3。
1 2 3 4 5 i
5
4
3
2
1
tij
剖析表
j
例,G = (VN,VT,P,S) VT =（ a,b） VN =（ S,A,B,C）
P:① S→AB ② S→AC ③ A→a ④ B→b ⑤ C→SB
输入串,X=aabb=a1a2a3a4 所有产生式符合 Chomsky范式
① 令 j=1,计算 ti1,1≤i≤ 4
i=1,a1=a,∵P 中有 A→a ∴ 有 t11=(A)
i=2,a2=a,∵P 中有 A→a ∴ 有 t21=(A)
i=3,a3=b,∵P 中有 B→b ∴ 有 t31=(B)
i=4,a4=b,∵P 中有 B→b ∴ 有 t41=(B)
② 第一次迭代,令 j=2,计算 ti2,1≤i≤ 3
对于 a1a2=aa,∵ 不能产生 aa ∴ 有 t21=φ
对于 a2a3=ab,∵S→AB,A→a,B→b ∴ 有 t22=(s)
对于 a3a4=bb,∵P 中产生式不能产生 bb ∴ 有 t32=(φ )
1 2 3 4 i
j
4
3
2
1 A A B B
φ S φ
③ 第二次迭代,令 j=3,计算 ti3,1≤i≤ 2
对于 a1a2a3=aab,∵ 不能产生 aab ∴ 有 t13=φ
对于 a2a3a4=abb,∵C→SB,S→ab,B→b ∴ 有 t23=(C)
④ 第三次迭代,令 j=4,计算 ti4，
对于 a1a2a3a4=aabb,∵S→AC,A→a,C→abb ∴ 有 t14=(S)
∵ t14=S ∴X=aabb 在 L(G)中,∴ 此串被识别 。
此算法实际上是一个由底向顶剖析算法 。
4
3
2
1
A A B B
φ S φ
1 2 3 4 i
φ
S
C
剖析表
a a b b↓ ↓
↓↓A A B B
S
S
C
导出树
+
+
作业：对 CYK算法的例题上机编程，打出剖析表和导出树。
§ 7-4 自动机理论引言,x
当给出某类文法后，可根据它设计一种相应的称为自动机的硬件模型。它由控制装置、输入带和某些类型的存储器组成，这种硬件模型是一种识别器称自动机。不同的自动机可以识别不同的文法形成的语言。
0型文法：图灵机识别上下文有关型：线性约束自动机上下文无关型：下推自动机有限状态型：有限状态自动机识别器 X? L{G}
G
一,有限状态自动机 可以识别由有限状态文法所构成的语言
1、基本定义：五元式 M系统 M=(∑,Q,δ,q0,F )
其中,∑,输入符号的有限集合
Q：状态的有限集合
δ,状态转换函数是 QΧ ∑ 到 Q的一种映射
q0：初始状态 q0? Q
F：终止状态集合
2、有限自动机的结构转换函数,δ (q,a)=p
表示有限控制器处于 q状态，而输入头读入符号 a，则有限控制器转换到下一状态 p。
QF?
∑ 输入带
0 1 1 0
输入头有限状态控制器 Q q0→ q 1→,..F
3、自动机识别输入字符串的方式
L(M) = {x| δ (q0,x)在 F中 }
δ (q,x)＝ Φ 拒识，停机
4、自动机的状态转换图,表示自动机识别过程例,M=(∑,Q,δ,q0,F )
Q ＝ {q0,q1,q2,q3}
∑ ＝ {0,1}
F ={q0}
δ (q0,0)= q2,δ (q0,1)= q1,
δ (q1,0)= q3,,δ (q1,1)= q0,
δ (q2,0)= q0,δ (q2,1)= q3,
δ (q3,0)= q1,δ (q3,1)= q2
q0 q1
q2 q3
1
1
1
1
0 0 0 0
输入,x=110101
q0 q1 q0 q2 q3 q1 q0?F
∴ X可以识别
∴ δ (q0,110101)= q0
例：已知自动机状态转换图如下
x1=aab 可以识别
x2=abb 不可以识别可以识别的语言,L(G)=anb
qB状态，只有出没有进，为不可到达状态
qΦ状态，只有进没有出，为陷阱
1 1 0 1 10
a
b
baa b
q0 qA
qB q
Φ a,b
4、不确定的有限状态自动机即,δ (q,a)= {q1,q2,… qk}当输入 a时，下一个状态可能为多个状态之一。
例,M=(∑,Q,δ,q0,F )
Q ＝ {q0,q1,q2,q3,q4}
∑ ＝ {0,1}
F ={q2,q4}
δ (q0,0)= {q0,q3},δ (q0,1)= {q0,q1}
δ (q1,0)= Φ(在 q1不会输入 0)
δ (q1,1)= q2
δ (q2,0)= q2,δ (q2,1)= q2,
δ (q3,0)= q4,δ (q3,1)= Φ
δ (q4,0)= q4,δ (q4,1)= q4
状态转换图输入字串,010110
q0 q0 q0 q0 q0
q3 q1 q3 q1 q2 q2?F
q0 q3
q1
0 0
0,1
0,1
1
1
0,1
q4
q2
0 1 0 1
1 0
∴ 输入字符串 X=010110
可以被自动机识别，但在识别过程中，对不确定状态需要进行试探。
5、构造一个有限自动机定理 1：设 G = (VN,VT,P,S)为有限状态文法，一定存在一个有限状态自动机 M=(∑,Q,δ,S,F)使 L(G) = L(M).
已知有限状态文法 G = (VN,VT,P,S)
由有限状态文法构造有限自动机的步骤：
① ∑ ＝ VT
② Q ＝ VN∪{T}
③ q0 = S
④ 若 P中有 S→Φ,则 F = (S,T),否则 F = {T}
⑤ 若 P中有 B→a,则 δ (B,a) = {T},B? VN,a? VT
⑥ 若 P中有 B→aC,则 δ (B,a) = (C),B,C? VN,a? VT
⑦ 对 VT中所有的终止符 a,都有 δ (T,a) = Φ,a? VT
例：有限状态文法 G = (VN,VT,P,S) VN = {S,B} VT = {0,1}
P,S→0B,B→0B/ 1S/0 (B→0B,B→1S,B→0)
构造有限自动机 M=(∑,Q,δ,q0,F )
① ∵ ∑ ＝ VT ∴ ∑ ＝ {0,1}
② ∵ Q ＝ VN∪{T} ＝ {S,B,T}
③ q0 = S
④ ∵ P中无 S→Φ ∴ F = {T}
⑤ ∵ S →0B,∴ δ (S,0) = B,∵ B →0B,∴ δ (B,0) = B,
∵ B →1S,∴ δ (B,1) = S,∵ B →0,∴ δ (B,0) = T,
∵ P中无 S→1x,x? VN,∴ δ (S,1) = Φ
⑥ 对 VT = {0,1}有 δ (T,0) = δ (T,1)＝ Φ
∴ 构造的自动机 M为
M=(∑,Q,δ,q0,F ),∑ ＝ {0,1},Q= {S,B,T},
q0={S},F={T}
δ,δ (s,0)={B}
δ (s,1)=Ф
δ (B,0)={B,T}
δ (B,1)={S}
δ (T,0)=δ (T,1)=Ф
设 x=00100,可以识别可以证明,L(M)=L(G)
0
1
0
T
S B
0
6.由有限自动机 M构造有限状态文法定理 2：已知有限自动机 M，则有一个有限状态文法 G，使
L(G) = L(M)。
已知 M=(∑,Q,δ,q0,F )，构造 G = (VN,VT,P,S) 的步骤如下：
① VT＝ ∑ ② VN ＝ Q ③ S＝ q0
④ 对于 δ (B,a) = C,若 B,C?Q,a?∑,则 P中有 B→aC.
若 C?F,则还有产生式 B→a
例：已知有限自动机
M=(∑,Q,δ,q0,F ),Q ＝ {q0,q1,q2}
∑ ＝ {0,1} F ={q2}
δ (q0,0)= q2,δ (q0,1)= q1,δ (q1,0)= q2,,δ (q1,1)= q0
δ (q2,0)= q2,δ (q2,1)= q1
构造 G = (VN,VT,P,S) 如下,
① VT ＝ ∑ ＝ {0,1}
② VN= Q = {q0,q1,q2}
③ S = q0
④ ∵ δ (q0,0)= q2,,∴ 有 q0→0 q2,∵ q2? F ∴ 有 q0→0
∵ δ (q0,1)= q1,,∴ 有 q0→1 q1,
∵ δ (q1,0)= q2,,∴ 有 q1→0 q2,∵ q2? F ∴ 有 q1→0
∵ δ (q1,1)= q0,,∴ 有 q1→1q0,
∵ δ (q2,0)= q2,,∴ 有 q2→0q2,∵ q2? F ∴ 有 q2→0
∵ δ (q2,1)= q1,,∴ 有 q2→1q1,
∴ 有限状态文法为：
G = (VN,VT,P,S)
VT ＝ {0,1}
VN = {q0,q1,q2}
S = q0
P,q0→0 q2,q0→1q1,q0→0
q1→0 q2,q1→1q0,q1→0
q2→0 q2,q2→1 q1,q2→0
状态图输入 x＝ 1100
由自动机 M,δ (q0,1100)＝ q2,∵ q2? F ∴1100 可以接受由有限文法 G,q0→1q1→11q0→110q2→1100
∴ L(M) = L(G)
q0 q1
q2
1
1
1
1
1
1
0
0
0 0 0 0
0
0
0
q1q0
q2 T有限自动机有限状态文法二,下推自动机（ PDA）可以识别由上下文无关文法构成的语言
下推自动机结构：
七元式 MP = (∑,Q,δ,q0,Z0,F,Г )
其中 ∑,Q,,q0,F同有限自动机
δ,转换函数 Г,推下符号的有限集合 Z0,推下存贮器的起始符例如,δ (qi,b,Z) = (qj,β )
qi：目前状态,b：输入符号,Z：下推存储器的内容
qj,下一状态,β,下推存储器的下一状输入带 ∑
只读头有限状态器 Q
读写头下推存储器（堆栈型）
b
B
Z0
识别输入字串 X的方式
①终止状态方式
②空堆栈识别方式例：不确定的下推自动机
MP = ((q0),(a,b,c,d),(S,A,B,C,D),δ,q0,S,Φ )
即,Q= (q0),∑= (a,b,c,d),
Г = (S,A,B,C,D),Z0=(S),F=(Φ)
δ (q0,c,S) = {(q0,DAB),(q0,C)}
δ (q0,a,D) = {(q0,λ )},δ (q0,b,B) = (q0,λ )
δ (q0,d,C) = (q0,λ ),δ (q0,a,A) ={ (q0,AB ),(q0,CB )}
}),,(),,(,|{)( 00* FqrqzxqXXML ffP
)},(),,(,|{)( 00* qzxqXXML P
输入 x＝ caadbb
(q0,S ) → (q0,DAB) → (q0,AB) → (q0,CBB) → (q0,BB) → (q0,B)
→ (q0,C) → → (q0,ABB) →
→ (q0,λ )
堆栈变空,X=caadbb可以接受，这种不确定的下推自动机在识别过程中需试探进行。
c a a d b
da 不通 不通
b
例：确定自动机 MP = (∑,Q,δ,q0,Z0,F,Г )
∑ = (0,1) Q ＝ {q0,q1,q2}
Г ＝ (2,0) F =(q0) Z0 = (Z)
δ (q0,0,Z) = (q1,02),δ (q1,0,0) = (q1,00)
δ (q1,1,0) = {(q2,λ )},δ (q2,1,0) = (q2,λ )
δ (q2,λ,2) = (q0,λ )
X=0011
δ (q0,Z) → δ (q1,02) → δ (q1,002) → δ (q2,02) →
δ (q2,2) → δ (q0,λ )
堆栈变空,X＝ 0011可以被接受
0 0 1 1
λ
由上、下文无关文法 G = (VN,VT,P,S)构造一个下推自动机
MP = (∑,Q,δ,q0,Z0,F,Г )步骤如下：
① ∑ ＝ VT
② Г ＝ VN∪{ VT}
③ Z0 = S
④ Q = q0
⑤ F = φ (用堆栈变空来识别 )
⑥ 由 p构造 δ 函数
Ⅰ,若 A→ 在 P中,则有 δ (q0,λ,A) = (q0,)
Ⅱ,对 VT中所有终止符 a,有 δ (q0,a,a) = (q0,λ )
例,G={(s,A),(a,b,c,d),p,S}
P,S→cA,A→aAb,A→d
构造 MP = (∑,Q,δ,q0,Z0,F,Г )
① Q = q0
② ∑ ＝ VT＝ {a,b,c,d}
③ Z0 = S
④ Г ＝ VN∪{ VT}=(S,A,a,b,c,d)
⑤ F = Φ (由堆栈变空来识别 )
在 P中有 S→ cA,则 δ (q0,λ,S) = (q0,cA )
A→ aAb,则 δ (q0,λ,A) = (q0,aAb )
A→ d,则 δ (q0,λ,A) = (q0,d)
由上式可合并,δ (q0,λ,A) = {(q0,aAb),(q0,d) }
由规则 Ⅱ 对 VT：
δ (q0,a,a) = (q0,λ ),δ (q0,b,b) = (q0,λ )
δ (q0,c,c) = (q0,λ ),δ (q0,d,d) = (q0,λ )
对 x=caadbb
(q0,S ) → 无，可以先输入空格 λ 。
∴
(q0,S) (q0,CA) (q0,A) (q0,aAb) (q0,Ab) (q0,aAbb)
(q0,Abb) (q0,dbb) (q0,bb) (q0,b ) (q0,λ )堆栈空若文法符合 Creibadh范式，产生式形式为：
A →a α,A? VN,a? VT，
上面规则 Ⅰ,Ⅱ 合成一个规则，若 A →,
则有 δ (q0,a,A) = (q0,α )
C
λ
→
a
)(* 包括V N?
λ
→→→
λ
→
→
λ
→ → → →
c a
a d b b
例,Greibach范式文法
G = ({S,A,B},{a,b,c,d},P,S)
P,S→cA,A→aAB,A→d,B→b
可以构造一个下推自动机 MP = (∑,Г,Q,δ,Z0,q0,F)
其中 ∑ ＝ VT＝ {a,b,c,d},Г ＝ VN = (S,A,B),Q = q0
Z0 = S,F = Φ
因 P中有 S→ cA,则 δ (q0,c,S) = (q0,A )
A→ aAB,则 δ (q0,a,A) = (q0,AB )
A→ d,则 δ (q0,d,A) = (q0,λ )
B→ b,则 δ (q0,b,B) = (q0,λ )
形式，根据上面的规则这些产生式都符合?aA?
输入 X=caadbb
(q0,S) → (q0,A) (q0,AB) (q0,ABB) (q0,BB)
→ (q0,B) → (q0,λ )
只用六步就完成，而上例用九步。说明符合 Greibach范式的文法产生的语言容易被下推自动机识别。
c a a d
b b
→ → →
三、图灵机：可以识别 0型文法所产生的语言
1、结构
2、定义：一个图灵机 T是一个六元式 T = (∑,Q,Г,δ,q0,F )
其中：
Q：状态集合
Г ＝ ∑ ＋ B,B空
∑ = Г - B,q0起始状态,q0? Q
F:终止状态控制装置读写头输入带图灵机是最复杂的自动机。它的一个构型用三元式（ q,α,i）
表示 q? Q,α? (Г - B)*
映射 δ 的使用
δ (q,Ai)=(P,X,R)在 Ai处插入 X后右移
δ (q,Ai)=(P,X,L)在 Ai处插入 X后左移
3、图灵机 T所接受的语言
},),,(*|)1,,(|{)( *0* FqiqTXqXXTL
例,T = (∑,Q,Г,δ,q0,F )
∑ ＝ (0,1),Q=(q0,q1,… q5),
Г =(0,1,B,X,Y),F=(q5)
① δ (q0,0)= (q1,x,R ) ② δ (q1,0) = (q1,0,R)
③ δ (q2,Y) = (q2,Y,L) ④ δ (q3,Y) = (q3,Y,R)
⑤ δ (q4,0) = (q4,0,L ) ⑥ δ (q1,Y) = (q1,Y,R )
⑦ δ (q2,x) = (q3,x,R ) ⑧ δ (q3,B) = (q5,Y,R )
⑨ δ (q4,x) = (q0,x,R ) ⑩ δ (q1,1) =(q2,Y,L )
⑴ δ (q2,0) = (q4,0,L )
输入,x=0011,则图灵机运行如下：
(q0,0011,1 ) → (q1,x011,2 ) → (q1,x011,3 ) →
(q2,x0Y1,2) → (q4,x0Y1,1 ) → (q0,x0Y1,2 ) →
(q1,xxY1,3 ) → (q1,xxY1,4 ) → (q2,xxYY,3) →
(q2,xxYY,2 ) → (q3,xxYY,3 ) → (q3,xxYY,4 ) →
(q3,xxYY,5 ) → (q5,xxYYY,6) q5? F
∴ X ＝ 0011被接受
↓ ↓ ↓
↓
① ② ⑩
⑴ ⑨
⑥ ⑩ ③
④⑦
⑧
↓ ↓
↓ ↓ ↓
↓ ↓ ↓
↓
①
④
§ 7-5 误差校正句法分析一,解决噪声干扰的方法
① 推断文法时,考虑噪声干扰的样本
② 在预处理中,除掉噪声,平滑处理
③ 用随机文法,采用概率的概念,给句子的出现加上概率的分布
④ 用转换文法,把有噪声句子转换为无噪声句子
⑤ 用误差校正剖析句法集群法二,随机文法
定义：四元式 GS = (VN,VT,PS,S)
PS形式,α i→ β ij j=1,2...n i=1,2...k
其中 α i,β ij?( VN∪ VT)*
Pij,α i产生 β ij的可能性为 Pij,称为产生概率 。
产生概率 Pij满足,0≤P ij≤ 1以及出现概率 P(X)满足,等于产生概率的乘积 。
用 GS产生的语言称为随机语言 。
L(Gs)={(x,P(x))|X?V T*,S→X,j= 1,2...k,且 }
1
1
n
j
ijp
pxP iki 1)(
pxP jkj 1)(
pij
pj
假如某随机文法为：
Gs = (VN,VT,P,S)
VN={A1,A2,.… Ak} VT={a1,a2,.… am},S=A1
PS形式：
其中
1
1
0
1 1
m
l
l
i
k
j
m
l
l
ij pp
Aa
p
A
Aa
p
A
Aa
p
A
Aa
p
A
kmi
ili
i
i
m
ik
l
ij
i
i
.....
,
22
11
2
1
1
1
a
p
A
a
p
A
a
p
A
mi
li
i
m
i
l
i
i
0
0
1
0
..,.,
1
例：有随机文法 Gs = (VN,VT,P,S)
VN={S,A,B} VT={0,1}
PS形式,S→ 1A B→ 0 B→ 1S
A→ 0B A→ 1
导出式
S→ 1A→ 10B→ 100,P(X)=P(100)=1ⅹ 0.8ⅹ 0.3=0.24
S→ 1A→ 11,P(X)=P(11)=1ⅹ 0.2=0.2
由 Gs产生的语言 L(Gs)
产生的链 X P(X)出现的概率
11 0.2
100 0.24
(101)n11 0.2ⅹ( 0.7ⅹ 0.8)n
(101)n100 0.24ⅹ( 0.7ⅹ 0.8)n
1 0.3
0.8 0.2
B
S
A
1
1
1
P=0.7
P=0.8
P=0.2
P=0.3
0
00.7
T
用随机文法作识别
① 用大量的样本去推断随机文法,每个随机文法代表一类
② 检查待识别的样本符合哪一个随机文法,就把它归于该随机文法所代表的一类
③ 若待识别的样本符合二个以上的随机文法再求待识别样本对每一类的出现概率，把待识别样本归于出现概率最大的一类。
例：关于,7‖,,1‖的手写体数字产生,1‖的随机文法 G1 = (VN,VT,P,S)
VN={S,A,B,C,D,E,F,H,I}
VT={0,1,3,4,5,6,7}
0
123
4
7 005555 05555 0055565
―1‖
基元
P形式：? S→0A? A→0B? B→5C? C→5D
D→ 5E? D→ 5? E→ 5? A→ 5F
F→ 5H? H→ 5I
⑴ I→5
P1=1 P2=0.2 P3=1 P4=1
P5=0.75 P6=0.25 P8=0.8
IA
B
C D
E
S
H
F
0
0
5
5
5
5
5 5
5 5
5
状态图
T
GT = (VN,VT,P,S)
VN={S,A1,B1,C1,D1,E1,F1,O1,G1} VT={1,2,3,4,5,6,7}
P形式：
S→ 0A1? A1→ 0B1? B1→ 0C1? C1→ 5D1
D1→ 5E1? E1→ 5F1? F→ 5? E1→ 5
B1→ 5O1? O1→ 5G1 ⑴ G1→ 5
0005555 000555 00555
关于手写
,7‖的随机文法
P3=0.8
P6=0.375 P8=0.625
P9=0.2
0
123
4
765
基元状态图设待识别链 X=00555
① 用,7‖随机文法产生,00555‖
S→ 0A1→ 00B1→ 005O1→ 0055G1→ 00555
P7(00555)= P1P2P9P10P11=0.2 出现的概率为 0.2
② 用,1‖随机文法产生,00555‖
S→ 0A→ 00B→ 005C→ 0055D→ 00555
P7(00555)= P1P2P3P4P6=0.05 出现的概率为 0.05
∵P 7(00555)> P1(00555) ∴X= 00555? 7
A1
B1
C1 D1
E1
F
S
P1
O1
0
0
5
5
5
5
0 5
5 5
5
① ② ⑨ ⑩ ⑴
① ② ③ ④ ⑥
T
怎样求代表各类的随机文法
① 先求出代表各类的一般文法 (用一般文法的文法推断 )
② 用统计法由训练样本求出现概率
③ 再由出现概率求产生概率例：关于,7‖,,1‖,找大量人写,7‖,,1‖并进行统计如下关于手写,7‖,X1=0005555 P(X1)=30%
X2=000555 P(X2)=50%
X3=00555 P(X3)=20%
关于手写,1‖:
先用以上训练样本推断出一般文法,(用链文法的推断方法 )
然后在各产生式上加产生概率就可以了 。 现在就变成求产生概率的问题 。
0 0 5 5 5
0 5 5 5 5
0 0 5 5 5 5
'
3
'
2
'
1
X
X
X
%5)(
%80)(
%15)(
'
3
'
2
'
1
XP
XP
XP
再用每一个训练样本的出现概率求产生概率
P1P2P3P4P5P6P7=0.3 ——X1=0005555
P1P2P3P4P5P8=0.5 ——X2=000555
P1P2P3P10P11=0.2 ——X3=00555
∵P 1=P2=P4=P5=P7=P10=P11=1
∴P 3P6=0.3
P3P8=0.5
P9=0.2
∵P 3+P9=1
∴P 3=0.8
P6=0.375,P8=0.625
用同样的方法可求出其它产生概率三,句法集群法输入句法模式取样 X=(x1,x2,..,xs)
其中 xi为终止符集合 xi=a1a2...
输出：要求把 xi分配到相应的 m个子集中 (即 m类 ),并给出每个集群的文法 G(k),k=1,2,… m
输入第一个取样 x1,由 x1推出文法 G1(1)
∴x 1?L(G 1(1))
输入 x2,计算 d(x2,L(G1(1)))长度,判定 x1和 x2的相似度 。
① 若 d(x2,L(G1(1)))<t,则 x1,x2? 集群 1,由 x1,x2推出文法 G2(2)
② 若 d(x2,L(G1(1)))≥t,则 x1,x2 集群 1,对 x2推出新文法 G1(2)
t为门限
③ 对新的取样重复第二步,最后获得 m个集群,对应文法为
Gn1(1),Gn2(2)..,Gnm(m)
关于门限 t的选择：
假定已知 m类句法模式取样 X(1),X(2)..,X(m)
m类取样对应的文法分别为 G(1),G(2)..,G(m)
文法对应的语言为 L(G1),L(G2)..,L(GM)
门限 t由下式决定：
其中 X(K)是类别 k中的一个取样
L(GL)是类别 L的语言上式说明门限 t应小于 X(K)同文法 G1,G2,… Gm的语言的最小距离,只有这样才能把 m类分开 。
) ) }(,({m in )(
,G
Lxdt lk
lk
lk
K=1,2….m
L=1,2…..m
四,最小距离法
对句法模式的度量
① 两个模式间的距离
d(x,y)=min(x→y) 由模式 x导出 y的最小变换次数
② 句子和语言间的距离
d(x,L(G))=min{d(x,y)}
③ 求输入句子 X和语言 L(G)的距离,即是在语言 L(G)中寻求和句子 X具有最小距离的句子 Y。 为了获得这一距离,
必须搜索 L(G)中所有句子,从中找到和 X最近的句子 Y。
可写成如下形式：
的一个句子为 )()(),( GLGLyGLx
)}(|),({m i n)}(,{,..2,1 GLYYXdGLXd iiimi
最小距离句法识别
① 二类问题,G1,G2代表二类
d(x,L(G1))< d(x,L(G2)),则 x?L(G 1) ∴x?G 1
d(x,L(G1))> d(x,L(G2)),则 x?L(G 2) ∴x?G 2
② 多类情况,G1,G2...Gm
相应的语言为,L(G1),L(G2)…,L(GM)
对未知模式 X进行归类的最小距离规则为
d(x,L(G(i)))=min[d(x,L(G(k)))] k=1,2,...m
则 x?L(G (i)) ∴x?G (i)
§ 7-1 形式语言概述一、基本概念
1、字母表,与所研究的问题有关的符号集合。
例,V1={A,B,C,D},V2={a,b,c,d}
2、句子 (链 )：由字母表中的符号所组成的有限长度的符号串。
3、句子 (链 )的长度,所包含的符号数目。例,|a3b3c3|=9
4、语言,由字母表中的符号组成的句子集合，用 L表示。
例：字母表 V={a,b}
L1={ab,aab,abab} 有限语言
L2={anbm|n,m=0,1,2….} 无限语言
5、文法,在一种语言中，构成句子所必须遵循的规则的集合，
用 G表示。 L(G)表示由文法 G构成的语言。
6,V*:由字母表 V中的符号组成的所有句子的集合，包括空句子
λ在内。例,V*＝ {λ,01,001}
7,V＋,不包括空句子在内的句子集合，即 V＋ ＝ V*－ (λ)
8,VT,终止符，不能再分割的最简基元的集合，用小写字母表示。 VT={a,b,c}
9,VN,非终止符，由基元组成的子模式和句子的集合。用大写字母表示。 VN={A,B,C}
VT,VN的关系,VT∩ VN= Φ(空集 )
VT∪ VN= V（全部字母表）
10、产生式 (再写规则 )P：存在于终止符和非终止符间的关系式。
例,α→β,α? VN,β? VN,VT.
11、文法的数学定义,它是一个四元式，由四个参数构成。
G={VN,VT,P,S}
二,短语结构文法
1,0型文法 （ 无限制 ）
设文法 G = (VN,VT,P,S)
VN,非终止符,用大写字母表示
VT,终止符,用小写字符表示
P：产生式
S：起始符产生式 P,α→β,其中 α? V+,β? V* α,β无任何限制
( V+不包括空格,V*包括空格 )
例,0型文法 G = (VN,VT,P,S)
VN = {S,A,B}
VP = {a,b,c}
P,① S→aAbc ② Ab→bA ③ Ac→Bbcc
④ bB→Bb ⑤ aB→aaA ⑥ aB→λ(空格 )
S→Aa bc→abAc→abBbcc→aBbbcc→ bbcc
此文法可以产生,X=anbn+2cn+2 n≥0
X|n=0=bbcc
由 0型文法产生的语言称为 0型语言 。
2,1型文法 （ 上下文有关文法 ）
设文法 G = (VN,VT,P,S)
产生式 P,α1Aα2→α1βα2
其中 A? VN,β? V+,α1,α2? V*
|α1Aα2|≤|α1βα2|,或 |A|≤|B|
由上下文有关文法构成的语言称为上下文有关语言，
用 L(G1)表示,G1：上下文有关文法
① ② ③ ④ ⑥
例,G = (VN,VT,P,S)
VN = {S,B,C} VT = {a,b,c}
P,① S→aSBC ② CB→BC ③ S→abC ④ bB→bb
⑤ bC→bc ⑥ cC→cc
λ1Sλ2→λ1aSBCλ2,bBλ→bbλ
对于 S→aSBC
∵ α 1= λ,α 2= λ,A = S,B=aSBC,并且 |S|<|aSBC|
∴ 符合 1型文法规则对于 bB→bb
∵ α 1= b,α 2= λ,A = B,B=b,并且 |B| ≤ |b|
∴ 也符合 1型文法规则产生式都符合 1型文法的要求
S→aSBC→aabCBC→abbBCC→aabbCC→aabbcC→aabbcc
∴ X=a2b2c2
此文法 G可产生的语言,L(G)={anbncn|n=1,2...}
假设基元语言 L(G)可以描述不同的三角型
X= abc X= a2b2c2
a
b c
① ②③ ④ ⑥⑤
a
bc
c
c
b
b
a a
2,2型文法（上下文无关文法）
设文法 G = (VN,VT,P,S)
产生式 P,A→β 其中 A? VN（ 且是单个的非终止符 )
β? V+ (可以是终止符,非终止符,不能是空格 )
对产生式的限制比较严格由上下文无关文法构成的语言称为上下文无关语言 。
例：文法 G = (VN,VT,P,S)
VN = {S,B,C}
VT = {a,b}
P,① S→aB ② S→bA ③ A→a ④ A→aS
⑤ A→bAA ⑥ B→b ⑦ B→bS ⑧ B→aBB
aB→abS→abaB→abab
S abbA→abba
bA→baS→baaB→baab
babA→baba
例,G = (VN,VT,P,S)
VN = {S,T,F}
VT = {a,+,*,(,)}
P,① S→S+T ② S→T ③ T→T*F ④ T→F
⑤ F→(S) ⑥ F→a
S→S+T→T+T→F+T→a+T→a+T*F→a+F*F→a+a*F→a+a*a
① ⑦
③
④
③
⑥
⑥
①
①
②
②
②
① ② ④ ⑥ ⑥⑥③ ④
两种方法替换非终止符：
① 最左推导：每次替换都是先从最左边的非终止符开始，
例如上边的例子。我们经常采用最左推导。
② 最右推导：每次替换都是先从最右边的非终止符开始，
例如,S→S+T →S+F →S+a → T+a → F+a → a+a
3,3型文法 （ 有限状态文法 ）
文法 G = (VN,VT,P,S)
产生式 P,A→aB 或 A→a,（ 对产生式限制最严格 ）
其中 A,B? VN（ 且是单个字符 ）,a? V T(且是单个字符 )
由 3型文法产生的语言成为 3型语言 。
例：文法 G = ({S,A},{0,1},P,S)
P,① S→0A ② A→0A ③ A→1
S→0A→00A→000A→0001
L(G)={0n1|n=1,2...}
例：构造文法 G能产生语言 L(G) = {x|x=0n 10m | n,m>0}
解,G = (VN,VT,P,S)
VT=(0,1)
P,① S→0B ② B→0B ③ B→1S ④ B→0
∴ VN=(S,B)
四种文法的关系,
包含关系：限制不严格的文法必然包含限制严格的文法。
3型 2型
1型
0型三,图象描述语言（ PDL）
1970年,Show提出图像描述语言任何图象都可用头尾来表示定义了四种二元连接算子
1,a + b
2,a x b
3,a – b
4,a * b
t
h
a头与 b尾相连
h
ht a尾与 b尾相连,形成两个头
ht
t
a头与 b头相连，形成一头二尾
a头连 b头,a尾连 b尾，形成一头一尾
h
htt
h
t
基元 b
a b
a
b
a
b
头 头尾 尾一元算子 ~
一个基元的头或尾可以与另一基元的头或尾相连而成为模式串，并可设置一些较复杂的联结关系和进行各种运算。
例：文法 G = (VN,VT,P,S)
VT = { →,↗,↘,↓,(),+,-,x,*,~ } VN= {S,A,B,C}
P,① S→A ② S→B
③ A→(b+(C+c)) ④ B→(d+(a+(~d))*C),
⑤ C→((b+c)*a)
h
t
b
h
t
~b
a b c d
L(G) = {(b+(((b+c)*a)+c)) ; ((d+(a+(~d)))*((b+c)*a))}
b c
a
a
d ~d
b
b
c
ca
CB
S
d
b~
+
导出过程
d
a +
+ c * a
S
A
b +
c+C
b + c * a
求ＰＤＬ表达式的规则：
① 脱括号由内往外的次序进行,无括号由左向右进行
② 对于连接基元组成基元结构,必须符合规定的连接点头,尾数目例：给出一个 PDL文法
G = ({S,A,B,C,D,E},{a↗,b ↘,→,d↓,(,),+,*,~},P,S)
P,① S →(A+(B)) ② B →(C)+D
③ D →b ④ E →(a+b)
⑤ A →d ⑥ C → E*c
⑦ D → (~d) ⑧ A →a
c
可以导出手写大写字符,A‖的四种表达式
S →(A+(B)) →(a+(B)) →(a+((C)+D) ) →(a+((E*c)+D))
→(a+(((a+b)*c)+D)) →(a+(((a+b)*c)+(~d)))
(d+(((a+b)*c)+b)),? (a+(((a+b)*c)+b)),? (d+(((a+b)*c)+(~d)))
① ⑧ ② ⑥
④ ⑦
a
d
b
b
a
a
b
b
ba
~dd c~d
a
a
b
c
四,标准形式文法在句法分析和自动机的一些算法中,有时要求标准化文法,下面介绍二种标准文法 。
1,乔姆斯基 (Chomsky)范式,一种上下文无关文法如果它的每个产生式 P都符合二种形式：
A→BC (A,B,C? VN)或 A→a (A? VN,a? VT)
该文法称 Chomsky范式已知上下文无关文法 G = (VN,VT,P,S)用以下步骤产生
Chomsky范式的等价文法
G = (VN,VT,,S)
① 若Ｐ中已经是 A→BC,A→a形式放入 中
② Ｐ中其它的产生式形式为 A→ θ1θ2…,θn
其中 θi? VN 或 θi? VT
P
P
用下面的产生式集合代替：
A→Y1Y2...n
Y2...n→Y2Y3...n
…
Yn-1...n→Yn,,n-1 Yi? VN
若 θi? VN,则令 Yi=θi；若 θi? VT,再引入 Yi→θi
例：把文法 G = (VN,VT,P,S)变成 Chomsky范式
VN = {S,A,B}
VP = {a,b}
P,S→AB,A→a,A→abABa,B→b
① 把 S→AB,A→a,B→b放入 中
② A→abABa,A→θ1θ2θ3θ4θ5，
其中 θ1=θ5=a,θ2=b,θ3=A,θ4=B
A→Y1Y2345,Y2345→Y2Y345,Y345→Y3Y45,Y45→Y4Y5,
∵ θ3,θ4? VN ∴ Y345→AY45,Y45→BY5,
∵ θ1θ2θ5? VT
∴ 引入新的产生式,Y1→a,Y2→b,Y5→a
P
符合 chomsky范式文法,文法 G2 = (VN,VT,,S)
VN = { Y1Y2345,Y2Y345,Y45,Y5,S,A,B}
A→Y1Y2345,Y1→a,Y2345→Y2Y345,Y2→b,Y345→AY45,
Y45→BY5,Y5→a,
S→BA,A→a,B→b
若 x=bababa
用 G1导出,S→BA→bA→babABa→bababa,
用 G2导出,S→BA→b Y1Y2345...→baY2345→
baY2Y345→babY345→babAY45 →babaY5
→bababY5→bababa
用原文法 G1 只用四步可以导出 bababa而用标准文法 G2则用九步才导出
P
2,格雷巴赫范式 (Greibach)
若一个上下文无关文法具有 P形式：
A→aα,A? VN,a? VT,α? VN*(带空格 ) 则此文法称为
Greibach范式。
例：上下文无关文法
G = (VN,VT,P,S)
VN = {S,C},VT = {a,b,c}
P形式,S→aCbb,C→aCbb C→c
变成 Greibach范式,C→cλ即 C→c符合 Greibach范式,不变
S→aCbb,用 S→aCBB,B→b代替
C→aCbb,用 C→aCBB,B→b代替符合 Greibach范式：
P,S→aCBB,C→aCBB,C→c,B→b,
五,高维文法,上面我们介绍的都是一维链 （ 串 ） 文法,为了描述更复杂的图形,图象,需要用高维文法,包括树文法,图文法,
网文法等等 。
1,树文法：
定义：四元组 Gt = (v,r,P,S)
其中 V=VN∪ VT,r,秩 (一个节点的直接分支数 )
P形式,Ti→Tj Ti,Tj都是树由 Gt产生的语言叫树语言 。
L(Gt)={T| T? T∑,Ti→T Ti? S },T∑ 是带有 VT中结点的树集合扩展树文法,全部产生式形式其中 x1,x2..,xn? VN,x? VT,n? r(x)
具有上面产生式形式的树文法称扩展的树文法 。
Gt
X x
x1,x2… xn
例,Gt = (v,r,P,S)
V=VN∪ VT ＝（ S,A,B,K,a,b）
VT ＝ ( →,↗ ),r(a)=(2,0),r(b)=(2,0),r(k)=2
P,① S→K ② A→a ③ B→b
④ A→a ⑤ B→b
∴ S→K
a b
A B A B A B
A B
a b
①
④ ⑤
a
bk
A B
①
④⑤
S→K
a b
A B A B
④ ⑤
② ③ a
b
k
导出树导出图
b baa
例 2：在氢云室内用正粒子打击核目标碰撞发出的射线可以用树文法来描述。
树文法 Gt = (v,r,P,S),VN＝（ S,A,B）,VT ＝ (a,b)
基本定义：
P:
a
b
(凸弧 ) (凹弧 )
S → a
|
S
S → a
A B
S → a
A BBA
S → a
A BBAA B
A → a
|
A
A → a B → a
|
B
B → a
r(a)=(0,1,2,4,6),r(b)=(0,1)
射线导出树：
S → a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
b
b
b
b
b
b
b
b
b
b
b
b
b
a
a
b
射线图：
§ 7-2 文法推断根据已知 L(G)样本集导出未知文法 G的过程 。
(一 )基本定义：
1.若在产生式中至少有一个产生式存在以下形式：
Ai→αiAiβi
此文法 G = (VN,VT,P,S) 是循环文法或不确定,由它产生的语言 L(Gt)为无限的 。
2.若文法 G为不循环的,则必为确定的,且 L(G)为有限的 。
样本集 推断算法 GtSt=(x1,x2… x t)
导师
3.当 L(GA)= L(GB)时,则 GA与 GB等效,等价 。
例：有限状态文法 GA = (VN,VT,P,S),VN = {S},VT = {0,1}
P:S→0S,S→1
则 L(GA)={0n1|n=1,2,… }
上下文无关文法 GB = (VN,VT,P,S),VN = {S,A},VT = {0,1}
P:S→A1,A→AA,A→0 则 L(GB)={0n1|n=1,2,… }
∴ L(GA)= L(GB) ∴ GA与 GB等效
4.S+是 L(G)的子集,即 S+? L(G),称为正取样,是 子集,
记为 称为负取样,
5.若正取样 S+=(x1,x2…,,xi)= L(G),称为 S+是完备的,负取样
= (x1,x2…,,xi) =,称 也是完备的,
且 St=(S+,S-)=(x1,x2…,,xi)=( L(G),)也是完备的 。
S? )(GL?
)(GLS
S? )(GL? S?
)(GL?
(二 ) 有限状态文法推断状态图表示方法,文法可以用图来表示例,G = (VN,VT,P,S)
VN = {S,A,B,C}
VT = {0,1}
P,① S→0A ② A→0A
③ B→0 ④ B→0B
⑤ S→1B ⑥ A→1B
⑦ C→0C ⑧ S→1C
⑨ A→1 ⑩ C→1
T：附加状态此文法可以产生的字符串
x1=00n1,x2=0n+110m+1,
x3=10n+1,x4=10n1
A
S
CB
T
0
0 0
0
11
11
1
0
一,规范确定文法已知正取样 S+=(x1,x2…,,xn)
推断规范文法 Gc = (VN,VT,PL,S)的步骤如下：
① VT = S+中不同的终止符
② 设 xi= ai1ai2..,ain链
∴ PL,S→ai1Zi1 Zi1? VN,ai1? VT
Zi1→ai2Zi2 Zi2? VN,ai2? VT
…
ZIn-2→ain-1Zi n-1 Zin-1? VN,ain-1? VT
ZIn-1→ain ain? VT
∴ VN={S,Zi1,Zi2,..,Zin-1,}
此文法产生的语言是确定的,有限的,且有性质,L(GL)=S+
例：已知 S+=(01,100,111,0010)
① VT ={0,1}
② ∵ x1=01,∴ S→0Z1,Z1→1
x2=100,S→1Z2,Z2→0Z3,Z3→0
x3=111,S→1Z4,Z4→1Z5,Z5→1
x4=0010,S→0Z6,Z6→0Z7,Z7→1Z8,Z8→0
∴ VN={S,Z1,Z2,..,Z8 }
推断出的文法为,Gc = (VN,VT,Pc,S)
VN={S,Z1,Z2,..,Z8,},VT ={0,1}
PL,S→0Z1,Z1→1,S→1Z2,Z2→0Z3,Z3→0,S→1Z4
Z4→1Z5,Z5→1,S→0Z6,Z6→0Z7,Z7→1Z8,Z8→0,
状态图：
显然对任一有限取样都可用此法推断出规范文法，方法简单，适用计算机运算。缺点是非终止符太多，产生式也多。
S
Z1
Z2
Z3
Z4
Z5
Z6
Z7
Z8T
0
0
0
0
0
0
1
1 1
1
1 1
二,导出文法 （ 简化规范文法 ）
设,Gc为规范文法,非终止符集合 VN={S,Z1,Z2,..,Zn },把
VN分成 r个子集,VND={Bj,B1,B2..,Br} S? Bj,Zi? Bj
这些子集满足：
Bj∩B k=Ф,j≠k
∪B j = VN
定义导出文法 GD = (VND,VT,PD,Bs)是由规范文法 Gc产生的文法,导出规则如下：
① VT相同
② VND = (Bs,B1,B2,… Br)
③ Bs为起始符,Bs=S
④ PD定义,a,若 Zα→αZβ 在 Pc中,则 PD中有
Bi→αBj,Za? Bi,Zβ? Bj
b,若 Zα→a在 Pc中,则 PD中有 Bi→a,Za? Bi
r
j=s
例,S+=(01,100,111,0010)
规范文法 Gc = (VNC,VT,Pc,S)
VNC = {S,Z1,Z2,… Z8}
对 VNC分割为：
VND = {(S),(Z1,Z6,Z7),(Z2,Z3,Z8),( Z4,Z5)}={ Bs,B1,B2,B3}
对于 S→0Z1∵ S? BS,Z1? B1 ∴ PD中有 BS→0B1
对于 Z1→1 ∵ Z1? B1 ∴ PD中有 B1→1
同理,BS→1B2,B2→0B2,B2→0,
BS→1B3,B3→1B3,B3→1
BS→0B1,B1→0B1,B1→1B2,B2→0
把相同的产生式合并后有：
Pc,BS→0B1,BS→1B2,BS→1Bs,B1→1,B1→0B1，
B1→1B2,B2→0B2,B2→0,B3→1B3,B3→1
状态图导出文法等效规范文法 L(GC)=L(GD)
这种方法由于分割方式不同会导出不同的文法而分割方式又无系统理论作指导,而靠经验和试探 。
B5
B3B2B1
T
0
0
11
1
1
1
1
0
0
三,形式微商文法形式微商定义：集合 A对于符号 a? VT的形式微商是：
DaA={X|ax? A }
若 a=λ(空串 ),则 DλA=A
例,A=S+={01,100,111,0010}
则 D0A= D0S+={1,010}
D1A= D1S+={00,11}
扩展：二次微商 Da1a2A=Da2(Da1A)
n次微商,Da1a2… an－ 1anA= Dan(Da1a2… an－ 1)A
对上例,D00 S+= D0 (D0 S+) = D0 (1.010)=(10)
D11 S+= (1) D000 S+ =Φ,D100 S+={λ}
已知正取样 S+={x1,x2,...xn}T
形式微商文法 GCD = (VN,VT,P,S),定义如下：
① VT =（ S＋ 中不同的符号 ）
② VN = U=(U1,U2,… UP) 其中 Ui( i=1,2… p)是 S+的形式微商,
且令 U1=DλS＋
③ 起始符,S=U1=DλS＋
④ 令 Ui,Uj? VN
P,当 DaUi= Uj,则 Ui→aUj
当 λ? DaUi,则 Ui→a
例,S+={101,111},推断形式微商文法如下：
① VT =（ 0,1）
② DλS＋ = S＋ ={101,111}= U1=S 起始符
③ ∵ D1S＋ ={01,11}= D1S= U2 ∴ S→1U2
∵ D10S＋ = D0(D1S＋ )= D0U2={1}= U3 ∴ U2→0U3
∵ D11S＋ = D1(D1S＋ )= D1U2={1}= U3 ∴ U2→1U3
∵ D101S＋ = D1(D10S＋ )= D1U3={λ} ∴ U3→1
∵ D111S-＋ = D1(D11S＋ )= D1U3={λ} ∴ U3→1
形式微商文法为 (相同产生式合并 )：
GCD = (VN,VT,P,S)
VT =（ 0,1） VN =（ S,U2,U3）
P,S→1U2,U2→1U3,U2→0U3,U3→1
状态图为：
S
U2 U3 T
1
10.1
四,k-尾文法,对形式微商文法进行长度限制,并对等价状态进行合并
k尾定义,ф(U,A,k)={X|X? DaA |X|≤k}
形式微商文法中两个状态间的等效性的充要条件为：
ф(XiS+k)= g(XjS+k)-k尾相等利用 k尾等效把形式微商文法中的等效状态合并,
导出 k尾文法 。
例,S+={01,1001}
① 先求形式微商文法
∵ DλS+= S+={01,1001}= U1=S
D0S+={1}= U2 ∴ S→0U2
D01S+= D1(D0S+)= D1U2={λ} ∴ U2→1
D1S+={001}= U3 ∴ S→1U3
D10S-= {01}= D0U3=U4 ∴ U3→0U4
D100S+= {1}=D0U4= U5 ∴ U4→0U5
D1001S+= {λ} ∴ U5→1
② 求 k尾等效状态,|X|≤k
k=4,k=3,k=2,k=1
U1=DλS+= {01,1001},{01},{0,1},{ф}
U2=D0S+= {1},{1},{1},{1}
U3=D1S+= {001},{001},{ф},{ф}
U4=D10S+= {01},{01},{01},{ф}
U5=D100S+= {1},{1},{1},{1}
等效状态为 k=4,k=3,k=2,k=1
(U2,U5) (U1,U4) (U1,U4) (U1,U3,U4)
(U2,U5 ) (U2,U5) (U2,U5,)
③ 合并状态,导出 k尾文法
k=4时 S→0U2,U1→1,S→1U3,U3→0U4,U4→0U2
k=3,2时 S→0U2,U2→1,S→1U3,U3→0S
k=1时 S→0U2,U2→1,S→1S,S→0S
状态图讨论：推断 k－尾文法时,k尾的选择很重要,k小时文法简单，但循环产生式增多，这样就可以导出更多的 S+
以外的子串来，有时这是不允许的。
1
S S
S
T
T
T1
1
1
U2
U3
U4
U2 U3
U2
0
0
00
0
0
0,1
1
K=2,3
K=1K=4
三,树文法推断一棵树可以看成一个多枝的链 。 因此前边讲的链 （ 串 ）
文法的推断方法可以用在树文法的推断上 。 任何一个数字化的网络模板都可以用树结构来表示如下：
由下面的四种方式表示成树枝全从根开始的树 。
X11 X12,..,.,X1n
X21 X22,..,.,X2n
...,..,..,..,..
Xn1 Xn2,..,.,Xnn
树状的数字化网络模式
S 根树干
N个枝
S
树干
M个枝…..…..
① 树文法先选一个合适的树干,由树干推出一个链文法
② 再推各树枝的文法
③ 把树干文法与树枝文法合并树干树干树枝树枝根 S
S
例：已知数字化模式
L1 L2 L3 L4 L5 L6
0 0 0 1 1 1
0 0 0 1 1 1
1 1 0 0 0 0
1 1 0 0 0 0
1 1 1 1 0 0
1 1 1 0 0 0
1 1 0 0 0 0
1 0 0 0 0 0
R1 R2 R3 R4 R5 R6
树干根 S
① 先由树干推出树干文法 GA
P,S → A1
A1 → $— A2
|
|
R1
L1
A2 → $— A3
|
|
R2
L2
A3 → $— A4
|
|
R3
L3
A4 → $— A5
|
|
R4
L4
A5 → $— A6
|
|
R5
L5
A6 → $
|
|
R6
L6
② 上面推出树干文法 GA,再推出树枝文法 GL1,
GL2..,GL6,GR1,GR2,..,GR6
③ 再将树干文法与树枝文法合并 GT= GA∪G L∪G R
§ 7-3 句法分析一,用句法分析作模式识别设给定训练样本为 M类即,ω 1,ω 2,… ω M
每类有 N个样本,如 ω 1的训练样本为,S=(X1,X2,… XN)T
由这些样本可以推断出 ω 1类的文法 G1,同样方法可推断出 ω 2类的文法 G2,…,ω M类的文法 GM,对待识别句子 X进行句法分析,若 X属于由文法 Gi构成的语言 L(Gi),则
x? ω i 类 。
框图如下：
X? L{G1}
G1
X? L{G2}
G2
X? L{GM}
GM
x 判决 X? ω i
……
句法分析过程识别结果待识别句子二句法分析的主要方法
1参考匹配法：
2状态图法：适用于有限状态文法例,G = (VN,VT,P,S)
VT =（ 0,1） VN =（ S,A,B,C）
P,S→ 1A,S→ 0B,S→ 1C,A→ 0A,A→ 0
B→ 0,C→ 0C,C→ 0,C→ 1B
X? 样本链码 X1
X? L{G2}x
……
样本链码 X2
X? 样本链码 XN
判决 X?ω
i
X? Xi
S
CBA
T
1 10
0
0
1
0
由状态图可以知道此文法可以识别的句子
X1=10n+1,X2=00,
X3=10n10,X4=10n+1
未知句子：由状态图可知
x1=10010(可以识别 )
x2=10110(不可以识别 )
0
0
状态图
2,填充树图法 (适用于上下文无关文法 )：
当给定某待识别链 X及相应的文法 G时,我们建立一个以 X
为底,S为顶的三角形,按文法 G的产生式来填充此三角形,
使之成为一个分折树 。 若填充成功表明否则填充树有二种方法
① 由顶向底剖析
② 由底向顶剖析填充树图法在填充三角形时应遵守三条原则：
① 首位考察：首先考虑选用某个产生式后能导出 X的第一个字符
② 用某产生式后,不能出现 X中不包含的终止符
③ 用某产生式后,不能导致符号串变长 (变短 )
)(GLX?
)(GLX? S
X
由顶向底 (由上而下 )剖析例,G = (VN,VT,P,S) VT =（ 0,1） VN =（ S,A,B）
P,① S→ 1 ② S→B 1 ③ S→B ④ B→ 1A
⑤ B→B 1A ⑥ A→ 0A ⑦ A→ 0
设,X=1000,用由上而下剖析方法判断 X是否属于 L(G)
B B
1
0 A
A
S
B
S
1 A
S
A0
0
⑦
∴ X=1000? L(G) ⑥
⑥
③
④
由底向顶 (由下而上 )剖析例,G = (VN,VT,P,S)
VT =（ a,b,c,f,g） VN =（ S,T,I）
P:① S→T ② I→a ③ S→Tfs ④ I→b
⑤ T→IgT ⑥ I→c ⑦ T→I
设,X=afbgc
① 用 I→a
② 用 T→I
③ 用 I→b
④ 用 I→c
⑤ 用 T→I
a f b g c
↓
I
a f b g c
↓
I
↓
T
a f b g c
↓
I
↓
T
↓
I
a f b g c
↓
I
↓
T
↓
I I
↓
a f b g c
↓
I
↓
T
↓
I I
↓
↓
T
① ② ③ ④
⑤ ⑥
a f b g c
↓
I
↓
T
↓
I I
↓
↓
T
T
a f b g c
↓
I
↓
T
↓
I I
↓
↓
T
T
↓
S
a f b g c
↓
I
↓
T
↓
I I
↓
↓
T
T
S
⑥ 用 T→IgT
⑦ 用 S→T
⑧ 用 S→TfS
S
⑦ ⑧
∴ X=afbgc? L(G)
三、杨格 (Younger)法
Younger法是个较前述各方法更系统的方法，适用于任何相应于 2型文法类别的识别。下面结合一例说明此方法。
设有一代表类别的文法 G = (VN,VT,P,S)其中
VT =（ 0,1,2） VN =（ S,B）
P,① S→SBS ② B→BB ③ B→BS
④ S→ 2 ⑤ B→ 0 ⑥ B→ 1
现在要用 Younger法来识别 X=202102是否? G.
首先将上述文法化为 Chomsky标准形式 。 此形式文法的代换式只有两种形式,即非终止符 → 非终止符?非终止符 （ 双非终止符形式 ）
非终止符 → 终止符 （ 终止符形式 ）
将式上所示文法中第 1条改为 S→SA,A→BS 两条（ A为人为增加的非终止符），使整个文法成为：
① S→SA ② A→BS ③ B→BB
④ B→BS ⑤ S→ 2 ⑥ B→ 0 ⑦ B→ 1
而令 VT =（ 0,1,2） VN =（ S,A,B）便完成了 Chomsky形式的转化。 Younger法将对 Chomsky形式文法进行分析。
待识别符号串的任一,子串,都可用 i,j两个整数来指明：
所谓子串即把一符号串任一截取一段，这段符号串（包括单个符号）就叫原来符号的子串。譬如符号串 202102的子串就有 2,0,2,1,0,2（个数为 1的子串）； 20,02,21，
10,02（个数为 2的子串）； 202,021,210,102（个数为 3
的子串）； 2021,0210,2102（个数为 4的子串）； 20210，
02102（个数为 5的子串）和 202102（个数为 6的子串即原符号串）。
这 21个符号串都可由正整数 i,j表示。 i代表子串中符号的个数（即子串长度），而 j表示这子串的首位在原符号串中占第几位。如上面所举的第 1子串,2‖，即为 i=1,j=1
的子串，第 13个子串 021即是 i=3,j=2的子串。可见，任一子串都可用 i,j二数来指明。
识别表的建立，关键问题是根据给出的待识别串 X,建立一识别表。对于 202102,根据所给出的文法算得的识别表如下：
i 1 2 3
j 1 2 3 4 5 6 1 2 3 4 5 1 2 3 4
所有子串 2 0 2 1 0 2 20 02 21 10 02 202 021 210 102
所有
VN
S √? √ √ √
A √ √ √
B? √? √ √ √? √ √? √? √
4 5 6
1 2 3 1 2 1
2021 0210 2102 20210 02102 202102
√ √
√?
√ √?
表中每一位置由三个符号表示。头二个即 i和 j，而第三个是非终止符 (现为 S,A,B,见表中第一列 ).。 i＝ 1栏中第 2列
(j=2)与 B行相交的位置即为 (1,2,B),余类推。表中 (1,2,B)位置上有 √,代表对于所给文法,B可导出 i=1,j=2的子串，
即,0‖。反之，若这位置上为?，则说明 B不能导生子串
,0‖。
再举一例，第 2栏中第 2列,A行位置应该用（ 2,2,A）表示，
此位置上有 √,代表对于所给文法,B可导出 I=2,j=2的子串，即,02‖（见表）。（ ）
经分析可知，能容易地根据给出的符号串 (202102),在 i=1栏的各位置上打 √ 或?,又根据此栏结果，由一递推公式将
i=2栏各位置打上 √ 或? 。如此递推下去便可将表填满，识别表也就建成。在识别时只需检查最后一栏 ( 现为 i=6栏 ) 第一列第 S行位置 [即 (6,1,S)]上是 √ 还是?。若是 √,表示 S可导生子串 202102，故判 202102符合给出的文法。反之，即判不符合此文法。
020 SBSA
建立识别表的递推规则递推规则：将要决定 √ 或? 的位置表为 (i,j,k)通用形式。
K代表非终止符。又将 r(i,j,K)称为 (i,j,k)位置的识别值。
此值为 0或 1，分别表示 (i,j,k)位置上是 √ 或? 。计算 r(i,j,K)
(也即决定 √ 或? )的步骤是：
(i)算出其中 K1,K2代表 K→ K1K2.例如,A→ BS,K=A,K1=B,K2=S.
),1,1(),,1(
),2,2(),,2(
),1,1(),,1(
21
21
21
KijrKjir
KjirKjr
KjirKjr
（ 1）
(ii) 如果 (i,j,k)左侧是 K的代换式不只一个，譬如 K是 B时，
即有 B→ BB,B→ BS两个。这时则把 B,B叫做 K1,K2，根据它计算式 (1)中各值；此外，还需将 B,S叫做 K1’,K2’，
再按下面式算出：
对于所有 i,j,k（包括题中各个非终止符），算出式 (2)中的各值。只要其中之一值为 1，便在相应当位置上打 √,否则打? 。如此便可填满整个识别表 [若左侧为 K的代换式有三个，可按上述原则，再增加计算将 (1)式中 K1,K2改为 K1’’、
K2’’后的各值，余类推 。
),1,1(),,1(
),2,2(),,2(
),1,1(),,1(
'
2
'
1
'
2
'
1
'
2
'
1
KijrKjir
KjirKjr
KjirKjr
现作为例子用递推规则考察 (2,2,A)中的 √ 或? 。由于左侧为 A的代换式只有 A→ BS一个，故此时对于 (1)式只需计算 r(1,2,B)? r(1,3,S)=1?1=1,即 (2,2,A)应打 √ 。
此结果与前面分析得到的相符。
根据上述递推规则和给定的文法，容易编制计算机程序。当待识别串 X进入时，按此算出识别表，并检查表中最后一列 S位置上是 √ 还是?；若为 √,便判属于给定文法相应的类别，否则判为不属于此类别。
作业：对 Younger法的例题编程上机，打出识别表。
四,CYK(Cocke-Younger-Kasami)剖析 (列表法 )
条件,① 适用上下文无关文法
② 产生式应符合 Chomsky范式已知输入串 X=a1a2...an
构造三角形剖析表步骤如下：
① 令 j=1,按从 i=1到 i=n次序,求 ti1.把 X
分解为长度为 1的子串,
对子串 ai,若 p中有 A→a i,把 A填入 ti1中
② 令 j=2,按从 i=1到 i=n-1次序,求 ti2，
即第二行 。 把 X分解为长度为 2的子串,
对子串 aiai+1,若 p中有 A→BC,且有 B→a i,C→a i+1
则把 A填入 ti2中
③ 对于 j>2,1≤i≤n,已求出 tij-1,现求 tij
对于 1≤k≤j 中的任一 k,当 P中有 A→BC 且 B在 tik中,C在 ti+k,j-k中时,把 A
填入 tij中
④ 重复 ③ 直至完成此表,或整行都是空 (拒识 )当且仅当 S在 tin中,
X?L(G),即由 G可导出 X
分析一个长度为 n的串,所用的存储量正比于 n2,运算次数正比于 n3。
1 2 3 4 5 i
5
4
3
2
1
tij
剖析表
j
例,G = (VN,VT,P,S) VT =（ a,b） VN =（ S,A,B,C）
P:① S→AB ② S→AC ③ A→a ④ B→b ⑤ C→SB
输入串,X=aabb=a1a2a3a4 所有产生式符合 Chomsky范式
① 令 j=1,计算 ti1,1≤i≤ 4
i=1,a1=a,∵P 中有 A→a ∴ 有 t11=(A)
i=2,a2=a,∵P 中有 A→a ∴ 有 t21=(A)
i=3,a3=b,∵P 中有 B→b ∴ 有 t31=(B)
i=4,a4=b,∵P 中有 B→b ∴ 有 t41=(B)
② 第一次迭代,令 j=2,计算 ti2,1≤i≤ 3
对于 a1a2=aa,∵ 不能产生 aa ∴ 有 t21=φ
对于 a2a3=ab,∵S→AB,A→a,B→b ∴ 有 t22=(s)
对于 a3a4=bb,∵P 中产生式不能产生 bb ∴ 有 t32=(φ )
1 2 3 4 i
j
4
3
2
1 A A B B
φ S φ
③ 第二次迭代,令 j=3,计算 ti3,1≤i≤ 2
对于 a1a2a3=aab,∵ 不能产生 aab ∴ 有 t13=φ
对于 a2a3a4=abb,∵C→SB,S→ab,B→b ∴ 有 t23=(C)
④ 第三次迭代,令 j=4,计算 ti4，
对于 a1a2a3a4=aabb,∵S→AC,A→a,C→abb ∴ 有 t14=(S)
∵ t14=S ∴X=aabb 在 L(G)中,∴ 此串被识别 。
此算法实际上是一个由底向顶剖析算法 。
4
3
2
1
A A B B
φ S φ
1 2 3 4 i
φ
S
C
剖析表
a a b b↓ ↓
↓↓A A B B
S
S
C
导出树
+
+
作业：对 CYK算法的例题上机编程，打出剖析表和导出树。
§ 7-4 自动机理论引言,x
当给出某类文法后，可根据它设计一种相应的称为自动机的硬件模型。它由控制装置、输入带和某些类型的存储器组成，这种硬件模型是一种识别器称自动机。不同的自动机可以识别不同的文法形成的语言。
0型文法：图灵机识别上下文有关型：线性约束自动机上下文无关型：下推自动机有限状态型：有限状态自动机识别器 X? L{G}
G
一,有限状态自动机 可以识别由有限状态文法所构成的语言
1、基本定义：五元式 M系统 M=(∑,Q,δ,q0,F )
其中,∑,输入符号的有限集合
Q：状态的有限集合
δ,状态转换函数是 QΧ ∑ 到 Q的一种映射
q0：初始状态 q0? Q
F：终止状态集合
2、有限自动机的结构转换函数,δ (q,a)=p
表示有限控制器处于 q状态，而输入头读入符号 a，则有限控制器转换到下一状态 p。
QF?
∑ 输入带
0 1 1 0
输入头有限状态控制器 Q q0→ q 1→,..F
3、自动机识别输入字符串的方式
L(M) = {x| δ (q0,x)在 F中 }
δ (q,x)＝ Φ 拒识，停机
4、自动机的状态转换图,表示自动机识别过程例,M=(∑,Q,δ,q0,F )
Q ＝ {q0,q1,q2,q3}
∑ ＝ {0,1}
F ={q0}
δ (q0,0)= q2,δ (q0,1)= q1,
δ (q1,0)= q3,,δ (q1,1)= q0,
δ (q2,0)= q0,δ (q2,1)= q3,
δ (q3,0)= q1,δ (q3,1)= q2
q0 q1
q2 q3
1
1
1
1
0 0 0 0
输入,x=110101
q0 q1 q0 q2 q3 q1 q0?F
∴ X可以识别
∴ δ (q0,110101)= q0
例：已知自动机状态转换图如下
x1=aab 可以识别
x2=abb 不可以识别可以识别的语言,L(G)=anb
qB状态，只有出没有进，为不可到达状态
qΦ状态，只有进没有出，为陷阱
1 1 0 1 10
a
b
baa b
q0 qA
qB q
Φ a,b
4、不确定的有限状态自动机即,δ (q,a)= {q1,q2,… qk}当输入 a时，下一个状态可能为多个状态之一。
例,M=(∑,Q,δ,q0,F )
Q ＝ {q0,q1,q2,q3,q4}
∑ ＝ {0,1}
F ={q2,q4}
δ (q0,0)= {q0,q3},δ (q0,1)= {q0,q1}
δ (q1,0)= Φ(在 q1不会输入 0)
δ (q1,1)= q2
δ (q2,0)= q2,δ (q2,1)= q2,
δ (q3,0)= q4,δ (q3,1)= Φ
δ (q4,0)= q4,δ (q4,1)= q4
状态转换图输入字串,010110
q0 q0 q0 q0 q0
q3 q1 q3 q1 q2 q2?F
q0 q3
q1
0 0
0,1
0,1
1
1
0,1
q4
q2
0 1 0 1
1 0
∴ 输入字符串 X=010110
可以被自动机识别，但在识别过程中，对不确定状态需要进行试探。
5、构造一个有限自动机定理 1：设 G = (VN,VT,P,S)为有限状态文法，一定存在一个有限状态自动机 M=(∑,Q,δ,S,F)使 L(G) = L(M).
已知有限状态文法 G = (VN,VT,P,S)
由有限状态文法构造有限自动机的步骤：
① ∑ ＝ VT
② Q ＝ VN∪{T}
③ q0 = S
④ 若 P中有 S→Φ,则 F = (S,T),否则 F = {T}
⑤ 若 P中有 B→a,则 δ (B,a) = {T},B? VN,a? VT
⑥ 若 P中有 B→aC,则 δ (B,a) = (C),B,C? VN,a? VT
⑦ 对 VT中所有的终止符 a,都有 δ (T,a) = Φ,a? VT
例：有限状态文法 G = (VN,VT,P,S) VN = {S,B} VT = {0,1}
P,S→0B,B→0B/ 1S/0 (B→0B,B→1S,B→0)
构造有限自动机 M=(∑,Q,δ,q0,F )
① ∵ ∑ ＝ VT ∴ ∑ ＝ {0,1}
② ∵ Q ＝ VN∪{T} ＝ {S,B,T}
③ q0 = S
④ ∵ P中无 S→Φ ∴ F = {T}
⑤ ∵ S →0B,∴ δ (S,0) = B,∵ B →0B,∴ δ (B,0) = B,
∵ B →1S,∴ δ (B,1) = S,∵ B →0,∴ δ (B,0) = T,
∵ P中无 S→1x,x? VN,∴ δ (S,1) = Φ
⑥ 对 VT = {0,1}有 δ (T,0) = δ (T,1)＝ Φ
∴ 构造的自动机 M为
M=(∑,Q,δ,q0,F ),∑ ＝ {0,1},Q= {S,B,T},
q0={S},F={T}
δ,δ (s,0)={B}
δ (s,1)=Ф
δ (B,0)={B,T}
δ (B,1)={S}
δ (T,0)=δ (T,1)=Ф
设 x=00100,可以识别可以证明,L(M)=L(G)
0
1
0
T
S B
0
6.由有限自动机 M构造有限状态文法定理 2：已知有限自动机 M，则有一个有限状态文法 G，使
L(G) = L(M)。
已知 M=(∑,Q,δ,q0,F )，构造 G = (VN,VT,P,S) 的步骤如下：
① VT＝ ∑ ② VN ＝ Q ③ S＝ q0
④ 对于 δ (B,a) = C,若 B,C?Q,a?∑,则 P中有 B→aC.
若 C?F,则还有产生式 B→a
例：已知有限自动机
M=(∑,Q,δ,q0,F ),Q ＝ {q0,q1,q2}
∑ ＝ {0,1} F ={q2}
δ (q0,0)= q2,δ (q0,1)= q1,δ (q1,0)= q2,,δ (q1,1)= q0
δ (q2,0)= q2,δ (q2,1)= q1
构造 G = (VN,VT,P,S) 如下,
① VT ＝ ∑ ＝ {0,1}
② VN= Q = {q0,q1,q2}
③ S = q0
④ ∵ δ (q0,0)= q2,,∴ 有 q0→0 q2,∵ q2? F ∴ 有 q0→0
∵ δ (q0,1)= q1,,∴ 有 q0→1 q1,
∵ δ (q1,0)= q2,,∴ 有 q1→0 q2,∵ q2? F ∴ 有 q1→0
∵ δ (q1,1)= q0,,∴ 有 q1→1q0,
∵ δ (q2,0)= q2,,∴ 有 q2→0q2,∵ q2? F ∴ 有 q2→0
∵ δ (q2,1)= q1,,∴ 有 q2→1q1,
∴ 有限状态文法为：
G = (VN,VT,P,S)
VT ＝ {0,1}
VN = {q0,q1,q2}
S = q0
P,q0→0 q2,q0→1q1,q0→0
q1→0 q2,q1→1q0,q1→0
q2→0 q2,q2→1 q1,q2→0
状态图输入 x＝ 1100
由自动机 M,δ (q0,1100)＝ q2,∵ q2? F ∴1100 可以接受由有限文法 G,q0→1q1→11q0→110q2→1100
∴ L(M) = L(G)
q0 q1
q2
1
1
1
1
1
1
0
0
0 0 0 0
0
0
0
q1q0
q2 T有限自动机有限状态文法二,下推自动机（ PDA）可以识别由上下文无关文法构成的语言
下推自动机结构：
七元式 MP = (∑,Q,δ,q0,Z0,F,Г )
其中 ∑,Q,,q0,F同有限自动机
δ,转换函数 Г,推下符号的有限集合 Z0,推下存贮器的起始符例如,δ (qi,b,Z) = (qj,β )
qi：目前状态,b：输入符号,Z：下推存储器的内容
qj,下一状态,β,下推存储器的下一状输入带 ∑
只读头有限状态器 Q
读写头下推存储器（堆栈型）
b
B
Z0
识别输入字串 X的方式
①终止状态方式
②空堆栈识别方式例：不确定的下推自动机
MP = ((q0),(a,b,c,d),(S,A,B,C,D),δ,q0,S,Φ )
即,Q= (q0),∑= (a,b,c,d),
Г = (S,A,B,C,D),Z0=(S),F=(Φ)
δ (q0,c,S) = {(q0,DAB),(q0,C)}
δ (q0,a,D) = {(q0,λ )},δ (q0,b,B) = (q0,λ )
δ (q0,d,C) = (q0,λ ),δ (q0,a,A) ={ (q0,AB ),(q0,CB )}
}),,(),,(,|{)( 00* FqrqzxqXXML ffP
)},(),,(,|{)( 00* qzxqXXML P
输入 x＝ caadbb
(q0,S ) → (q0,DAB) → (q0,AB) → (q0,CBB) → (q0,BB) → (q0,B)
→ (q0,C) → → (q0,ABB) →
→ (q0,λ )
堆栈变空,X=caadbb可以接受，这种不确定的下推自动机在识别过程中需试探进行。
c a a d b
da 不通 不通
b
例：确定自动机 MP = (∑,Q,δ,q0,Z0,F,Г )
∑ = (0,1) Q ＝ {q0,q1,q2}
Г ＝ (2,0) F =(q0) Z0 = (Z)
δ (q0,0,Z) = (q1,02),δ (q1,0,0) = (q1,00)
δ (q1,1,0) = {(q2,λ )},δ (q2,1,0) = (q2,λ )
δ (q2,λ,2) = (q0,λ )
X=0011
δ (q0,Z) → δ (q1,02) → δ (q1,002) → δ (q2,02) →
δ (q2,2) → δ (q0,λ )
堆栈变空,X＝ 0011可以被接受
0 0 1 1
λ
由上、下文无关文法 G = (VN,VT,P,S)构造一个下推自动机
MP = (∑,Q,δ,q0,Z0,F,Г )步骤如下：
① ∑ ＝ VT
② Г ＝ VN∪{ VT}
③ Z0 = S
④ Q = q0
⑤ F = φ (用堆栈变空来识别 )
⑥ 由 p构造 δ 函数
Ⅰ,若 A→ 在 P中,则有 δ (q0,λ,A) = (q0,)
Ⅱ,对 VT中所有终止符 a,有 δ (q0,a,a) = (q0,λ )
例,G={(s,A),(a,b,c,d),p,S}
P,S→cA,A→aAb,A→d
构造 MP = (∑,Q,δ,q0,Z0,F,Г )
① Q = q0
② ∑ ＝ VT＝ {a,b,c,d}
③ Z0 = S
④ Г ＝ VN∪{ VT}=(S,A,a,b,c,d)
⑤ F = Φ (由堆栈变空来识别 )
在 P中有 S→ cA,则 δ (q0,λ,S) = (q0,cA )
A→ aAb,则 δ (q0,λ,A) = (q0,aAb )
A→ d,则 δ (q0,λ,A) = (q0,d)
由上式可合并,δ (q0,λ,A) = {(q0,aAb),(q0,d) }
由规则 Ⅱ 对 VT：
δ (q0,a,a) = (q0,λ ),δ (q0,b,b) = (q0,λ )
δ (q0,c,c) = (q0,λ ),δ (q0,d,d) = (q0,λ )
对 x=caadbb
(q0,S ) → 无，可以先输入空格 λ 。
∴
(q0,S) (q0,CA) (q0,A) (q0,aAb) (q0,Ab) (q0,aAbb)
(q0,Abb) (q0,dbb) (q0,bb) (q0,b ) (q0,λ )堆栈空若文法符合 Creibadh范式，产生式形式为：
A →a α,A? VN,a? VT，
上面规则 Ⅰ,Ⅱ 合成一个规则，若 A →,
则有 δ (q0,a,A) = (q0,α )
C
λ
→
a
)(* 包括V N?
λ
→→→
λ
→
→
λ
→ → → →
c a
a d b b
例,Greibach范式文法
G = ({S,A,B},{a,b,c,d},P,S)
P,S→cA,A→aAB,A→d,B→b
可以构造一个下推自动机 MP = (∑,Г,Q,δ,Z0,q0,F)
其中 ∑ ＝ VT＝ {a,b,c,d},Г ＝ VN = (S,A,B),Q = q0
Z0 = S,F = Φ
因 P中有 S→ cA,则 δ (q0,c,S) = (q0,A )
A→ aAB,则 δ (q0,a,A) = (q0,AB )
A→ d,则 δ (q0,d,A) = (q0,λ )
B→ b,则 δ (q0,b,B) = (q0,λ )
形式，根据上面的规则这些产生式都符合?aA?
输入 X=caadbb
(q0,S) → (q0,A) (q0,AB) (q0,ABB) (q0,BB)
→ (q0,B) → (q0,λ )
只用六步就完成，而上例用九步。说明符合 Greibach范式的文法产生的语言容易被下推自动机识别。
c a a d
b b
→ → →
三、图灵机：可以识别 0型文法所产生的语言
1、结构
2、定义：一个图灵机 T是一个六元式 T = (∑,Q,Г,δ,q0,F )
其中：
Q：状态集合
Г ＝ ∑ ＋ B,B空
∑ = Г - B,q0起始状态,q0? Q
F:终止状态控制装置读写头输入带图灵机是最复杂的自动机。它的一个构型用三元式（ q,α,i）
表示 q? Q,α? (Г - B)*
映射 δ 的使用
δ (q,Ai)=(P,X,R)在 Ai处插入 X后右移
δ (q,Ai)=(P,X,L)在 Ai处插入 X后左移
3、图灵机 T所接受的语言
},),,(*|)1,,(|{)( *0* FqiqTXqXXTL
例,T = (∑,Q,Г,δ,q0,F )
∑ ＝ (0,1),Q=(q0,q1,… q5),
Г =(0,1,B,X,Y),F=(q5)
① δ (q0,0)= (q1,x,R ) ② δ (q1,0) = (q1,0,R)
③ δ (q2,Y) = (q2,Y,L) ④ δ (q3,Y) = (q3,Y,R)
⑤ δ (q4,0) = (q4,0,L ) ⑥ δ (q1,Y) = (q1,Y,R )
⑦ δ (q2,x) = (q3,x,R ) ⑧ δ (q3,B) = (q5,Y,R )
⑨ δ (q4,x) = (q0,x,R ) ⑩ δ (q1,1) =(q2,Y,L )
⑴ δ (q2,0) = (q4,0,L )
输入,x=0011,则图灵机运行如下：
(q0,0011,1 ) → (q1,x011,2 ) → (q1,x011,3 ) →
(q2,x0Y1,2) → (q4,x0Y1,1 ) → (q0,x0Y1,2 ) →
(q1,xxY1,3 ) → (q1,xxY1,4 ) → (q2,xxYY,3) →
(q2,xxYY,2 ) → (q3,xxYY,3 ) → (q3,xxYY,4 ) →
(q3,xxYY,5 ) → (q5,xxYYY,6) q5? F
∴ X ＝ 0011被接受
↓ ↓ ↓
↓
① ② ⑩
⑴ ⑨
⑥ ⑩ ③
④⑦
⑧
↓ ↓
↓ ↓ ↓
↓ ↓ ↓
↓
①
④
§ 7-5 误差校正句法分析一,解决噪声干扰的方法
① 推断文法时,考虑噪声干扰的样本
② 在预处理中,除掉噪声,平滑处理
③ 用随机文法,采用概率的概念,给句子的出现加上概率的分布
④ 用转换文法,把有噪声句子转换为无噪声句子
⑤ 用误差校正剖析句法集群法二,随机文法
定义：四元式 GS = (VN,VT,PS,S)
PS形式,α i→ β ij j=1,2...n i=1,2...k
其中 α i,β ij?( VN∪ VT)*
Pij,α i产生 β ij的可能性为 Pij,称为产生概率 。
产生概率 Pij满足,0≤P ij≤ 1以及出现概率 P(X)满足,等于产生概率的乘积 。
用 GS产生的语言称为随机语言 。
L(Gs)={(x,P(x))|X?V T*,S→X,j= 1,2...k,且 }
1
1
n
j
ijp
pxP iki 1)(
pxP jkj 1)(
pij
pj
假如某随机文法为：
Gs = (VN,VT,P,S)
VN={A1,A2,.… Ak} VT={a1,a2,.… am},S=A1
PS形式：
其中
1
1
0
1 1
m
l
l
i
k
j
m
l
l
ij pp
Aa
p
A
Aa
p
A
Aa
p
A
Aa
p
A
kmi
ili
i
i
m
ik
l
ij
i
i
.....
,
22
11
2
1
1
1
a
p
A
a
p
A
a
p
A
mi
li
i
m
i
l
i
i
0
0
1
0
..,.,
1
例：有随机文法 Gs = (VN,VT,P,S)
VN={S,A,B} VT={0,1}
PS形式,S→ 1A B→ 0 B→ 1S
A→ 0B A→ 1
导出式
S→ 1A→ 10B→ 100,P(X)=P(100)=1ⅹ 0.8ⅹ 0.3=0.24
S→ 1A→ 11,P(X)=P(11)=1ⅹ 0.2=0.2
由 Gs产生的语言 L(Gs)
产生的链 X P(X)出现的概率
11 0.2
100 0.24
(101)n11 0.2ⅹ( 0.7ⅹ 0.8)n
(101)n100 0.24ⅹ( 0.7ⅹ 0.8)n
1 0.3
0.8 0.2
B
S
A
1
1
1
P=0.7
P=0.8
P=0.2
P=0.3
0
00.7
T
用随机文法作识别
① 用大量的样本去推断随机文法,每个随机文法代表一类
② 检查待识别的样本符合哪一个随机文法,就把它归于该随机文法所代表的一类
③ 若待识别的样本符合二个以上的随机文法再求待识别样本对每一类的出现概率，把待识别样本归于出现概率最大的一类。
例：关于,7‖,,1‖的手写体数字产生,1‖的随机文法 G1 = (VN,VT,P,S)
VN={S,A,B,C,D,E,F,H,I}
VT={0,1,3,4,5,6,7}
0
123
4
7 005555 05555 0055565
―1‖
基元
P形式：? S→0A? A→0B? B→5C? C→5D
D→ 5E? D→ 5? E→ 5? A→ 5F
F→ 5H? H→ 5I
⑴ I→5
P1=1 P2=0.2 P3=1 P4=1
P5=0.75 P6=0.25 P8=0.8
IA
B
C D
E
S
H
F
0
0
5
5
5
5
5 5
5 5
5
状态图
T
GT = (VN,VT,P,S)
VN={S,A1,B1,C1,D1,E1,F1,O1,G1} VT={1,2,3,4,5,6,7}
P形式：
S→ 0A1? A1→ 0B1? B1→ 0C1? C1→ 5D1
D1→ 5E1? E1→ 5F1? F→ 5? E1→ 5
B1→ 5O1? O1→ 5G1 ⑴ G1→ 5
0005555 000555 00555
关于手写
,7‖的随机文法
P3=0.8
P6=0.375 P8=0.625
P9=0.2
0
123
4
765
基元状态图设待识别链 X=00555
① 用,7‖随机文法产生,00555‖
S→ 0A1→ 00B1→ 005O1→ 0055G1→ 00555
P7(00555)= P1P2P9P10P11=0.2 出现的概率为 0.2
② 用,1‖随机文法产生,00555‖
S→ 0A→ 00B→ 005C→ 0055D→ 00555
P7(00555)= P1P2P3P4P6=0.05 出现的概率为 0.05
∵P 7(00555)> P1(00555) ∴X= 00555? 7
A1
B1
C1 D1
E1
F
S
P1
O1
0
0
5
5
5
5
0 5
5 5
5
① ② ⑨ ⑩ ⑴
① ② ③ ④ ⑥
T
怎样求代表各类的随机文法
① 先求出代表各类的一般文法 (用一般文法的文法推断 )
② 用统计法由训练样本求出现概率
③ 再由出现概率求产生概率例：关于,7‖,,1‖,找大量人写,7‖,,1‖并进行统计如下关于手写,7‖,X1=0005555 P(X1)=30%
X2=000555 P(X2)=50%
X3=00555 P(X3)=20%
关于手写,1‖:
先用以上训练样本推断出一般文法,(用链文法的推断方法 )
然后在各产生式上加产生概率就可以了 。 现在就变成求产生概率的问题 。
0 0 5 5 5
0 5 5 5 5
0 0 5 5 5 5
'
3
'
2
'
1
X
X
X
%5)(
%80)(
%15)(
'
3
'
2
'
1
XP
XP
XP
再用每一个训练样本的出现概率求产生概率
P1P2P3P4P5P6P7=0.3 ——X1=0005555
P1P2P3P4P5P8=0.5 ——X2=000555
P1P2P3P10P11=0.2 ——X3=00555
∵P 1=P2=P4=P5=P7=P10=P11=1
∴P 3P6=0.3
P3P8=0.5
P9=0.2
∵P 3+P9=1
∴P 3=0.8
P6=0.375,P8=0.625
用同样的方法可求出其它产生概率三,句法集群法输入句法模式取样 X=(x1,x2,..,xs)
其中 xi为终止符集合 xi=a1a2...
输出：要求把 xi分配到相应的 m个子集中 (即 m类 ),并给出每个集群的文法 G(k),k=1,2,… m
输入第一个取样 x1,由 x1推出文法 G1(1)
∴x 1?L(G 1(1))
输入 x2,计算 d(x2,L(G1(1)))长度,判定 x1和 x2的相似度 。
① 若 d(x2,L(G1(1)))<t,则 x1,x2? 集群 1,由 x1,x2推出文法 G2(2)
② 若 d(x2,L(G1(1)))≥t,则 x1,x2 集群 1,对 x2推出新文法 G1(2)
t为门限
③ 对新的取样重复第二步,最后获得 m个集群,对应文法为
Gn1(1),Gn2(2)..,Gnm(m)
关于门限 t的选择：
假定已知 m类句法模式取样 X(1),X(2)..,X(m)
m类取样对应的文法分别为 G(1),G(2)..,G(m)
文法对应的语言为 L(G1),L(G2)..,L(GM)
门限 t由下式决定：
其中 X(K)是类别 k中的一个取样
L(GL)是类别 L的语言上式说明门限 t应小于 X(K)同文法 G1,G2,… Gm的语言的最小距离,只有这样才能把 m类分开 。
) ) }(,({m in )(
,G
Lxdt lk
lk
lk
K=1,2….m
L=1,2…..m
四,最小距离法
对句法模式的度量
① 两个模式间的距离
d(x,y)=min(x→y) 由模式 x导出 y的最小变换次数
② 句子和语言间的距离
d(x,L(G))=min{d(x,y)}
③ 求输入句子 X和语言 L(G)的距离,即是在语言 L(G)中寻求和句子 X具有最小距离的句子 Y。 为了获得这一距离,
必须搜索 L(G)中所有句子,从中找到和 X最近的句子 Y。
可写成如下形式：
的一个句子为 )()(),( GLGLyGLx
)}(|),({m i n)}(,{,..2,1 GLYYXdGLXd iiimi
最小距离句法识别
① 二类问题,G1,G2代表二类
d(x,L(G1))< d(x,L(G2)),则 x?L(G 1) ∴x?G 1
d(x,L(G1))> d(x,L(G2)),则 x?L(G 2) ∴x?G 2
② 多类情况,G1,G2...Gm
相应的语言为,L(G1),L(G2)…,L(GM)
对未知模式 X进行归类的最小距离规则为
d(x,L(G(i)))=min[d(x,L(G(k)))] k=1,2,...m
则 x?L(G (i)) ∴x?G (i)
