UCAS - AI学院 - 自然语言处理专项课 - 第3讲 - 课程笔记_cfg派生树 示例

形式语言与自动机

形式语言

• 语言：
  • 一个抽象的数学系统
  • 按照一定规律构成的句子和符号串的有限或无限集合
• 语言描述的三种途径
  • 穷举法：只适合句子数目有限的语言
  • 语法描述：生成语言中“合格”的句子
  • 自动机：对输入的句子进行检验以区别是否为语言中的句子
• 形式语言：用于精确地描述语言及其结构的手段
  • 又称代数语言学
  • 重写规则表示形式$\alpha \to \beta$
  • 即字符串$\alpha$可以利用重写规则被改写成$\beta$
    • 使用不同的规则并以不同的顺序运用，可以得到不同的新字符串
• 形式语法：四元组$G=(N,\Sigma ,P,S)$
  • $N$：非终结符（变量）的有限集合
  • $\Sigma$：终结符（常数）的有限集合（二者的交集为空，且并集为总词汇表$V$）
  • $P$：一组重写规则的有限集合$P=\alpha \to \beta$
  • $S$：句子符或初始符
  • $\alpha$和$\beta$是$V$中元素构成的串，但$\alpha$中至少包含一个非终结符
• 推导：设$G=(N,\Sigma ,P,S)$是一个文法，在闭包$(N\cup \Sigma {)}^{\ast }$上定义关系${\Rightarrow }_G$如下（直接派生）：
  • 如果$\alpha \beta \gamma$是$(N\cup \Sigma {)}^{\ast }$中的符号串，且$\beta \to \delta$是$P$的产生式，那么$\alpha \beta \gamma {\Rightarrow }_G\alpha \delta \gamma$
  • ${\Rightarrow }_G^{+}$（按非平凡方式派生）表示${\Rightarrow }_G$的传递闭包，即$(N\cup \Sigma {)}^{\ast }$上，符号串${\xi }_i$到${\xi }_{i+1}$的$n$步（$n\ge 1$）推导（至少一步发生变化）
  • ${\Rightarrow }_G^{\ast }$（派生）表示${\Rightarrow }_G$的自反和传递闭包，即$(N\cup \Sigma {)}^{\ast }$上，符号串${\xi }_i$到${\xi }_{i+1}$的$n$步（$n\ge 0$）推导（可不发生任何推导或者空操作）
• 最左推导：每步推导中只改写最左非终结符
• 最右推导：每步推导中之改写最右非终结符
  • 最有推导又称规范推导
• 句型：一些特殊类型的符号串，为文法$G=(N,\Sigma ,P,S)$的句子形式（句型）：
  1. $S$是一个句子形式
  2. 如果$\alpha \beta \gamma$是一个句子形式，且$\beta \to \delta$是$P$的产生式，则$\alpha \delta \gamma$也是一个句子形式
• 句子：文法$G$的不含非终结符的句子形式称为$G$生成的句子
• 正则文法：
  • 如果文法$G$的$P$中的规则满足如下形式：
    • $A\to Bx$
    • $A\to x$
    • 其中$A,B$为非终结符，$x$为终结符
  • 称该文法为正则文法，或称3型文法（左线性正则文法）
  • 如果规则形式为$A\to xB$，则该文法称为右线性正则文法
• 由文法$G$生成的语言，记$L(G)$，指$G$生成的所有句子的集合： L ( G ) : { x ∣ x ∈ Σ , S ⇒ G + x } L(G) : \{ x | x \in \Sigma, S \Rightarrow_G^+ x \} L(G):{x∣x∈Σ,S⇒G+​x}
• 上下文无关文法：
  • 如果$P$中的规则满足如下形式：
    • $A\to \alpha$
    • 其中$A$为非终结符，$\alpha$为文法允许的任意字符串
  • 称该文法为上下文无关文法，或称2型文法
• 上下文有关文法：
  • 如果$P$中的规则满足如下形式：
    • $\alpha A\beta \to \alpha \gamma \beta$
    • $A$为非终结符，$\alpha ,\beta ,\gamma$均为文法允许的任意字符串
    • $\gamma$至少包含一个字符
  • 称该文法为上下文有关文法，或称1型文法
• 无约束文法：
  • 无限制重写系统
  • 规则满足如下形式：
    • $\alpha \to \beta$
  • 0型文法
• 语言的关系$L(G0)\supseteq L(G1)\supseteq L(G2)\supseteq L(G3)$
• 约定：认定受限最多的文法产生该语言
• CFG产生语言的派生树表示：
  1. 对$\forall x\in N\cup \Sigma$给一个标记作为节点，$S$为树的根节点
  2. 如果一个节点标记为$A$，并且至少有一个除它纵深以外的后裔，则$A\in N$
  3. 如果一个节点标记为$A$，其$k$个直接后裔节点按从左到右标记为$A_1,\dots ,A_k$，则$A\to A_1{A}_2\dots A_k$一定是$P$中的一个产生式
• CFG的二义性：
  • 一个文法$G$，如果存在某个句子不只一棵分析树与之对应，则称这个文法是二义的

有限自动机与正则文法

• 自动机
  • 有限自动机
    • 确定性有限自动机
    • 非确定性有限自动机
  • 下推自动机
  • 线性带限自动机（与1型文法等价）
  • 图灵机（与0型文法等价）
• 确定性有限自动机DFA：五元组$M=(\Sigma ,Q,\delta ,q_0,F)$
  • $\Sigma$，输入符号的有穷集合
  • $Q$，状态的有限集合
  • $q_0\in Q$，初始状态
  • $F$，终止状态集合，$F\subseteq Q$
  • $\delta$，$Q\times \Sigma \to Q$的映射，支配着有限状态控制的行为，亦称状态转移函数
• DFA定义的语言：
  • 如果一个句子$x$使得有限自动机$M$有：
    • $\delta (q_0,x)=p,p\in F$
  • 那么称句子$x$被$M$接受
  • 由$M$定义的语言$T(M)$就是被$M$接受的句子的全集
  • T ( M ) : { x ∣ δ ( q 0 , x ) ∈ F } T(M) : \{ x | \delta(q_0, x) \in F \} T(M):{x∣δ(q0​,x)∈F}
• 非确定性有限状态自动机NFA：五元组$M=(\Sigma ,Q,\delta ,q_0,F)$
  • $\Sigma$，输入符号的有穷集合
  • $Q$，状态的有限集合
  • $q_0\in Q$，初始状态
  • $F$，终止状态集合，$F\subseteq Q$
  • $\delta$，$Q\times \Sigma \to Q$的幂集$2^Q$的映射（转换不唯一，结果为状态集合）
  • DFA可以认为是NFA的一个特例
• NFA和DFA的联系
  • 设$L$是一个被NFA接受的句子的集合，则存在一个DFA，能够接受$L$
  • 由于接受同样的链集，一般情况下无需区分他们，统称FA
• 正则文法与有限自动机的关系
  • 如果文法$G$是一个正则文法，则存在一个FA$M$，使得$T(M)=L(G)$
  • 如果有一个FA$M$，则存在一个正则文法$G$，使得$L(G)=T(M)$
• 由$G$构造$M$：
  1. 令$\Sigma =V_T$， Q = V N ∪ { T } Q = V_N \cup \{ T \} Q=VN​∪{T}，$q_0=S$，$T$是一个新增加的非终结符
  2. 如果在$P$中有产生式$S\to ϵ$，则 F = { S , T } F = \{S, T\} F={S,T}，否则 F = { T } F = \{ T \} F={T}
  3. 如果在$P$中有产生式$B\to a$，$B\in V_N$，$a\in V_T$，则$T\in \delta (B,a)$
  4. 如果在$P$中有产生式$B\to aC$，$B,C\in V_N$，$a\in V_T$，则$C\in \delta (B,a)$
  5. 对于每一个$a\in V_T$，有$\delta (T,a)=\varnothing$
• 由$M$构造$G$：
  1. 令$V_N=Q$，$V_T=\Sigma$，$S=q_0$
  2. 如果有$C\in \delta (B,a),B,C\in Q,a\in \Sigma$，则在$P$中有产生式$B\to aC$
  3. 如果$C\in \delta (B,a),C\in F$，则在$P$中有产生式$B\to a$

下推自动机与CFG

• 下推自动机PDA：
  • 可以看成是一个带有附加的下推存储器的有限自动机
  • 下推存储器是一个栈
• PDA定义：七元组$M=(\Sigma ,Q,\Gamma ,\delta ,q_0,Z_0,F)$
  • $\Sigma$，输入符号的有穷集合
  • $Q$， 状态的有穷集合
  • $\Gamma$，下推存储器符号的有穷集合
  • $Z_0\in \Gamma$，最初出现在下推存储器顶端的符号
  • $F$，终止状态集合
  • $\delta$，从 Q × ( Σ ∪ { ϵ } ) × Γ Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma Q×(Σ∪{ϵ})×Γ到$Q\times {\Gamma }^{\ast }$子集的映射
  • $q_0\in Q$， 初始状态
• 状态转移时， δ ( q , a , Z ) = { ( q 1 , γ 1 ) . … , ( q m , γ m ) } \delta(q, a, Z) = \{(q_1, \gamma_1). \ldots, (q_m, \gamma_m)\} δ(q,a,Z)={(q1​,γ1​).…,(qm​,γm​)}，下推存储器中的$Z$将被${\gamma }_i$取代，后者的符号按照从左到右的顺序逐个压入栈中，读取下一个输入
• 特殊情况 δ ( q , ϵ , Z ) = { ( q 1 , γ 1 ) . … , ( q m , γ m ) } \delta(q, \epsilon, Z) = \{(q_1, \gamma_1). \ldots, (q_m, \gamma_m)\} δ(q,ϵ,Z)={(q1​,γ1​).…,(qm​,γm​)}，不向下读取新输入，只进行下推存储器内部的操作，称之为$ϵ$移动
• 合法转移：$a:(q,Z\gamma ){⊢}_M(q^{\prime },\beta \gamma )$
• 下推自动机接受的语言： T ( M ) = { x ∣ x : ( q 0 , Z 0 ) ⊢ M ∗ ( q , γ ) , γ ∈ Γ ∗ , q ∈ F } T(M) = \{ x | x : (q_0, Z_0) \vdash_M^\ast (q, \gamma), \gamma \in \Gamma^\ast, q \in F \} T(M)={x∣x:(q0​,Z0​)⊢M∗​(q,γ),γ∈Γ∗,q∈F}
  • 输入串，并且到达接受终止状态
• PDA与CFG的关系
  • 对一个CFG$G$，可以构造一个PDA$M$，使得$T(M)=L(G)$
  • 对一个PDA$M$，可以构造一个CFG$G$，使得$L(G)=T(M)$
• 各类自动机的区别
  • 能够使用信息存储空间的差异
  • FA：只能用状态
  • PDA：还能用下推存储器
  • LCA：可以用输入/输出带本身
  • TA：没有任何限制

FA在NLP中的应用

英语单词拼写检查

• 编辑距离：错误单词$X$，长度为$m$；正确单词$Y$，长度为$n$，二者的编辑距离为$X$转换到$Y$需要的插入、删除、替换、交换两个相邻基本单位的最小个数
• 键树搜索范围：N-T到N+T，T为编辑距离阈值
• 为了找到所有的可能，子串可以不从头取
• 路径寻找：深度优先搜索，寻找符合条件的候选中距离满足要求的

有限自动机用于英语单词形态分析

• 有限状态转换机：在进行状态转移的过程中还会产生一个输出