形式语言概述 文法推断 句法分析 自动机理论 误差校正句法分析 第七章        句法结构模式识别 形式语言概述 文法推断 句法分析 自动机理论 误差校正句法分析

§7-1 形式语言概述 一、基本概念 1、字母表：与所研究的问题有关的符号集合。 例：V1={A,B,C,D}, V2={a,b,c,d} §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} 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 ：非终止符，用大写字母表示 产生式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 c b c b c b a 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 ⑦ ① ⑥ 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)

包含关系：限制不严格的文法必然包含限制严格的文法。 四种文法的关系 : 包含关系：限制不严格的文法必然包含限制严格的文法。 0型 1型 2型 3型

三. 图象描述语言（PDL） 1970年，Show提出图像描述语言 任何图象都可用头尾来表示 定义了四种二元连接算子 1. a + b 2. a x b 3. a – b 4. a * b 头 头 h 基元b t 尾 尾 h b a a头与b尾相连 t h b a a尾与b尾相连,形成两个头 t h a t h b a头与b头相连，形成一头二尾 t h t h a头连b头, a尾连b尾，形成一头一尾 t

h t 一元算子~ 一个基元的头或尾可以与另一基元的头或尾相连而成为 模式串，并可设置一些较复杂的联结关系和进行各种运 算。 例：文法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) b ~b t h a b c d

L(G) = {(b+(((b+c)*a)+c)) ; ((d+(a+(~d)))*((b+c)*a))} 导出过程 a S S A B C b + d + c C + a + d a ~ b + c * b a + c *

求ＰＤＬ表达式的规则： ①   脱括号由内往外的次序进行，无括号由左向右进行 ②   对于连接基元组成基元结构，必须符合规定的连接 点头，尾数目 例：给出一个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 b a b b a b a c c a b ~d ~d d b a d ⑶ ⑷ ⑴ ⑵

四.标准形式文法 在句法分析和自动机的一些算法中，有时要求标准化文法，下 面介绍二种标准文法。 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

用下面的产生式集合代替： 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

符合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则 用九步才导出

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

VT ＝( →, ↗ ), r(a)=(2,0), r(b)=(2,0), r(k)=2 P: ① S→K ② A→a ③ B→b 例：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 ① S→K ① b 导出树 A B k ② ③ a b A B a 导出图 ④ ⑤ A B A B a b a ④ ⑤ ④ ⑤ k b a b a b

例2：在氢云室内用正粒子打击核目标碰撞发出的射线可以用 树文法来描述。 树文法Gt = (v, r, P, S) ，VN＝（S,A,B）， VT ＝(a, b) 基本定义： P: b (凹弧) (凸弧) a S → a S → a S → a S → a | S A A A B B B A B A A B B A → a A → a B → a B → a | | A B

r(a)=(0,1,2,4,6), r(b)=(0,1) 射线导出树： 射线图： a S → a b a a a a a a a a b a b b a a b a b b a a b a b b a a b a b b a b

根据已知L(G)样本集导出未知文法G的过程。 §7-2 文法推断 根据已知L(G)样本集导出未知文法G的过程。 (一)基本定义： 1.若在产生式中至少有一个产生式存在以下形式： Ai→αiAiβi 此文法G = (VN, VT, P, S) 是循环文法或不确定，由它产生的语言L(Gt)为无限的。 2.若文法G为不循环的，则必为确定的，且L(G)为有限的。 St=(x1, x2… xt) Gt 样本集 推断算法 导师

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), )也是完备的。

(二) 有限状态文法推断 状态图表示方法，文法可以用图来表示 例：G = (VN,VT, P, S) VN = {S, A, B, C} 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 S 1 1 1 A C B 1 1 T

一.规范确定文法 已知正取样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 状态图： 显然对任一有限取样都可用此法推断出规范文法，方法 简单，适用计算机运算。缺点是非终止符太多，产生式 也多。 S 1 Z6 1 Z4 Z2 1 Z1 Z7 Z5 Z3 1 1 1 Z8 T

定义导出文法GD = (VND,VT, PD, Bs)是由规范文法Gc产生 的文法，导出规则如下： ① VT相同 二.导出文法（简化规范文法） 设：Gc为规范文法，非终止符集合VN={S,Z1,Z2,... Zn }, 把VN分成r个子集: VND={Bj,B1,B2... Br} S∈Bj, Zi∈Bj 这些子集满足： Bj∩Bk=Ф, j≠k ∪Bj = 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) 这种方法由于分割方式不同会导出不同的文法而分割 方式又无系统理论作指导，而靠经验和试探。 1 状态图 导出文法等效规范文法 L(GC)=L(GD) 这种方法由于分割方式不同会导出不同的文法而分割 方式又无系统理论作指导，而靠经验和试探。 B5 1 1 1 1 B2 B3 B1 1 1 T

三.形式微商文法 形式微商定义：集合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 1 U2 U3 T 1 0.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+ 以外的子串来，有时这是不允许的。 S 1 1 0,1 S S U3 1 U3 U2 T U2 U4 U2 K=2,3 1 T 1 K=1 K=4 T

一棵树可以看成一个多枝的链。因此前边讲的链（串） 文法的推断方法可以用在树文法的推断上。任何一个数 字化的网络模板都可以用树结构来表示如下： 三.树文法推断 一棵树可以看成一个多枝的链。因此前边讲的链（串） 文法的推断方法可以用在树文法的推断上。任何一个数 字化的网络模板都可以用树结构来表示如下： 由下面的四种方式表示成树枝全从根开始的树。 X11 X12 ... X1n X21 X22 X2n Xn1 Xn2 Xnn 树状的数字化网络模式 树干 S S 根 M个枝 ….. ….. N个枝 树干

①树文法先选一个合适的树干，由树干推出一个链文法 ②再推各树枝的文法 ③把树干文法与树枝文法合并 根S 树枝 树干 S 树干 树枝

例：已知数字化模式 L1 L2 L3 L4 L5 L6 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 R1 R2 R3 R4 R5 R6 根S 树干

①先由树干推出树干文法GA P: L1 L2 S | → A1 | A1 → $ — A2 A2 → $ — A3 | | R1 R2 L3 L6 L5 L4 | | | | A3 → $ — A4 A6 → $ A5 → $ — A6 A4 → $ — A5 | | | | R3 R6 R5 R4

②上面推出树干文法GA,再推出树枝文法GL1, GL2... GL6,GR1, GR2,... GR6 ③再将树干文法与树枝文法合并 GT= GA∪GL∪GR

§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 X∈L{G2} X∈ωi 判决 待识别句子 识别结果 G2 …… X∈L{GM} GM 句法分析过程

二句法分析的主要方法 1参考匹配法： 2状态图法：适用于有限状态文法 x 例：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∈Xi X∈ωi x X∈样本链码X2 X∈L{G2} 判决 …… X∈样本链码XN

由状态图可以知道此文法可以识别的句子 X1=10n+1 , X2=00 , X3=10n10, X4=10n+1 未知句子：由状态图可知 S 1 1 1 B C A T 状态图

2、填充树图法(适用于上下文无关文法)： 当给定某待识别链X及相应的文法G时，我们建立一个以X 为底，S为顶的三角形，按文法G的产生式来填充此三角形， 使之成为一个分折树。若填充成功表明 否则 填充树有二种方法 ①由顶向底剖析 ②由底向顶剖析 填充树图法在填充三角形时应遵守三条原则： ①首位考察：首先考虑选用某个产生式后能导出X的 第一个字符 ②用某产生式后，不能出现X中不包含的终止符 ③用某产生式后，不能导致符号串变长(变短) S X

⑴由顶向底(由上而下)剖析 例：G = (VN,VT, P, S) VT =（0,1） VN =（S, A, B） P: ① S→1 ② S→B1 ③ S→B ④ B→1A ⑤ B→B1A ⑥ A→0A ⑦ A→0 设：X=1000，用由上而下剖析方法判断X是否属于L(G) S S S ③ B B B ④ A 1 1 A ⑥ A ⑥ ∴ X=1000∈L(G) A ⑦

P: ① S→T ② I→a ③ S→Tfs ④ I→b ⑤ T→IgT ⑥ I→c ⑦ T→I 设：X=afbgc ①用I→a ②用T→I ⑵由底向顶(由下而上)剖析 例：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 T I ② T ③ ④ ① ↓ ↓ ↓ I I a f b g c I ↓ ↓ ↓ a f b g c a f b g c T T T ⑥ ⑤ ↓ ↓ ↓ I I I I I I ↓ ↓ ↓ ↓ ↓ ↓ a f b g c a f b g c

⑥用T→IgT ⑦用S→T ⑧用S→TfS S ↓ T T T T T T ↓ ↓ ↓ ↓ I I I I I I ↓ ↓ ↓ ↓ ↓ ↓ a f b g c S a f b g c S T ∴ X=afbgc ∈ L(G) T T ↓ ↓ I I I ↓ ↓ ↓ a f b g c

三、杨格(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代表子串中符号的 ⑶ 识别表的建立，关键问题是根据给出的待识别串X,建 立一识别表。对于202102,根据所给出的文法算得的识别 表如下：

i   1 2 3 j 4 5 6 所有子串 20 02 21 10 202 021 210 102 所有 VN S √ • A B       4   5 6 1 2 3 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符合给出的文法。反之，即 判不符合此文法。

⑷ 建立识别表的递推规则 递推规则：将要决定√ 或• 的位置表为(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）

(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’’后的各值，余类推。 ⑵

作业：对Younger法的例题编程上机，打出识别表。 现作为例子用递推规则考察(2, 2, A)中的√ 或• 。由于 左侧为A的代换式只有A→BS一个，故此时对于(1)式只 需计算r(1, 2, B) • r(1, 3, S)=1 •1=1 ,即(2, 2, A)应打√。 此结果与前面分析得到的相符。 根据上述递推规则和给定的文法，容易编制计算机程 序。当待识别串X进入时，按此算出识别表，并检查表中 最后一列S位置上是√ 还是•；若为√ ，便判属于给定文 法相应的类别，否则判为不属于此类别。 作业：对Younger法的例题编程上机，打出识别表。

剖析表 j 四.CYK(Cocke-Younger-Kasami)剖析(列表法) 条件：①适用上下文无关文法 ②产生式应符合Chomsky范式 已知输入串X=a1a2...an 构造三角形剖析表步骤如下： ①令j=1,按从i=1到i=n次序，求ti1.把X 分解为长度为1的子串， 对子串ai,若p中有A→ai,把A填入ti1中 ②令j=2,按从i=1到i=n-1次序，求ti2， 即第二行。把X分解为长度为2的子串， 对子串aiai+1,若p中有A→BC,且有B→ai, C→ai+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。 5 4 3 2 1 tij 1 2 3 4 5 i 剖析表

例：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=(φ) j 4 3 2 1 φ S φ A A B B 1 2 3 4 i

对于a1a2a3=aab, ∵不能产生aab ∴有t13=φ ③ 第二次迭代，令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)中， ∴此串被识别。 此算法实际上是一个由底向顶剖析算法。 + + S 4 3 2 1 S C φ C 导出树 S φ S φ A A B B A A B B ↓ ↓ ↓ ↓ 1 2 3 4 i a a b b 剖析表

作业：对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。 ∑ 输入带 1 1 输入头 q0→ q1→ ...F 有限状态控制器Q

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 1 q0 q1 1 1 q2 q3 1

x1=aab 可以识别 输入：x=110101 q0 q1 q0 q2 q3 q1 q0∈F ∴ X可以识别 例：已知自动机状态转换图如下 x1=aab 可以识别 x2=abb 不可以识别 可以识别的语言：L(G)=anb qB状态，只有出没有进，为不可到达状态 qΦ状态，只有进没有出，为陷阱 1 1 1 1 a b q0 qA b a a b 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

∴ 输入字符串X=010110可以被自动机识别，但在识别过程中，对不确定状态需要进行试探。 状态转换图 输入字串：010110 q0 q0 q0 q0 q0 q3 q1 q3 q1 q2 q2∈F 0，1 q3 q4 q0 1 0，1 q1 1 ∴ 输入字符串X=010110可以被自动机识别，但在识别过程中，对不确定状态需要进行试探。 q2 0，1 1 1 1

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=(∑,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) B S 1 T

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

①VT ＝∑＝ {0, 1} 构造G = (VN,VT, P, S) 如下： ② 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

由自动机M： δ(q0,1100)＝ q2， ∵ q2 ∈F ∴1100可以接受 状态图 输入x＝1100 由自动机M： δ(q0,1100)＝ q2， ∵ q2 ∈F ∴1100可以接受 由有限文法G： q0→1q1→11q0→110q2→1100 ∴ L(M) = L(G) 1 1 q0 q1 q0 q1 1 1 1 1 T q2 q2 有限自动机 有限状态文法

二.下推自动机（PDA）可以识别由上下文无关文法构成的语言 ⑴ 下推自动机结构： 七元式MP = (∑,Q,δ,q0, Z0 ,F, Г ) 其中∑,Q,,q0,F同有限自动机 δ:转换函数 Г:推下符号的有限集合 Z0 :推下存贮器的起始符 例如：δ(qi,b,Z) = (qj, β) qi：目前状态， b：输入符号， Z：下推存储器的内容 qj ：下一状态 ，β：下推存储器的下一状 输入带∑ b 只读头 Z0 读写头 B 有限状态器Q 下推存储器（堆栈型）

⑵ 识别输入字串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 )}

(q0, S ) → (q0,DAB) → (q0,AB) → (q0,CBB) → (q0,BB) → (q0,B) 输入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 a d 不通 不通 b

δ(q1,1,0) = {(q2, λ )}, δ(q2,1,0) = (q2, λ ) δ(q2, λ,2) = (q0, λ ) 例：确定自动机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可以被接受 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) }

δ(q0, a, a) = (q0, λ )， δ(q0, b,b) = (q0, λ ) 由规则Ⅱ对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 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, λ)

输入X=caadbb (q0, S) → (q0, A) (q0,AB) (q0,ABB) (q0,BB) → (q0, B) → (q0, λ) 只用六步就完成，而上例用九步。说明符合Greibach范式的文 法产生的语言容易被下推自动机识别。 a a c d → → → b b

2、定义：一个图灵机T是一个六元式 T = (∑, Q, Г ,δ,q0, F ) 其中： Q：状态集合 Г＝ ∑＋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所接受的语言

例： 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 )

(q1, xxY1,3 ) → (q1, xxY1,4 ) → (q2, xxYY,3) → (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 误差校正句法分析 一、解决噪声干扰的方法 ①推断文法时，考虑噪声干扰的样本 ②在预处理中，除掉噪声，平滑处理 ③用随机文法,采用概率的概念，给句子的出现加上概率的分布 ④用转换文法，把有噪声句子转换为无噪声句子 ⑤用误差校正剖析句法集群法

Pij: αi产生βij的可能性为Pij，称为产生概率。 产生概率Pij满足： 0≤Pij≤1以及 二、随机文法 ⑴定义：四元式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≤Pij≤1以及 出现概率P(X)满足： 等于产生概率的乘积。 用GS产生的语言称为随机语言。 L(Gs)={(x,P(x))|X∈VT*,S→X,j=1,2...k,且 } pij pj

假如某随机文法为： Gs = (VN,VT, P, S) VN={A1, A2,.…Ak} VT={a1, a2,.…am} ，S=A1 PS形式： 其中

例：有随机文法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 S P=0.7 1 1 P=0.8 1 0.3 0.7 B A P=0.2 0.2 0.8 1 P=0.3 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} 2 3 1 4 “1” 5 7 00555 6 005555 05555 基元

P形式：⑴S→0A ⑵A→0B ⑶B→5C ⑷C→5D ⑸D→5E ⑹D→5 ⑺E→5 ⑻A→5F ⑼F→5H ⑽H→5I ⑾I→5 P3=1 P1=1 P2=0.2 P4=1 P5=0.75 P6=0.25 P8=0.8 5 S F 5 H 5 I A 5 状态图 B 5 E 5 C D T 5 5 5

关于手写“7”的随机文法 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 2 关于手写“7”的随机文法 1 3 4 7 0005555 000555 00555 5 6 基元 P3=0.8 P6=0.375 P8=0.625 P9=0.2

状态图 S T 设待识别链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 ∵P7(00555)> P1(00555) ∴X=00555∈7 5 S O1 5 P1 5 T A1 5 5 5 E1 5 B1 F C1 D1 5 ① ② ⑨ ⑩ ⑾ ① ② ③ ④ ⑥

⑶怎样求代表各类的随机文法 ①先求出代表各类的一般文法(用一般文法的文法推断) ②用统计法由训练样本求出现概率 ③再由出现概率求产生概率 例：关于“7”，“1”，找大量人写“7”，“1”并进行统计如下 关于手写“7”: X1=0005555 P(X1)=30% X2=000555 P(X2)=50% X3=00555 P(X3)=20% 关于手写“1”: 先用以上训练样本推断出一般文法,(用链文法的推断方法) 然后在各产生式上加产生概率就可以了。现在就变成求产 生概率的问题。

再用每一个训练样本的出现概率求产生概率 P1P2P3P4P5P6P7=0.3 ——X1=0005555 P1P2P3P4P5P8=0.5 ——X2=000555 P1P2P3P10P11=0.2 ——X3=00555 ∵P1=P2=P4=P5=P7=P10=P11=1 ∴P3P6=0.3 P3P8=0.5 P9=0.2 ∵P3+P9=1 ∴P3=0.8 P6=0.375 , P8=0.625 用同样的方法可求出其它产生概率

输出：要求把xi分配到相应的m个子集中(即m类)，并给出每个集群的文法G(k)，k=1,2,…m 三、句法集群法 输入句法模式取样X=(x1, x2,... xs) 其中xi为终止符集合xi=a1a2... 输出：要求把xi分配到相应的m个子集中(即m类)，并给出每个集群的文法G(k)，k=1,2,…m ⑴输入第一个取样x1,由x1推出文法G1(1) ∴x1∈L(G1(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类分开。 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。 可写成如下形式：

⑵最小距离句法识别 ①二类问题：G1，G2代表二类 d(x,L(G1))< d(x,L(G2)),则x∈L(G1) ∴x∈G1 d(x,L(G1))> d(x,L(G2)),则x∈L(G2) ∴x∈G2 ②多类情况：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)