<4D F736F F F696E74202D20D7D4C8BBD3EFD1D4C0EDBDE2A3A83033A3A9D0CECABDD3EFD1D4D3EBD7D4B6AFBBFA2E707074>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D20D7D4C8BBD3EFD1D4C0EDBDE2A3A83033A3A9D0CECABDD3EFD1D4D3EBD7D4B6AFBBFA2E707074>"

锅央顾
5 years ago
Views:

1 第 3 章形式语言与自动机及其在 NLP 中的应用 No.95, Zhongguancun East Road Beijing , China Tel. No.:

2 3.1 几个基本概念

3 3.1 几个基本概念树 (tree): 一个连通的无回路的无向图称为树 ( 或称自由树 ) 如果树中有一个结点被特别地标记, 则这棵树被称之为根树, 这个被特别标记的结点被称之为根结点

4 3.1 几个基本概念 A C A 根结点 B D E B C 中间 ( 内 ) 结点叶结点 D E 父结点 : A 是 B C 结点的父结点 ;C 是 D E 结点的父结点子结点 :B C 是 A 结点的子结点 ;D E 是 C 结点的子结点兄弟结点 :B C 互为兄弟结点 ; D E 互为兄弟结点

5 3.1 几个基本概念字符串 (string) 字符串定义 : 假定 Σ 是字符的有限集合, 它的每一个元素称之为字符由 Σ 中字符相连而成的有限序列被称之为 Σ 上的字符串 ( 或称符号串, 或称链 ) 特殊地, 不包括任何字符的字符串称为空串, 记作 ε 符号串的长度 : 符号串中符号的个数符号串 x 的长度用 x 表示 ε = 0 包括空串的 Σ 上字符串的全体记为 Σ*

6 3.1 几个基本概念字符串操作假定 Σ 是字符的有限集合,x, y 是 Σ 上的符号串 (1) 字符串连接 : 则把 y 的各个符号写在 x 的符号之后得到的符号串称为 x 与 y 的连接, 记作 xy 例如 : Σ={a, b, c}, x=ab, y=cba 那么,xy=abcba

7 3.1 几个基本概念设 x 是符号串, 把 x 自身连接 n 次得到的符号串, 即 z=xx x (n 个 x), 称为 x 的 n 次方幂, 记作 x n 注意 :x 0 = ε x n =xx n-1 =x n-1 x (n 1) x*=x n (n 0), x + = x n (n 1) 例如 : 如果 x=a, 则 x 1 =a, x 2 =aa, x 3 =aaa, 如果 x=ab, 则 x 0 = ε, x 3 =ababab

8 3.1 几个基本概念 (2) 符号串集合的乘积设 A, B 是符号串的集合, 则 A, B 的乘积定义为 : AB = { xy x A, y B} 相应地,A 0 = {ε}, A n =A n-1 A=AA n-1 例如 : 设 A={aa, bb}, B={cc, dd, ee}, 则 AB={aacc, aadd, aaee, bbcc, bbdd, bbee} A 2 ={aaaa, aabb, bbaa, bbbb}

9 3.1 几个基本概念 (3) 闭包如果 V 是字符表 Σ 上的字符串集合, 那么,V 的闭包定义为 :V* = V 0 V 1 V 2 V + = V 1 V 2 ( 称为 V 的正闭包 ) V + = V* - {ε} 例如 :V = {a, b} V* = {ε, a, b, aa, ab, bb, ba, aaa, } V + = {a, b, aa, ab, ba, bb, aaa, }

10 3.1 几个基本概念正则表达式 ( 简称正则式 ): 正则式对应于 Σ 上的一些子集 ( 正则集 ), 并通过递归定义 : 1) 空集 φ 和空字符串 ε 是正则式, 它们的正则集分别为 φ 和 {ε} 2) 任何 x Σ, x 是正则式, 它对应的正则集是 {x} 3) 如果 X, Y 是 Σ 上的正则式, 并且它们对应的正则集分别为 U, V, 那么,X Y, X Y 和 X * 也是正则式, 且它们对应的正则集分别为 U V, U V 和 U *

11 3.1 几个基本概念例如 : 假设 Σ = {0, 1}, 那么,0 和 1 都是正则表达式如果令 x=0, y=1, 那么, y* = 1* 也是正则式, 对应的正则集为 : U={ε, 1, 11, } xy* = 01* 也是正则式, 且它对应的正则集 : V={ 0, 01, 011, 0111, } x y* = {x} U = {0, ε, 1, 11, 111, }

12 3.1 几个基本概念正则表达式与有限状态图正则表达式可以用有向图表示, 图的结点是状态, 有一个起始结点和一个终止结点起始结点只有出边, 终止结点用双圆圈表示边上的符号表示从一个状态到另一个状态结点允许出现的字符, 这种图称之为有限状态图正则式 01* 对应的有限状态图为 : 0 1

13 3.1 几个基本概念栈 (stack) 栈是一种线性表,A = A 0, A 1,, A k. A 0 是栈底, A k 是栈顶, 当栈为空时,A 0 既是栈顶也是栈底 A k Top A 2 A 1 A 0 Last in, first out. Bottom

14 3.2 形式语言

15 3.2 形式语言关于语言的定义按照一定规律构成的句子和符号串的有限或无限的集合 - Chomsky 语言可以被看成一个抽象的数学系统 - 吴蔚天 (1994)

16 3.2 形式语言语言描述的三种途径穷举法只适合句子数目有效的语言语法描述生成语言中合格的句子自动机对输入的句子进行检验, 区别哪些是语言中的句子, 哪些不是语言中的句子

17 3.2 形式语言形式语言的直观意义形式语言是用来精确地描述语言 ( 包括人工语言和自然语言 ) 及其结构的手段形式语言学也称代数语言学以重写规则 α β 的形式表示, 其中, α,β 均为字符串顾名思义 : 字符串 α 可以被改写成 β 一个初步的字符串通过不断地运用重写规则, 就可以得到另一个字符串通过选择不同的规则并以不同的顺序来运用这些规则, 就可以得到不同的新字符串

18 3.2 形式语言形式语法的定义形式语法是一个 4 元组 G=(N, Σ, P, S), 其中 N 是非终结符的有限集合 ( 有时也叫变量集或句法种类集 ); Σ 是终结符的有限集合,N Σ=Φ;V=N Σ 称总词汇表 ;P 是一组重写规则的有限集合 :P={ α β }, 其中,α,β 是 V 中元素构成的串, 但 α 中至少应含有一个非终结符号 ;S N, 称为句子符或初始符例如 :G = ({A, S}, {0, 1}, P, S) P: S 0 A 1 0 A 00A1 A 1

19 3.2 形式语言推导的定义设 G=(N, Σ, P, S) 是一个文法, 在 (N Σ)* 上定义关系 ( 直接派生或推导 ) 如下 : G 如果 αβγ 是 (N Σ)* 中的符号串, 且 β δ 是 P 的产生式, 那么 αβγ αδγ G

20 3.2 形式语言 + G 用 ( 按非平凡方式派生 ) 表示的传 G 递闭包, 也就是 (N Σ)* 上的符号串 ξ i 到 ξ i+1 的 n ( n 1) 步推导或派生用 ( 派生 ) 表示的自反和传递闭 G G 包, 即由 (N Σ )* 上的符号串 ξ i 到 ξ i+1 经过 n ( n 0) 步推导或派生如果清楚某个推导是文法 G 所产生的, 则 + 符号或中的 G 可以省略不写 G G

21 3.2 形式语言最左推导最右推导和规范推导约定每步推导中只改写最左边的那个非终结符, 这种推导称为最左推导约定每步推导中只改写最右边的那个非终结符, 这种推导称为最右推导最右推导也称规范推导

22 3.2 形式语言例 3.1:G = ({E, T, F}, {a, +, *, (, )}, P, E) P: E E + T T T T*F F F (E) a 字符串 a+a*a 的两种推导过程 : E E+T T+T F+T a+t a+t*f a+f*f a+a*f a+a*a ( 最左推导 ) E E+T E+T*F E+T*a E+F*a E+a*a T +a*a F + a*a a + a*a ( 最右推导 )

23 3.2 形式语言句型与句子一些特殊类型的符号串为文法 G=(N, Σ, P, S) 的句子形式 ( 句型 ): (1) S 是一个句子形式 ; (2) 如果 αβγ 是一个句子形式, 且 β δ 是 P 的产生式, 则 αδγ 也是一个句子形式 ; 文法 G 的不含非终结符的句子形式称为 G 生成的句子由文法 G 生成的语言, 记作 L(G), 指 G 生成的所有句子的集合即 :L(G)={x x Σ, S x} G

24 3.2 形式语言正则文法如果文法 G=(N, Σ, P, S) 的 P 中的规则满足如下形式 :A B x, 或 A x, 其中 A, B N, x Σ, 则称该文法为正则文法或称 3 型文法 ( 左线性正则文法 ) 如果 A x B, 则该文法称为右线性正则文法

25 3.2 形式语言例 3.2:G = (N, Σ, P, S), N = {S, A, B}, Σ = {a, b}, P: (a) S a A (b) A a A (c) A b b B (e) B b A b B B b B L(G) =?{a n b m }, n 1, m 3 (d) B b B

26 3.2 形式语言上下文无关文法 (CFG, context-free grammar) 如果 P 中的规则满足如下形式 :A α, 其中 A N,α (N Σ)*, 则称该文法为上下文无关文法 (CFG) 或称 2 型文法

27 3.2 形式语言例 3.3: G = (N, Σ, P, S), N = {S, A, B, C}, Σ = {a, b, c}, P: (a) S A B C (b) A a A a (c) B b B b (d) C B A c L(G) =?{a n b m a k c α }, n 1, m 1, k 0, α {0, 1}

28 3.2 形式语言上下文有关文法 (CSG, context-sensitive grammar) 如果 P 中的规则满足如下形式 : α A β αγβ, 其中 A N,α, β, γ (N Σ)*, 且 γ 至少包含一个字符, 则称该文法为上下文有关文法 (CSG) 或称 1 型文法另一种定义 :if x y, x (N Σ) +, y (N Σ)*, and y x

29 3.2 形式语言例 3.4: G = (N, Σ, P, S) N = {S, A, B, C}, Σ = {a, b, c}, P: (a) S A B C (b) A a A a (c) B b B b (d) B C B c c L(G) =?{a n b m c 2 }, n 1, m 1

30 3.2 形式语言无约束文法 ( 无限制重写系统 ) 如果 P 中的规则满足如下形式 : α β, α, β 是字符串, 则称 G 为无约束文法, 或称 0 型文法

31 3.2 形式语言显然, 每一个正则文法都是上下文无关文法, 每一个上下无关文法都是上下文有关文法, 而每一个上下文有关文法都是 0 型文法, 即 : L(G0) L(G1) L(G2) L(G3)

32 3.2 形式语言语言与文法类型的约定如果一种语言能由几种文法所产生, 则把这种语言称为在这几种文法中受限制最多的那种文法所产生的语言例 3.5:G = ({S, A, B}, {a, b}, P, S) P: S ab S ba A as A baa A a B bs B abb B b G 为上下文无关文法 L(G) = { 等数量的 a 和 b 构成的链 }

33 3.2 形式语言 CFG 产生的语言句子的派生树表示 CFG G=(N, Σ, P, S) 产生一个句子的派生树由如下步骤构成 : (1) 对于 x N Σ 给一个标记作为节点, S 作为树的根节点 (2) 如果一个节点的标记为 A, 并且它至少有一个除它自身以外的后裔, 则 A N

34 3.2 形式语言 (3) 如果一个节点的标记为 A, 它的 k ( k > 0) 个直接后裔节点按从左到右的次序依次标记为 A 1, A 2,, A k, 则 A A 1, A 2,, A k 一定是 P 中的一个产生式

35 3.2 形式语言例如,G = ({S, A}, {a, b}, P, S) P: S ba A baa A a G 所产生的句子 bbaa 可以由下面的生树表示 : S S b A b A A b A A b a A A a A a

36 3.2 形式语言上下文无关文法的二义性一个文法 G, 如果存在某个句子有不只一棵分析树与之对应, 那么称这个文法是二义的

37 3.2 形式语言例 : G(E): E E + E E * E (E) E E i 对于句子 i + i * i 有两棵对应的分析树 E E i E E + * E E E E + * E E i i i i i

38 3.3 自动机

39 语言与识别器的对应关系识别器是有穷地表示无穷语言的另一种方法每一个语言的句子都能被一定的识别器所接受语言类型 0 型 1 型 2 型 3 型识别器类型图灵机线性带限自动机下推自动机有限自动机

40 3.3.1 有限自动机与正则文法

41 3.3.1 有限自动机与正则文法确定的有限自动机 (Definite Automata, DFA) 确定的有限自动机 M 是一个五元组 : M = (Σ, Q, δ, q 0, F) 其中,Σ 是输入符号的有穷集合 ; Q 是状态的有限集合 ;q 0 Q 是初始状态 ; F 是终止状态集合,F Q; δ 是 Q 与 Σ 的直积 Q Σ 到 Q ( 下一个状态 ) 的映射它支配着有限状态控制的行为, 有时也称为状态转移函数

42 3.3.1 有限自动机与正则文法 DFA 示意图有限控制器输入头输入带 a a b a b b a 处在状态 q Q 中的有限控制器从左到右依次从输入带上读入字符开始时有限控制器处在状态 q 0, 并注视 Σ * 中一个链的最左符号映射 δ(q, a)=q (q, q Q, a Σ) 表示在状态 q 时, 若输入符号为 a, 则自动机进入状态 q 并且将输入头向右移动一个字符

43 3.3.1 有限自动机与正则文法状态变换图映射 δ(q, a) = q 可以由状态变换图描述 q a q 为了明确起见, 终止状态用双圈表示, 起始状态用有开始标记的箭头表示如 : 开始 q 0 a q 1

44 3.3.1 有限自动机与正则文法 DFA 定义的语言如果一个句子 x 使得有限自动机 M 有 δ(q 0, x) = p, p F, 那么, 称句子 x 被 M 接受由 M 定义的语言 T(M) 就是被 M 接受的句子的全集即 : T(M) = { x δ(q 0, x) F }

45 3.3.1 有限自动机与正则文法 DFA 定义的语言例 3.6: 开始 1 q 0 q 链 x = 被 M 接受. q 2 1 q 3 T(M) = { 含偶数个 0 和偶数个 1 的链 }

46 3.3.1 有限自动机与正则文法不确定的有限自动机 (Non-definite Automata, NFA) 不确定的有限自动机 M 是一个五元组 M = (Σ, Q, δ, q 0, F) 其中,Σ 是输入符号的有穷集合 ; Q 是状态的有限集合 ; q 0 Q 是初始状态 ; F 是终止状态集合,F Q; δ 是 Q 与 Σ 的直积 Q Σ 到 Q 的幂集 2 Q 的映射

47 3.3.1 有限自动机与正则文法 NFA 与 DFA 的区别 NFA 与 DFA 的唯一区别是 : 在 NFA 中 δ(q, a) 是一个状态集合, 而在 DFA 中 δ(q, a) 是一个状态例 3.7: 0,1 开始 0,1 q 0 1 q 1 1 q q 3 q 4 0,1 该自动机为不确定自动机 ; 句子 x =01011 可以被接受

48 3.3.1 有限自动机与正则文法 NFA 与 DFA 的关系定理 3.1: 设 L 是一个被 NFA 所接受的句子的集合, 则存在一个 DFA, 它能够接受 L ( 证明略, 数学归纳法 ) 说明 : 由于 DFA 与 NFA 所接受的是同样的链集, 所以一般情况下无需区分它们, 二者统称为有限自动机 (Finite Automata, FA)

49 3.3.1 有限自动机与正则文法正则文法与有限自动机的关系定理 3.2: 若 G = (V N,V T, P, S ) 是一个正则文法, 则存在一个有限自动机 M=(Σ, Q, δ, q 0, F), 使得 :T(M) = L(G)

50 3.3.1 有限自动机与正则文法由 G 构造 M 的一般步骤 : (1) 令 Σ =V T, Q=V N { T },q 0 =S, 其中, T 是一个新增加的非终结符 (2) 如果在 P 中有产生式 S ε, 则 F={S, T}, 否则 F={T} (3) 如果在 P 中有产生式 B a, B V N, a V T, 则 T δ(b, a)

51 3.3.1 有限自动机与正则文法 (4) 如果在 P 中有产生式 B ac,b, C V N, a V T, 则 C δ(b, a) (5) 对于每一个 a V T, 有 δ(t, a) = φ 例 3.8: 给定正则文法 G =(V N, V T, P, S ), 其中, V N ={S, B}, V T ={a, b}, P={S ab, B bs ab a} 构造与 G 等价的 NFA

52 3.3.1 有限自动机与正则文法 (1) 设 NFA M=(Σ, Q, δ, q 0, F), 根据上述步骤有 : Σ=V T ={a, b},q=v N { T }={S, B, T},q 0 =S, F={ T } (2) 映射 δ 为 :δ(s, a)={b} ( 因为有规则 S ab ) δ(s, b) = φ δ(b, a) = {B, T} ( 因为有 B ab, B a) δ(b, b) = {S} ( 因为有 B bs ) δ(t, a) = φ δ(t, b) = φ

53 3.3.1 有限自动机与正则文法等价的 NFA 的状态变换图为 : 开始 a a S B T b a

54 3.3.1 有限自动机与正则文法定理 3.2: 若 M= (Σ, Q, δ, q 0, F) 是一有限自动机, 则存在正则文法 G=(V N, V T, P, S) 使 L(G)=T(M) 由 M 构造 G 的一般步骤 : (1) 令 V N = Q,V T = Σ,S =q 0 ; (2) 如果 C δ(b, a),b, C Q,a Σ, 则在 P 中有产生式 B ac; (3) 如果 C δ(b, a),c F, 则在 P 中有产生式 B a

55 3.3.2 CFG 与下推自动机

56 3.3.2 CFG 与下推自动机下推自动机 (Push-Down Automata, PDA) PDA 可以看成是一个带有附加的下推存储器的有限自动机, 下推存储器是一个栈如下图所示 : c d d b b b 输入带只读头有限控制器 Z 0 Z 下推存储器读写头

57 3.3.2 CFG 与下推自动机 PDA 的定义一个不确定的 PDA 可以表达成一个 7 元组 : M = (Σ, Q, Γ, δ, q 0, Z 0, F) 其中,Σ 是输入符号的有穷集合 ; Q 是状态的有限集合 ; q 0 Q 是初始状态 ; Γ 为下推存储器符号的有穷集合 ; Z 0 Γ 为最初出现在下推存储器顶端的符号 ; F 是终止状态集合,F Q; δ 是从 Q (Σ {ε}) Γ 到 Q Γ * 子集的映射

58 3.3.2 CFG 与下推自动机映射关系 δ 的解释映射关系 δ(q, a, Z)={(q 1, γ 1 ), (q 2, γ 2 ),,(q m, γ m )} 其中, q 1, q 2,, q m Q, a Σ, Z Γ, γ 1, γ 2,,γ m Γ* 该映射的意思是 : 当 PDA 处于状态 q, 面临输入符号 a 时, 自动机将进入 q i, i = 1, 2,, m 状态, 并以 γ i 来代替下推存储器 ( 栈 ) 顶端符号 Z, 同时将输入头指向下一个字符当 Z 被 γ i 取代时,γ i 的符号按照从左到右的顺序依次从下向上推入到存储器

59 3.3.2 CFG 与下推自动机特殊情况下, 当 δ(q, ε, Z)={(q 1, γ 1 ), (q 2, γ 2 ),, (q m, γ m )} 时, 输入头位置不移动, 只用于处理下推存储器内部的操作, 叫作 ε 移动

60 3.3.2 CFG 与下推自动机符号约定设有序对如果 ( Γ * * q, γ ), q Q, γ, 对于 a ( { ε}), β Γ, Z Γ ( q', β ) δ ( q, a, Z), q', q Q, 则表达式 a: (q, Zγ) (q, βγ) M 表示根据下推自动机的状态变换规则, 输入 a 能使下推自动机 M 由格局 (q, Zγ) 变换到格局 (q, βγ), 或称 a: (q, Zγ) (q, βγ) M 为合法转移零次或多次合法转移记为 : a: (q, Zγ) * (q, βγ) M 可以省略不写 M

61 3.3.2 CFG 与下推自动机下推自动机接受的语言下推自动机 M 所接受的语言定义为 : * T(M) = {x x: (q 0, Z 0 ) M (q, γ), γ Γ*, q F } Definition 1: A PDA accepts its input by consuming it and entering an accepting state. Definition 2: The set of strings that cause the PDA to empty its stack, starting from the initial instantaneous description (ID).

62 3.3.2 CFG 与下推自动机例 3.9 下推自动机 M = (Σ, Q, Γ, δ, q 0, Z 0, F) 接受语言 L={wcw R w {a, b} * }, 其中,Q={0, 1}, Σ={a, b, c}, Γ = {A, B}, q 0 = 0, Z 0 = #, F = {1}, δ 定义如下 : (1) δ(0, a, ε) {(0, A)} (2) δ(0, b, A) {(0, AB)} M (3) δ(0, b, B) {(0, BB)} (4) δ(0, c, B) {(1, B)} M (5) δ(1, b, B) {(1, ε)} (6) δ(1, a, A) {(1, ε)} M M M M

63 3.3.2 CFG 与下推自动机对于输入 abbcbba 下推自动机 M 的处理步骤为 : 状态输入栈运用的规则 0 abbcbba # - 0 bbcbba A# δ(0, a, ε) {(0, A)} 0 bcbba BA# δ(0, b, A) {(0, AB)} 0 cbba BBA# δ(0, b, B) {(0, BB)} 1 bba BBA# δ(0, c, B) {(1, B)} 1 ba BA# δ(1, b, B) {(1, ε)} 1 a A# δ(1, b, B) {(1, ε)} 1 ε # δ(1, a, A) {(1, ε)}

64 3.3.3 图灵机和线性带限自动机

65 3.3.3 图灵机和线性带限自动机图灵机的理解有限控制器读 / 写头 a 1 a 2 a i a n B B 输入 / 输出带给定字符串 α 存放于输入 / 输出带上, 开始时图灵机 M 处于状态 q 0, 它的读 / 写头扫描着 α 的最左字符根据转移函数 δ 的定义, 即对于目前状态以及正扫描着的字符,M 改变当前状态读 / 写头扫描的字符, 以及读写 / 头的位置

66 3.3.3 图灵机和线性带限自动机图灵机与有限自动机的区别图灵机可以通过其读 / 写头改变输入带的字符

67 3.3.3 图灵机和线性带限自动机图灵机的定义一个图灵机 T 可以表达成一个 6 元组 : M = (Σ, Q, Γ, δ, q 0, F) 其中,Σ 是输入 / 输出带上字符的有穷集合 ; Q 是状态的有限集合 ;Γ=Σ {B}, B 为空白字符 ; q 0 Q 是初始状态 ;F 是终止状态集,F Q; δ 是从 Q Σ 到 Q Σ {R, L, S} 子集的映射 R, L, S 分别表示右移一格左移一格和停止不动

68 3.3.3 图灵机和线性带限自动机图灵机的解释图灵机 T 的一个格局可以定义为 (q, α, i), 其中,q Q, α 是字符串, 且 α Σ, i 是整数, 表示 T 的读 / 写头到 α 左端的距离图灵机 T 通过如下转移动作引起格局变化 : 假设 (q, A 1 A 2 A n, i), 1 i n+1 是当前 T 的格局, (1) 如果 δ (q, A i ) = (p, X, R), 1 i n, 那么,T 的基本运行 ( 即指定为 T 的基本移动 ) 可以表示为 : (q, A 1 A 2 A n, i) (p, A 1 A 2 A i-1 XA i+1 A n, i+1) T 即 T 的读 / 写头在 i 位置写入符号 X, 并将读 / 写头向右移动一个位置

69 3.3.3 图灵机和线性带限自动机 (2) 如果 δ (q, A i ) = (p, X, L), 2 i n, 那么, (q, A 1 A 2 A n, i) (p, A 1 A 2 A i-1 XA i+1 A n, i-1) 即 T 的读 / 写头在 i 位置写入符号 X, 并将读 / 写头向左移动一个位置, 但不超出输入带的左端 (3) 如果 i = n+1, 读写头超出原字符串的右端, 读到的是空白符号 B, 此时如果有 δ (q, B) = (p, X, R), 那么 (q, A 1 A 2 A n, n+1) (p, A 1 A 2 A n X, n+2) 而如果 δ (q, B) = (p, X, L), 则 : T T (q, A 1 A 2 A n, n+1) (p, A 1 A 2 A n X, n) T

70 3.3.3 图灵机和线性带限自动机图灵机接受的语言如果 T 的两个格局 X 和 Y 之间的基本移动 ( 包括不移动 ) 的次数是有限的, 且互相关联, 则可记为 : X * Y T 由图灵机 T 所接受的语言定义为 : L(T)={α α Σ *, (q 0, α, 1) * T (q, β, i), q F, β Γ * }

71 3.3.3 图灵机和线性带限自动机给定一个识别语言 L 的图灵机 T, 不失一般性, 我们假定每当输入串被接受时,T 就停机, 即没有下一个动作另一方面, 对于未接受的链,T 可能不停机定理 3.3 如果 L 是一个由 0 型文法产生的语言, 则 L 可被一个图灵机所接受定理 3.4 如果 L 可被一个图灵机所接受, 则 L 是一个由 0 型文法产生的语言

72 3.3.3 图灵机和线性带限自动机线性带限自动机线性带限自动机是一个确定的单带图灵机其读写头不能超越原输入带上字符串的初始和终止位置即线性带限自动机的存储空间被输入符号串的长度所限制

73 3.3.3 图灵机和线性带限自动机定义 : 一个线性带限自动机 M 可以表达成一个 6 元组 : M = (Σ, Q, Γ, δ, q 0, F) 其中,Σ 是输入 / 输出带上字符的有穷集合 ; Q 是状态的有限集合 ;q 0 Q 是初始状态 ; Γ 是输入带上符号的有穷集 ; F 是终止状态集合,F Q; δ 是从 Q Γ 到 Q Γ {R, L} 子集的映射 Σ 包括两个特殊符号 # 和 $, 分别表示输入链的左端和右端标志

74 3.3.3 图灵机和线性带限自动机线性带限自动机所接受的语言线性带限自动机 M 的格局, 以及两个格局之间的关系 M 的定义与图灵机的相同唯一不同的是对读写头位置的限制在线性带限自动机中, 对于读写头超出输入字符串长度范围时, 转移动作没有定义线性带限自动机 M 接受的语言 : L(M)={α α (Σ-{#, $}) *, (q 0, #α$, 1) * (q, β, i), q F, β Γ * } M

75 3.3.3 图灵机和线性带限自动机对于任何 q Q, A Γ, 如果映射 δ(q, A) 包含的成员不超过一个, 则线性带限自动机是确定的定理 3.5: 如果 L 是一个前后文有关语言, 则 L 由一个不确定的线性带限自动机所接受反之, 如果 L 被一个线性带限自动机所接受, 则 L 是一个前后文有关语言

76 3.3.4 各类自动机的区别与联系

77 3.3.4 各类自动机的区别与联系主要区别 : 各类自动机的主要区别是它们能够使用的信息存储空间的差异 : 有限状态自动机只能用状态来存储信息 ; 下推自动机除了可以用状态以外, 还可以用下推存储器 ( 栈 ); 线性带限自动机可以利用状态和输入 / 输出带本身因为输入 / 输出带没有先进后出的限制, 因此, 其功能大于栈 ; 而图灵机的存储空间没有任何限制

78 3.3.4 各类自动机的区别与联系识别语言的能力 : 有限自动机等价于正则文法 ; 下推自动机等价于上下文无关文法 ; 线性带限自动机等价于上下文有关文法, 图灵机等价于 0 型文法

79 3.4 有限自动机在 NLP 中的应用

80 3.4 有限自动机的应用有限自动机用于英语单词拼写检查 [Oflazer, 1996] 设 X 为拼写错误的字符串, 其长度为 m, Y 为 X 对应的正确的单词 ( 答案 ), 其长度为 n 则 X 和 Y 的编辑距离 ed(x[m], Y[n]) 为 : 从字符串 X 转换到 Y 需要的插入删除替换和交换两个相邻的基本单位 ( 字符 ) 的最小个数如 : ed (recoginze, recognize) = 1 ed (sailn, failing) = 3

81 3.4 有限自动机的应用假设 Z = z 1 z 2 z p 为字母表 A 上的 p 个字母构成的字符串,Z[j] 表示含有 j(j 1) 个字符的子串 X[m] 为拼写错误的字符串, 其长度为 m,y[n] 为与 X 串接近的字符串 ( 一个候选 ), 其长度为 n 则给定两个串 X 和 Y 的编辑距离 ed(x[m], Y[n]) 可以通过循环计算出从字符串 X 转换到 Y 需要进行插入删除替换和交换两个相邻的字符操作的最少次数

82 3.4 有限自动机的应用 (1) 如果 x i+1 = y j+1 ( 两个串的最后一个字母相同 ), 则 ed(x[i+1], Y[j+1]) = ed(x[i], Y[j]); (2) 如果 x i = y j+1, 并且 x i+1 = y j ( 最后两个字符需要交换位置 ), 则 ed(x[i+1], Y[j+1]) = 1+min{ed(X[i-1], Y[j-1]), X: a b Y: * * * * b a j i ed(x[i], Y[j+1]), ed(x[i+1], Y[j])}

83 3.4 有限自动机的应用 (3) 其它情况下, ed( X[ i + 1], Y[ j + 1]) = 1+ min{ ed( X[ i], Y[ j]), ed( X[ i], Y[ j + 1]), ed( X[ i + 1], Y[ j])} 其中, ed( X[0], Y[ j]) = j (0 j n) ed( X[ i], Y[0]) = i (0 i m) ed ( X[ 1], Y[ j]) = ed( X[ i], Y[ 1]) ( 边界约定 )

84 3.4 有限自动机的应用构造一个确定的有限状态机 R : R = ( Q, A, δ, q 0, F ) 其中,Q 表示状态集 ; A 表示输入字符集 ; δ : Q A Q q Q 0 Q F 为起始状态 ; 为终止状态集 ;

85 3.4 有限自动机的应用 * 如果 L A 表示有限状态机 R 接受的语言, 字母构成的所有合法单词都是有限状态机中的一条路径给定一个输入串, 对其进行检查的过程就是在给定阈值 t (t > 0) 的情况下, 寻找那些与输入串的编辑距离小于 t 的路径那么, 一个字符串 X [ m] L 能够被 R 识别的条件是存在非空集合 : C = { Y[ n] Y[ n] L and ed( X[ m], Y[ n]) t}

86 3.4 有限自动机的应用 q 0 a b m z 说明 : 蓝色节点表示终结节点, 下同对于某一字符串 X, 搜索与之编辑距离最短的单词 ( 路径 )

87 3.4 有限自动机的应用即 : cuted( X[ m], Y[ n]) = min{ ed( X[ i], Y[ n])} l i u 其中,l = max (1, n - t), u = min (m, n + t) 例如 :t = 2, X = reprter (m = 7), Y = repo (n = 4), 那么 : l = max {1, 4-2} = 2; u = min {7, 4+2} = 6 cuted (reprter, repo) = min {ed (re, repo) =2, ed (rep, repo) =1, ed (repr, repo) =1, ed (reprt, repo) =2, ed (reprte, repo) =3}=1

88 3.4 有限自动机的应用有限自动机用于英语单词形态分析 [Allen, 1995] 英语单词形态变化非常普遍, 例如 : eat: eats, eating, ate, eaten happy: happier, happiest seed?

89 3.4 有限自动机的应用说明 : 在实际应用中, 除了有限状态机以外, 还常常使用有限状态转换机 (finite state transducer, FST) 的概念粗略地讲, 有限状态转换机与有限自动机 ( 或有限状态机 ) 的区别在于 :FST 在完成状态转移的同时产生一个输出, 而 FA( 或 FSM) 只实现状态转移, 不产生任何输出

90 3.4 有限自动机的应用 h a p p y i : y ε : 识别单词 :happy, happier, happiest 可转换的形式 : happier happy + er happiest happy + est e 8 9 r s t

91 3.4 有限自动机的应用一般地, 具有相同的前缀或词根, 词缀不同的单词可以共用一个有限状态转移机, 共享其中的某些状态节点如 :tie, ties, trap, traps, try, tries, to, torch, torches, toss, tosses 等

92 3.4 有限自动机的应用有限自动机用于词性标注 [Roche, 1995] (a)the time flies like an arrow. (b)may I take a can? (c) 他其实人很好, 就是好喝酒词性 (part-of-speech) 消歧

93 3.4 有限自动机的应用以下介绍文献 [Roche, 1995] 描述的词性标注方法 : 在词性标注规则的基础上建立状态转换机, 由状态转换机实现词性消歧该方法包括如下 4 步 : (1) 将每一条消歧规则转换成相应的状态转换机 np/np vbd/vbn vbd vbn PREVTAG np 标记 x / y 表示在给定输入 x 的情况下, 产生输出 y

94 3.4 有限自动机的应用 (2) 将上一步得到的与每一条规则关联的状态转换机进行扩展变换, 使其成为可以对输入句子进行全局操作的转换机?/? 0 np/np vbn/vbd?/? 1 np/np 状态 i 发出的弧上的标记? 表示其它任何一个没有出现在状态 i 发出的所有弧上的字符

95 3.4 有限自动机的应用 (3) 将所有的状态转换机合并成一个 ( 需要参照转换机构造的规范操作方法, 略 ) (4) 把上一步得到的状态转换机转换成等价的确定性状态转换机在理论上, 并不是所有的非确定性转换机都可以转换成等价的确定性的转换机 ( 这也是转换机与自动机的区别之一 ), 但在本应用中状态转换机总是可以转换成确定性的

96 3.4 有限自动机的应用为了快速实现词典查找,E. Roche 等人对词典的存储也采用了确定的有限状态自动机的思想 -Directed Acyclic Graph (DAG) a d s nns ads bag nns nn, vb b i a g y nn, vb g e d vbd, vbn bagged vbn, vbd bayed vbn, vbd bids nns

97 3.4 有限自动机的应用除了前面提到的单词拼写检查词法分析词性标注等工作以外, 有限状态自动机还广泛地应用于句法分析短语识别机器翻译和语音识别等很多方面

98 本章小结几个基本概念树, 字符串, 字符串操作正则表达式, 有限状态图形式文法 4 种形式文法的定义和相互关系文法识别的语言 ( 推导 )

99 本章小结关于自动机 (Automata) 4 种自动机的定义和区别自动机识别语言的能力文法与自动机的关系有限自动机与状态转移机的应用英文单词拼写检查英文单词形态分析词性标注宗成庆 : 自然语言理解讲义

100 习题 3-1. 构造上下文无关文法用以产生 : (a) 有相同数目的 0 和 1 的所有 0, 1 符号串 (b) {a 1 a 2 a n a n a 2 a 1 a i {0,1}, 1 i n} 3-2. 有以下文法 :G = ({S,B,C},{a,b,c},P, S), 其中 : P: S asbc abc CB BC bb bb bc bc cc cc 求 L(G)=?

101 习题 3-3. 设文法 G 由如下规则定义 : S AB A Aa bb B a Sb 给出下列句子形式的派生树 : (1) baabaab (2) bbabb 3-4. 写一个程序模拟一个确定性的 PDA 3-5. 写一个程序以正则文法 G 作为输入, 构造 G 相应的有限自动机

102 Thanks 谢谢!

PowerPoint Presentation

PowerPoint Presentation 第 3 章形式语言与自动机及其在 NLP 中的应用北京市海淀区中关村东路 95 号邮编 :100190 电话 :+86-10-8254 4688 邮件 :cqzong@nlpr.ia.ac.cn 3.1 基本概念宗成庆 : 自然语言理解讲义, 第 3 章 2/106 3.1 基本概念树 (tree): 树是一种数据结构一个连通的无回路的无向图称为树 ( 或称自由树 ) 如果树中有一个结点被特别地标记,