最容易做的网站类型,七牛云做wordpress图床,汕头网站制作公司价格,网站怎么做外部链接文章目录1形式语言1.2形式语言3推导3.1句型、句子、语言3.2文法3.3派生树与二义性4有限自动机和正则文法4.1确定的有限自动机DFA4.2不确定的有限自动机NFA4.3有限自动机正则文法5.下推自动机PDA和上下文无关文法CFG5.1PDA5.1.1 PDA的例子.5.2 其他自动机5.2.1 区别6. 有…
文章目录1形式语言1.2形式语言3推导3.1句型、句子、语言3.2文法3.3派生树与二义性4有限自动机和正则文法4.1确定的有限自动机DFA4.2不确定的有限自动机NFA4.3有限自动机正则文法5.下推自动机PDA和上下文无关文法CFG5.1PDA5.1.1 PDA的例子.5.2 其他自动机5.2.1 区别6. 有限自动机在nlp中的应用6.1 英语单词拼写检查6.1.1 编辑距离6.1.2 有限状态机6.1.3 深度优先搜索找路径5.2 英语单词形态分析FA的变种6.作业3.13.23.33.43.53.61形式语言
语言人类所特有的用来表达意思、交流思想的工具是一种特殊的社会现象由语音、词汇和语法构成一定的系统。语言描述的三种途径 穷举法 — 只适合句子数目有限的语言。语法描述 — 生成语言中合格的句子。自动机 — 对输入的句子进行检验区别哪些是语言中的句子哪些不是语言中的句子 形式语言是用来精确地描述语言包括人工语言和自然语言及其结构的手段。形式语言学 也称 代数语言学 以重写规则 α→β\alpha\rightarrow\betaα→β的形式表示其中 α,β\alpha,\betaα,β 均为字符串。顾名思义字符串 α\alphaα 可以被改写成 β\betaβ 。一个初步的字符串通过不断地运用重写规则就可以得到另一个字符串。通过选择不同的规则并以不同的顺序来运用这些规则就可以得到不同的新字符串。
1.2形式语言
形式语法四元组G(N、Σ,P,S)G(N、\Sigma,P,S)G(N、Σ,P,S) N非终结符号变量Σ\SigmaΣ 终结符号N∩Σ∅;VN∪Σ:词汇表N \cap \Sigma\emptyset;\\VN\cup\Sigma:词汇表N∩Σ∅;VN∪Σ:词汇表P一组重写规则的有限集合P{α→β},其中αβ是V中元素构成的串但α至少有一个非终结符号S∈N(初始符或句子符号P\{\alpha\rightarrow\beta\},其中\alpha\beta是V中元素构成的串但\alpha至少有一个非终结符号S\in N(初始符或句子符号P{α→β},其中αβ是V中元素构成的串但α至少有一个非终结符号S∈N(初始符或句子符号eg:G({ A,S},{0,1},P,S)P:S→0A1,0A→00A1,A→1P:S\rightarrow0 A 1,\\0 A\rightarrow00A1,\\A\rightarrow1P:S→0A1,0A→00A1,A→1
3推导 推导 设G(N、Σ,P,S)G(N、\Sigma,P,S)G(N、Σ,P,S)施一个文法在(N∪Σ)∗(N\cup\Sigma)^*(N∪Σ)∗上定义关系G(直接派生或推导\stackrel{G}{}(直接派生或推导G(直接派生或推导*推导n1推导n0推导n1 最左推导 最右推导规范推导
3.1句型、句子、语言
句型与句子 一些特殊类型的符号串G(N、Σ,P,S)G(N、\Sigma,P,S)G(N、Σ,P,S)的句子形式句型 S是一个句子形式句型推出的也是一个句型 αβγ是一个句型且有β→δ是p的产生式则αδγ也是一个句型\alpha\beta\gamma是一个句型\\且有\beta\rightarrow\delta是p的产生式\\则\alpha\delta\gamma也是一个句型αβγ是一个句型且有β→δ是p的产生式则αδγ也是一个句型 句子不含有非终结符的句型语言L(G),G产生的所有句子
3.2文法
0型文法无限制重写系统无约束文法P:α→β,字符串P:\alpha\rightarrow\beta,字符串P:α→β,字符串理论上的无用处1型文法上下文有关文法CSG):P:αAβ→αγβA∈N,α,γ,β∈(N∪Σ)∗,且γ至少包含一个字符另一种定义ifx→y,x∈(N∪Σ),y∈(N∪Σ)∗,并且∣y∣≥∣x∣(越推越长P:\alpha A\beta\rightarrow \alpha \gamma \beta\\A\in N,\alpha, \gamma ,\beta\in(N\cup \Sigma)^*,且\gamma至少包含一个字符\\另一种定义if x\rightarrow y,x\in(N\cup \Sigma)^,y\in(N\cup \Sigma)^*,并且|y|\geq|x|(越推越长P:αAβ→αγβA∈N,α,γ,β∈(N∪Σ)∗,且γ至少包含一个字符另一种定义ifx→y,x∈(N∪Σ),y∈(N∪Σ)∗,并且∣y∣≥∣x∣(越推越长2型文法上下文无关文法CFGP:A→α,A∈N,α∈(N∪Σ)∗P:A\rightarrow \alpha,A\in N,\alpha\in(N\cup \Sigma)^*P:A→α,A∈N,α∈(N∪Σ)∗3型文法正则文法P:A→Bx∣A→x,A,B∈Nx∈Σ(左线性正则文法A→xB(右线性正则文法P:A\rightarrow Bx|A\rightarrow x,A,B\in Nx\in \Sigma(左线性正则文法\\A\rightarrow xB(右线性正则文法P:A→Bx∣A→x,A,B∈Nx∈Σ(左线性正则文法A→xB(右线性正则文法0-3,约束越来越大L(G3)⊆L(G2)⊆L(G1)⊆L(G0)L(G3)\subseteq L(G2)\subseteq L(G1)\subseteq L(G0)L(G3)⊆L(G2)⊆L(G1)⊆L(G0) 显然每一个正则文法都是上下文无关文法每一个上下无关文法都是上下文有关文法而每一个上下文有关文法都是0型文法 判别文法类别时倾向于判别为约束最大的 如果一种语言能由几种文法所产生则把这种语言称为在这几种文法中受限制最多的那种文法所产生的语言。
3.3派生树与二义性
2型文法上下文无关CFG 产生的语言句子的派生树表示CFGG(N、Σ,P,S)G(N、\Sigma,P,S)G(N、Σ,P,S)产生一个句子的派生树由如下 步骤构成 (1) 对于x∈N∪Σx\in N \cup \Sigmax∈N∪Σ 给一个标记作为节点, S 作为树的根节点。(2) 如果一个节点的标记为 A并且它至少有一个除它自身 以外的后裔则A∈NA\in NA∈N。(3) 如果一个节点的标记为 A它的 k ( k 0) 个直接后裔节 点按从左到右的次序依次标记为 A1, A2, …, Ak则 A - A1A2…Ak 一定是 P 中的一个产生式 上 下文无关文法的二义性 一个文法 G如果存在某个句子有不只一棵分析树与之对应那么称这个文法是二义的
4有限自动机和正则文法
4.1确定的有限自动机DFA
确定的有限自动机M是一个五元组M(Σ,Q,δ,q0,F)Σ:输入符号的有穷集合Q状态的有限集合q0∈Q:初始状态F终止状态集合F⊆Qδ:是Q×Σ到Q的映射它支配着有限状态控制的行为状态转移函数M(\Sigma,Q,\delta,q_0,F)\\ \Sigma:输入符号的有穷集合\\ Q状态的有限集合\\ q_0\in Q:初始状态\\ F终止状态集合F\subseteq Q\\ \delta:是Q×\Sigma到Q的映射它支配着有限状态控制的行为状态转移函数M(Σ,Q,δ,q0,F)Σ:输入符号的有穷集合Q状态的有限集合q0∈Q:初始状态F终止状态集合F⊆Qδ:是Q×Σ到Q的映射它支配着有限状态控制的行为状态转移函数从q0开始输入头开始在最左边输入aq′δ(q,a)从q转移到状态q′并将输入头向右移动一个字符从q_0开始输入头开始在最左边输入aq\delta(q,a)从q转移到状态q并将输入头向右移动一个字符从q0开始输入头开始在最左边输入aq′δ(q,a)从q转移到状态q′并将输入头向右移动一个字符状态变换图如下 DFA所定义的语言 可接受如果有一个句子x使得δ(q0,x)p,p∈F,则x可被M接受如果有一个句子x使得\delta(q_0,x)p,p\in F,则x可被M接受如果有一个句子x使得δ(q0,x)p,p∈F,则x可被M接受KaTeX parse error: Undefined control sequence: \inF at position 23: …x|\delta(q_0,x)\̲i̲n̲F̲\} 确定的接受一个输入只会从一个状态转换到另一个状态不会有其他可能
4.2不确定的有限自动机NFA
不确定的有限自动机M是一个五元组M(Σ,Q,δ,q0,F)Σ:输入符号的有穷集合Q状态的有限集合q0∈Q:初始状态F终止状态集合F⊆Qδ:是Q×Σ到Q的幂集2Q的映射状态转移函数M(\Sigma,Q,\delta,q_0,F)\\ \Sigma:输入符号的有穷集合\\ Q状态的有限集合\\ q_0\in Q:初始状态\\ F终止状态集合F\subseteq Q\\ \delta:是Q×\Sigma到Q的幂集2^Q的映射状态转移函数M(Σ,Q,δ,q0,F)Σ:输入符号的有穷集合Q状态的有限集合q0∈Q:初始状态F终止状态集合F⊆Qδ:是Q×Σ到Q的幂集2Q的映射状态转移函数–区别在这里区别 δ(q,a)\delta(q,a)δ(q,a) 在DFA中是一个状态在NFA中是一个状态集合 不确定性δ(q0,0)q3q0\delta(q_0,0){q_3q_0}δ(q0,0)q3q0关系设 L 是一个被 NFA 所接受的句子的集合则存在一个 DFA它能够接受 L。 由于 DFA 与 NFA 所接受的是同样的链集所以一般情况下无需区分它们二者统称为有限自动机 (finite automata, FA)。可以转化
4.3有限自动机正则文法
正则文法和FA等价 若G(VN,VT,P,S)G(V_N,V_T,P,S)G(VN,VT,P,S)是一个正则文法则必然存在一个有限自动机M(Σ,Q,δ,q0,F)M(\Sigma,Q,\delta,q_0,F)M(Σ,Q,δ,q0,F),使得T(M)L(G)若Ms是一个有限自动机则必然存在正则文法G,L(G)T(M) 由正则文法构造有限自动机M 令ΣVT,QVN∪T,q0S,其中T是一个新增加的非终结符号\SigmaV_T,QV_N\cup{T},q_0S,其中T是一个新增加的非终结符号ΣVT,QVN∪T,q0S,其中T是一个新增加的非终结符号如果P中有S→ϵ,则F{S,T}否则F{T}S\rightarrow\epsilon,则F\{S,T\}否则F\{T\}S→ϵ,则F{S,T}否则F{T}如果P中有B→a,B∈VN,a∈VT,则T∈δ(B,a)B\rightarrow a,B\in V_N,a\in V_T,则T\in\delta(B,a)B→a,B∈VN,a∈VT,则T∈δ(B,a)如果P有B→aC,B、C∈VN,a∈VT,则C∈δ(B,a)B\rightarrow aC,B、C\in V_N,a\in V_T,则C\in \delta(B,a)B→aC,B、C∈VN,a∈VT,则C∈δ(B,a)对于每一个a∈VT,有δ(T,a)∅a\in V_T,有\delta(T,a)\emptya∈VT,有δ(T,a)∅ 由有限自动机M构造正则文法G 令VNQ,VTΣ,Sq0V_NQ,V_T\Sigma,Sq_0VNQ,VTΣ,Sq0如果C∈δ(B,a),B,C∈Q,a∈Σ则P:B→aC如果C\in \delta(B,a),B,C\in Q,a\in \Sigma则P:B\rightarrow aC如果C∈δ(B,a),B,C∈Q,a∈Σ则P:B→aC如果C∈δ(B,a),B,C∈F,a∈Σ则P:B→a如果C\in \delta(B,a),B,C\in F,a\in \Sigma则P:B\rightarrow a如果C∈δ(B,a),B,C∈F,a∈Σ则P:B→a
5.下推自动机PDA和上下文无关文法CFG
5.1PDA
下推自动机PDAPDA 可以看成是一个带有附加的下推存储器的有限自动机下推存储器是一个栈 一个不确定的PDA可以表达成一个7元组M(Σ,Q,Γ,δ,q0,Z0,F)Σ:输入符号Q:状态的有限集合q0∈Q初始状态Γ:下推存储器符号的有穷集合Z0∈Γ:为最初出现在下推存储器顶端的符号F:终止状态集合F⊆Qδ是从Q×(Σ∪{ϵ})×Γ到Q×Γ∗子集的映射M(\Sigma,Q,\Gamma,\delta,q_0,Z_0,F)\\\Sigma:输入符号\\Q:状态的有限集合\\q_0\in Q初始状态\\\Gamma:下推存储器符号的有穷集合\\Z_0\in \Gamma:为最初出现在下推存储器顶端的符号\\F:终止状态集合F\subseteq Q\\\delta是从Q×(\Sigma\cup\{\epsilon\})×\Gamma到Q×\Gamma^*子集的映射M(Σ,Q,Γ,δ,q0,Z0,F)Σ:输入符号Q:状态的有限集合q0∈Q初始状态Γ:下推存储器符号的有穷集合Z0∈Γ:为最初出现在下推存储器顶端的符号F:终止状态集合F⊆Qδ是从Q×(Σ∪{ϵ})×Γ到Q×Γ∗子集的映射 映射关系\delta的解释 δ(q,a,Z){(q1,γ1).(q2,γ2),...(qm,γm)},q∈Q,a∈Σ,γ∈Γ∗\delta(q,a,Z)\{(q_1,\gamma_1).(q_2,\gamma_2),...(q_m,\gamma_m)\},q\in Q,a\in \Sigma,\gamma \in \Gamma^*δ(q,a,Z){(q1,γ1).(q2,γ2),...(qm,γm)},q∈Q,a∈Σ,γ∈Γ∗当PDA处于状态 q面临输入符号a 时自动机将进入 qi , i 1, 2, …, m 状态并以γi\gamma_iγi 来代替下推存储器(栈)顶端符号Z同时将输入头指向下一个字符 。当 Z 被γi\gamma_iγi取代时γi\gamma_iγi 的符号按照从左到右的顺序依次从下向上推入到存储器。特殊情况ϵ移动aϵ\epsilon移动a\epsilonϵ移动aϵ,输入头位置不移动只用于处理下推存储器内部的操作 符号约定 合法转移设有序对(q,γ),q∈Q,γ∈Γ∗,对于a∈(Σ∪{ϵ})是输入字符,β∈Γ∗,Z∈F,如果(q′,β)∈δ(q,a,Z),q′,q∈Q(q,\gamma),q\in Q,\gamma\in \Gamma^*,对于a\in(\Sigma\cup\{\epsilon\})是输入字符,\beta\in \Gamma^*,Z\in F,如果(q,\beta)\in \delta(q,a,Z),q,q\in Q(q,γ),q∈Q,γ∈Γ∗,对于a∈(Σ∪{ϵ})是输入字符,β∈Γ∗,Z∈F,如果(q′,β)∈δ(q,a,Z),q′,q∈Q 0次或多次合法转移*推 PDA M可以接受的语言为 接受收入并可到达一个可接受状态
5.1.1 PDA的例子. 输入串是从左到右依次输入的 入栈出栈都走左边进出
5.2 其他自动机
图灵机 图灵机与0型文法等价图灵机与有限自动机(FA)的区别图灵机可以通过其读/写头改变输入带的字符。仅存在概念太灵活了 线性带限自动机 线性带限自动机与1型文法等价线性带限自动机是一个确定的单带图灵机其读 写头不能超越原输入带上字符串的初始和终止位置即线性带限自动机的存储空间被输入符号串的长度所限制。
5.2.1 区别
各类自动机的主要区别是它们能够使用的信息存储空间的差异 有限状态自动机只能用状态来存储信息下推自动机除了可以用状态以外还可以用下推存储器(栈)线性带限自动机可以利用状态和输入/输出带本身。因为输入/输出带没有**“先进后出”**的限制因此其功能大于栈而图灵机的存储空间没有任何限制。
6. 有限自动机在nlp中的应用
6.1 英语单词拼写检查
6.1.1 编辑距离
编辑距离 设 X 为拼写错误的字符串其长度为m, Y 为 X 对应的正确的单词(答案)其长度为 n。则 X 和 Y 的编辑距离ed(X[m], Y[n]) 定义为从字符串 X转换到 Y 需要的插入、删除、替换和交换两个相邻的基本单位(字符)的最小个数。如 ed (recoginze, recognize) 1ed (sailn, failing) 3 假设 Z z1 z2 … zp 为字母表 A上的p 个字母构成 的字符串Z[j] 表示含有j (j 1) 个字符的子串。X[m] 为拼写错误的字符串其长度为mY[n] 为与X串接近的字符串(一个候选)其长度为n。则给定两个串X 和Y的编辑距离ed(X[m], Y[n]) 可以通过循环计算出从字符串X 转换到Y 需要进行插入、删除、替换和交换两个相邻的字符操作的最少次数 (1) 如果 xi1yj1x_{i1} y_{j1}xi1yj1两个串的最后一个字母相同 则 ed(X[i1], Y[j1]) ed(X[i], Y[j]); (2) 如果 xiyj1x_{i} y_{j1}xiyj1并且 xi1yjx_{i1} y_{j}xi1yj最后两个字符需要 交换位置 则ed(X[i1], Y[j1]) 1min{ed(X[i-1], Y[j-1]),ed(X[i], Y[j1]),ed(X[i1], Y[j])}
*3其他情况(xi1≠yj1并且(xi≠yj1或xi1≠yjx_{i1}\neq y_{j1}并且(x_i\neq y_{j1}或x_{i1}\neq y_jxi1yj1并且(xiyj1或xi1yj
ed(X[i1], Y[j1]) 1min{ed(X[i], Y[j]),ed(X[i], Y[j1]),ed(X[i1], Y[j])}其中 ed(X[0],Y[j])j (0jn)X长度为0ed(X[i],Y[0])i,(0im边界约定ed(X[-1],Y[j])ed(X[i],Y[-1])max{m,n}
6.1.2 有限状态机
有时候要在自动机上做改变 R(Q,A,δ,q0,F)Q:状态集A输入集δ:Q×A→Qq0∈Q起始状态F⊆Q终止状态集R(Q,A,\delta,q_0,F)\\ Q:状态集\\ A输入集\\ \delta:Q×A\rightarrow Q\\ q_0\in Q起始状态\\ F\subseteq Q终止状态集R(Q,A,δ,q0,F)Q:状态集A输入集δ:Q×A→Qq0∈Q起始状态F⊆Q终止状态集 L⊆A∗L\subseteq A^*L⊆A∗是R接受的语言字母构成的所有合法单词都是有限状态机中的一条路径。给定一个输入串对其进行检查的过程就是在给定阈值 t (t 0) 的情况下寻找那些与输入串的编辑距离小于 t 的路径。那么一个字符串X[m]∉LX[m]\notin LX[m]∈/L 能够被 R识别的条件是存在非空集合 C{Y[n]∣Y[n]∈Led(X[m],Y[n])≤t}C\{Y[n]|Y[n]\in L \ ed(X[m],Y[n])\leq t\}C{Y[n]∣Y[n]∈Led(X[m],Y[n])≤t} 中间有共用的单词
定义cuted(X[m],Y[n])minl≤i≤u{ed(X[i],Y[n])}lmax(1,n−t),umin(m,nt)cuted(X[m],Y[n])min_{l\leq i\leq u}\{ed(X[i],Y[n])\}\\lmax(1,n-t),umin(m,nt)cuted(X[m],Y[n])minl≤i≤u{ed(X[i],Y[n])}lmax(1,n−t),umin(m,nt) t的用途 确定截取X的范围限定编辑距离
6.1.3 深度优先搜索找路径
Y是合法的单词X是输入的单词(可能是错的词找与X最接近的合法词汇采用深度优先搜索算法从自动机中选择路径。假设Xbax, t2。那么Ya/b/c/…/zlmax{1, 1-2}1 umin{3, 12}3。即从 X 中取长度在13个字符范围内的子串X’{b, ba, bax}分别计算与 Y 之间的编辑距离保留那些 ed(X’, Y)≤ t 的路径选择 ed 最小的路径继续扩展。Xbax, t2。 Y{ba, bi, bo, … …}。 截取 X: lmax{1, 2-2}1, umin{3, 22}3。 X’{b, ba, bax}保留那些 ed(X’, Y)≤ t 的路径选择 ed 最小的路径继续扩展。 Xbax, t2。Y{baa, bad, bag, bat, bay}。 截取 X: lmax{1, 3-2}1, umin{3, 32}3。 X’{b, ba, bax}保留那些 ed(X’, Y)≤ t 的路径选择 ed 最小的路径继续扩展Y。 Xbax, t2。Y{bade}。 截取 X: lmax{1, 4-2}2, umin{3, 42}3。 X’{ba, bax}保留那些 ed(X’, Y)≤ t 的路径选择 ed 最小的路径 深度优先可能有只能得到一个解不一定最优但肯定宽度优先可以得到最短的解算法
5.2 英语单词形态分析
单复数时态比较 一般地具有相同的前缀或词根词缀不同的单词可以共用一个有限状态转移机共享其中的某些状态节点。如tie, ties, trap, traps, try, tries, to, torch, torches, toss, tosses 等。除了单词拼写检查、形态分析以外有限状态自动机还广泛应用于词性标注、句法分析、短语识别、机器翻译和语音识别等很多方面。
FA的变种
有限自动机FA只实现状态转移不产生任何输出有限状态机FSM只实现状态转移不产生任何输出有限状态转换机FST完成状态转移的同时产生一个输出
6.作业
3.1 3.2 anbncn,n≥1a^nb^nc^n,n\geq1anbncn,n≥1
3.3 3.4 3.5 3.6
