[拼音]：wenfa tuiduan

[外文]：gram ticalinference

根据给定的有限样本集推断产生该样本集所属语言类的文法规则的学习算法。它是句法模式识别（见结构模式识别）的重要组成部分。通过文法推断可以得到一组重写规则（见短语结构文法），它们除了能描述给定的有限样本集外，还能描述那些虽不在给定样本集内但却与给定样本集在某种意义上有同样性质(属于同一类)的模式，从而可以用这一组重写规则对输入模式进行句法分析以达到识别的目的。文法推断过程就是对模式类进行描述的过程，它的正确性在很大程度上决定于所给样本集的完备性和人们对模式性质了解的程度，文法推断算法至今仍然是句法模式识别中的一个重要研究课题。

文法推断课题的一般性质是：

（1）给定某个文法G所产生的语言L(G)的一个有限子集S+(叫正样本集)和不属于这个语言的 的一个有限子集S -(叫负样本集)，须假定S+是结构完整的，即描述L(G)的每一条重写规则在描述S +中的样本时至少使用一次。

（2）推断得到的文法Ga应满足S+吇L(Ga)和。在理想情况下,L(Ga)=L(G)。在实际问题中,由于所提供样本的局限性,S+往往不是结构完整的，推断得到的文法Ga只是G 的一种近似。对于同样的有限样本集，不同的推断算法可以得到不同的Ga，因此需要定义一个所推断出的文法对于给定样本集的优度度量，从而能在某种意义上得到一个满意的结果。

文法推断算法有穷举文法推断算法和归纳文法推断算法两种形式。

（1）穷举文法推断算法：在一个文法类中进行搜索，以求得与所给样本集和学习系统（教师）所提供的其他附加信息一致的文法。为了提高搜索的效率可以利用覆盖这个重要概念：如果某个文法G1不产生S+中所有的语句，在穷举中可以删去被G1所覆盖的所有文法；而如果文法G1产生S-中某些句子，则在穷举中可删去所有覆盖G1的文法。

（2）归纳文法推断算法：从正样本S+中求得语言L的递归结构,从而使一个恰好产生给定正样本的非递归性文法成为一个能够产生任意多语句的递归性文法。以规范微商文法为基础的推断算法和基于k尾的文法是文法推断算法的两个例子。

首先用形式微商概念求出一个只产生学习样本集（语句 ）的规范文法。语句 A对于终止符a∈Σ的形式微商是DaA={x|ax∈A}。A对于空符号链λ（即符号数为0的链）的微商DλA＝A。A对于某个子句a1a2的形式微商是 Dɑ1ɑ2A＝Dɑ2(Dɑ1A)。类似地，Dɑ1ɑ2…ɑnA＝Dɑn(Dɑn-1(…(Dɑ1A…)))。对应正样本集S +的规范微商有限状态文法 ＝(N，Σ，P，S)按下列方法求得：

（1）∑是S +中所有语句中包含的所有互异的终止符 。

（2）N是S +对于∑的不为空的形式微商 ,N＝{u1,…,ur},其中u1=DλS +。

（3）S＝u1。

（4）按下列条件得到P中的重写规则:(i)ui→auj在P中的充分必要条件是Dɑui=uj;(ii)ui→a在P中的充分必要条件是λ∈Dɑui。例如S +＝{01,1001}的规范微商文法 ＝(N，∑，P，s)，其中∑＝{0,1}；N＝{u1,u2,u3,u4}(u1＝DλS +＝{01,1001}，u2＝D0u1＝{1},u3＝D1u1＝{001},u4＝D0u3＝{01},此外D0u4＝{1}＝u2);S＝u1；P:u1─→0u2,u2─→1，u1─→1u3，u3─→0u4，u4─→0u2。在求得 的基础上可以得到相应的递归性文法G＝(N′，∑，P′，s′)。这时把 的非终止符集划分为若干互不相交的子集，例如N1={u1,u2},N2＝{u3,u4},则N′＝{N1,N2}。为了求P′,只要把原来P 中的非终止符按它属于哪一个划分子集而改为N′中的相应符号,因此P′:N1─→0N1,N1─→1,N1─→1N2，N2─→0N2，N2─→0N1,此外s′＝N1，∑＝{0,1}。显然G产生的语言除了 S +外还有无限多的语句。 中的非终止符集可以用有限的不同方法划分为互不相交的子集，因此相应地有有限个递归性文法，其中至少有一个文法是推断问题的解。

语言 s对于终止符构成的子句z的k尾微商是

例如，对于语句 S+＝{01,100,111,0010}而言，

设ui和ui是规范微商有限状态文法 中两个互异的非终止状态,ui和uj分别对应于微商DxiS + 和DxjS +，其中xi，xj∈∑ *。则ui和uj为k尾等价状态的充分必要条件是

g(xi，S+,k)＝g(xj，S+,k)

把规范微商文法中等价的状态合并，可得到从 导出的可数个递归性文法，其中包含至少一个文法可作为推断问题的解。

对于正则文法，已研究出以规范微商文法为基础的推断算法和基于 k尾的文法推断算法，但对于上下文无关文法的推断则尚无普遍适用的算法，只是对某些特殊限制的上下文无关文法有了一些启发式的算法。例如应用结构信息序列推断算子优先文法以及k齐次、k互异文法和枢轴文法推断，图形描述文法的启发式推断等。在随机文法的推断方面，曾经提出一种直接综合随机有限状态自动机算法。其中状态转移概率可以从随机语句 中相应的概率信息中导出。

此外，在人机对话式的文法推断系统结构、正则树文法、网状文法等推断方法方面都已经取得了一定的成果。

严正声明：本文由历史百科网注册或游客用户智胜自行上传发布关于» 文法推断的内容，本站只提供存储，展示，不对用户发布信息内容的原创度和真实性等负责。请读者自行斟酌。同时如内容侵犯您的版权或其他权益，请留言并加以说明。站长审查之后若情况属实会及时为您删除。同时遵循 CC 4.0 BY-SA 版权协议，尊重和保护作者的劳动成果，转载请标明出处链接和本声明内容：作者：智胜；本文链接：https://www.freedefine.cn/wenzhan/34970.html