形式语言概述 文法推断 句法分析 自动机理论 误差校正句法分析

Presentation on theme: "形式语言概述 文法推断 句法分析 自动机理论 误差校正句法分析"— Presentation transcript:

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

2 6.1 句法模式识别概述 模式用句子形式描述，结构信息十分重要。 模式 句子 子模式 词组 基元 单词 组合关系 自然语言的文法
6.1 句法模式识别概述 模式用句子形式描述，结构信息十分重要。 模式 句子 子模式 词组 基元 单词 组合关系 自然语言的文法 句法模式识别用小而简单的基元与语法规则描述和识别 大而复杂的模式，通过对基元的识别，进而识别子模式，最终识别复杂模式。 符合某个文法的所有句子的集合 一个模式类

3 墙壁 f 地板 g E D B b a d c e （b） 图6.1 景物结构描述 与英文句子句法描述的对比 （c）

4 句法模式识别系统的组成： 句法模式识别存在的主要问题： * 基元选择尚无通用的方法； * 文法推断理论远不及统计学习发展得成熟。 句法模式识别的理论基础：形式语言 20世纪50年代中期乔姆斯基（Chomsky）。

5 §6-2 形式语言概述 一、基本概念 1、字母表：与所研究的问题有关的符号集合。 例：V1={A,B,C,D}, V2={a,b,c,d}
§6-2 形式语言概述 一、基本概念 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 6、V. :由字母表V中的符号组成的所有句子的集合，包括空句子λ在内。例： V
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}

7 用英文字母表尾部的小写字母x，y，v，w等表示。
终止符组成的字符串： 用英文字母表尾部的小写字母x，y，v，w等表示。 终止符和非终止符组成的混合字符串： 用希腊字母α，β，γ等表示。 性质： （字母表） （空集） P：生成式的有限集。用文法产生句子时的重写规则。 字符串 替换 字符串 S：起始符，代表模式本身，特殊的非终止符。 用生成式构成句子时，必须由左边是S的生成式开始。

8 一种语言有一种文法，由文法G构成的语言用L(G)表示：
由终止符组成 VT中字符组成的 所有句子的集合 文法G的 推导关系

9 ① ② ③ ⑤ 解： 是 说明： 利用文法构成句子时，除第一个生成式必须利用左边 为起始符 S 的生成式外，其余生成式使用的先后次序及重 复使用的次数都不受限制。

10 二. 短语结构文法 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→λ(空格)

11 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：上下文有关文法 ① ② ③ ④ ⑥

12 例：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型文法的要求

13 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

14 ① ② ③ ⑤

15 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

16 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 ① ③ ② ④ ① ⑥ ② ③ ② ① ② ④ ⑥ ③ ④ ⑥ ⑥

17 两种方法替换非终止符： ① 最左推导：每次替换都是先从最左边的非终止符开始，例如上边的例子。我们经常采用最左推导。
② 最右推导：每次替换都是先从最右边的非终止符开始， 例如： S→S+T →S+F →S+a → T+a → F+a → a+a

18 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)

19 四种文法的关系 : 包含关系：限制不严格的文法必然包含限制严格的文法。
四种文法的关系 : 包含关系：限制不严格的文法必然包含限制严格的文法。 0型 1型 2型 3型 后一种文法的限制比前一种文法的限制严格； 限制愈多的文法愈容易推断； 句法模式识别中多采用上下文无关文法和正则文法。

20 6.3 模式的描述方法 根据结构特征对模式进行描述。 —— 结构描述法，又称句法表示法。 模式的表示：链表示法、树表示法、图表示法。
6.3 模式的描述方法 根据结构特征对模式进行描述。 —— 结构描述法，又称句法表示法。 模式的表示：链表示法、树表示法、图表示法。 对应的文法：链文法（串文法）、树文法、图文法。 还有网文法、阵列文法等。 6.3.1 基元的确定 目前关于基元的确定没有一个通用的解决办法。 基元的选择遵循两个基本原则。

21 1．基元应是模式的基本单元，能够通过一定的结构关系对数 据进行紧凑、方便地描述。 2．基元应该容易用现有的非句法方法进行提取或识别。
例如：语音识别中 —— 音素； 识别手写文字 —— 笔划。 模式的链表示法 1．链码法 用不同斜率的直线段或曲线段为基元表示图形模式。 链码： 用字符表示基元后，被描述的 图形表示成的字符串。 弗利曼链码： 以八个基本方向的有向线段为基元， 用0~7八个数字符号表示。 弗利曼链码基元

22 简称PDL（Picture Description Language，PDL）。
编码： 矩形网格覆盖； 折线化和量化； 形成链码(有序结构)。 例：“2”的链码表示为 数字“2”的折线化和量化结果 2．图形描述语言法 简称PDL（Picture Description Language，PDL）。 基本基元：有向线段(直线段、弧线段) 。 由 “头(箭头端)” 和 “尾” 构成。

23 图象描述语言（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

24 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

25 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 *

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

27 可以导出手写大写字符“A”的四种表达式⑵⑶⑷ ⑴ S →(A+(B)) →(a+(B)) →(a+((C)+D) ) →(a+((E
可以导出手写大写字符“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 ⑶ ⑷ ⑴ ⑵

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

29 用下面的产生式集合代替： A→Y1Y2. n Y2. n→Y2Y3. n … Yn-1
用下面的产生式集合代替： A→Y1Y2...n Y2...n→Y2Y3...n … Yn-1...n→Yn,,n-1 Yi∈VN 若θi ∈ VN,则令Yi=θi；若θi ∈ VT,再引入Yi→θi

30 例：把文法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

31 符合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 Y1Y →baY2345→ baY2Y345 →babY345 →babAY45 →babaY5 →bababY5 →bababa 用原文法G1 只用四步可以导出bababa而用标准文法G2则 用九步才导出

32 2. 格雷巴赫范式(Greibach) 若一个上下文无关文法具有P形式： A→aα, A∈VN, a∈VT, α∈VN
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,

33 高维文法：上面我们介绍的都是一维链（串）文法，为了描
述更复杂的图形、图象, 需要用高维文法,包括树文法，图文法, 网文法等等。 6.3.3 模式的树表示法 高维表示法。 1．树的定义 树T是一个或一个以上结点的有限集合，并且满足： 1）存在一个唯一的指定为根的结点； 2）其余结点分为m个不相交的集合T1，T2，…，Tm，其中 每一个集合本身都是一个树，称为T的子树。 树的有序性： 同一层上各子树交换位置构成的树不同。 秩： 一个结点具有子树的个数，结点a的秩记为 r(a) 。 叶结点的秩为零。

34 长方体 基元 树结构描述 例： —— 结点a的秩可能是2，l或0。 结点a可能有 2，1或0个分枝

35 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中结点的树集合

36 由树文法Gt产生的语言L(Gt)是一些树的集合即模式集：
树文法定义为四元式 以字母表中字母 为根结点的树的秩 起始树的有限集 字母表 生成式的有限集 由树文法Gt产生的语言L(Gt)是一些树的集合即模式集： 所有结点都是终止符 的树的集合 树T由S中的起始树Ti开始， 用文法Gt的生成式逐步导出

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

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

39 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

40 试判断图6.7所示的树是否属于L(Gt)的一个句子。 解：生成式① ② ③中右边的树分别用T1，T2 ，T3表示。有
图6.7 模式 的树状表示

41 3．扩展树文法 其中，P中生成式 形式： 一个树文法有一个对应的扩展树文法。

42 例6.6 构成例6.5中树文法对应的扩展树文法。

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

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

45 (二) 有限状态文法推断 状态图表示方法，文法可以用图来表示 例：G = (VN,VT, P, S) VN = {S, A, B, C}
P: ① S→0A ② A→0A ③ B→ ④ B→0B ⑤ S→1B ⑥ A→1B ⑦ C→0C ⑧S→1C ⑨ A→ ⑩ C→1 T：附加状态 此文法可以产生的字符串 x1=00n1, x2=0n+110m+1, x3=10n+1, x4=10n1 S 1 1 1 A C B 1 1 T

46 一.规范确定文法 已知正取样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+

47 例：已知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,

48 状态图： 显然对任一有限取样都可用此法推断出规范文法，方法 简单，适用计算机运算。缺点是非终止符太多，产生式 也多。 S
1 Z6 1 Z4 Z2 1 Z1 Z7 Z5 Z3 1 1 1 Z8 T

49 二. 导出文法（简化规范文法） 设：Gc为规范文法，非终止符集合VN={S,Z1,Z2,
二.导出文法（简化规范文法） 设：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

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

51 状态图 导出文法等效规范文法 L(GC)=L(GD) 这种方法由于分割方式不同会导出不同的文法而分割 方式又无系统理论作指导，而靠经验和试探。
B5 1 1 1 1 B2 B3 B1 1 1 T

52 三.形式微商文法 形式微商定义：集合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+={λ}

53 已知正取样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

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

55 四.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

56 ②求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

57 状态图 讨论：推断k－尾文法时， k尾的选择很重要， k小时文 法简单，但循环产生式增多，这样就可以导出更多的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

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

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

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

61 ①先由树干推出树干文法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

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

63 §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 类。 框图如下：

64 X∈L{G1} G1 x X∈L{G2} X∈ωi 判决 待识别句子 识别结果 G2 …… X∈L{GM} GM 句法分析过程

65 二句法分析的主要方法 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∈Xi X∈ωi x X∈样本链码X2 X∈L{G2} 判决 …… X∈样本链码XN

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

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

68 ⑴由顶向底(由上而下)剖析 例：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 ⑦

69 ⑵由底向顶(由下而上)剖析 例：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

70 ⑥用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

71 三、杨格(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标准形式。此形式文法的代换式只有两种形式，即 非终止符→非终止符•非终止符（双非终止符形式） 非终止符→终止符（终止符形式）

72 将式上所示文法中第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的子串即原 符号串）。

73 这21个符号串都可由正整数i, j表示。i代表子串中符号的 个数（即子串长度），而j表示这子串的首位在原符号串 中占第几位。如上面所举的第1子串“2”，即为i=1、j=1的 子串，第13个子串021即是i=3、j=2的子串。可见，任一 子串都可用i, j二数来指明。 ⑶ 识别表的建立，关键问题是根据给出的待识别串X,建 立一识别表。对于202102,根据所给出的文法算得的识别 表如下：

74 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 • √

75 表中每一位置由三个符号表示。头二个即i和j，而第三个 是非终止符(现为S,A,B,见表中第一列)
表中每一位置由三个符号表示。头二个即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符合给出的文法。反之，即 判不符合此文法。

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

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

78 作业：对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法的例题编程上机，打出识别表。

79 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 i 剖析表

80 例：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 i

81 ③ 第二次迭代，令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 ↓ ↓ ↓ ↓ i a a b b 剖析表

82 作业：对CYK算法的例题上机编程，打出剖析表和导出树。

83 当给出某类文法后，可根据它设计一种相应的称为自动机 的硬件模型。它由控制装置、输入带和某些类型的存储器
§7-4 自动机理论 引言： x 当给出某类文法后，可根据它设计一种相应的称为自动机 的硬件模型。它由控制装置、输入带和某些类型的存储器 组成，这种硬件模型是一种识别器称自动机。不同的自动 机可以识别不同的文法形成的语言。 0型文法：图灵机识别 上下文有关型：线性约束自动机 上下文无关型：下推自动机 有限状态型：有限状态自动机 X∈L{G} 识别器 G

84 一、有限状态自动机 可以识别由有限状态文法所构成的语言 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

85 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

86 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

87 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

88 状态转换图 输入字串：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

89 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

90 例：有限状态文法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)＝ Φ

91 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

92 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

93 ①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,

94 ∴有限状态文法为： 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

95 由自动机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 有限自动机 有限状态文法

96

97 A接受链x的过程为：

98 2）按有限态自动机确定正则文法 对应关系：

99 若将qi，qj分别命名为Ai，Aj：

100

101 下推自动机与上下文无关文法 1．下推自动机 有限态自动机的限制： 只能接受正则文法产生的语言， 不能接受上下文无关文法产生的语言。 下推自动机(PDA)：有限态自动机+下推存储器 可识别上下文无关文法产生的句子。

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

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

104 输入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

105 例：确定自动机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 λ

106 ⑶ 由上、下文无关文法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, λ )

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

108 由规则Ⅱ对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 → → → →

109 例： 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, λ)

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

111 三、图灵机：可以识别0型文法所产生的语言 1、结构 2、定义：一个图灵机T是一个六元式 T = (∑, Q, Г ,δ,q0, F ) 其中： Q：状态集合 Г＝ ∑＋B, B空 ∑= Г- B, q0起始状态，q0 ∈Q F:终止状态 控制装置 读写头 输入带

112 图灵机是最复杂的自动机。它的一个构型用三元式（q, α, i） 表示q ∈Q, α∈(Г- B)
图灵机是最复杂的自动机。它的一个构型用三元式（q, α, i） 表示q ∈Q, α∈(Г- B)* 映射δ的使用 δ(q,Ai)=(P,X,R)在Ai处插入X后右移 δ(q,Ai)=(P,X,L)在Ai处插入X后左移 3、图灵机T所接受的语言

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

114 输入：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被接受 ↓ ① ↓ ② ↓ ⑩ ↓ ↓ ↓ ⑨ ⑾ ① ↓ ↓ ↓ ③ ⑥ ⑩ ↓ ⑦ ④ ↓ ④ ↓ ↓ ⑧

115 §7-5 误差校正句法分析 一、解决噪声干扰的方法 ①推断文法时，考虑噪声干扰的样本 ②在预处理中，除掉噪声，平滑处理 ③用随机文法,采用概率的概念，给句子的出现加上概率的分布 ④用转换文法，把有噪声句子转换为无噪声句子 ⑤用误差校正剖析句法集群法

116 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

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

118 例：有随机文法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)出现的概率 (101)n11 0.2ⅹ(0.7ⅹ0.8)n (101)n ⅹ(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

119 ⑵用随机文法作识别 ①用大量的样本去推断随机文法，每个随机文法代表一类 ②检查待识别的样本符合哪一个随机文法，就把它归于该 随机文法所代表的一类 ③若待识别的样本符合二个以上的随机文法 再求待识别样本对每一类的出现概率，把待识别样本归 于出现概率最大的一类。

120 例：关于“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 基元

121 P形式：⑴S→0A ⑵A→0B ⑶B→5C ⑷C→5D ⑸D→5E ⑹D→5 ⑺E→5 ⑻A→5F ⑼F→5H ⑽H→5I ⑾I→5
I A 5 状态图 B 5 E 5 C D T 5 5 5

122 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 000555 00555 5 6 基元 P3=0.8 P6=0.375 P8=0.625 P9=0.2

123 状态图 设待识别链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 ① ② ⑨ ⑩ ⑾ ① ② ③ ④ ⑥

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

125 再用每一个训练样本的出现概率求产生概率 P1P2P3P4P5P6P7=0. 3 ——X1=0005555 P1P2P3P4P5P8=0
再用每一个训练样本的出现概率求产生概率 P1P2P3P4P5P6P7=0.3 ——X1= P1P2P3P4P5P8=0.5 ——X2= 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 用同样的方法可求出其它产生概率

126 输出：要求把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为门限

127 ③对新的取样重复第二步，最后获得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

128 四、最小距离法 ⑴ 对句法模式的度量 ①两个模式间的距离 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。 可写成如下形式：

129 ⑵最小距离句法识别 ①二类问题：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)