Learning Context-Free Grammars from Partially Structured Examples
Learning Context-Free Grammars from Partially Structured Examples
复制标题
从部分结构化示例中学习上下文无关语法
DOI：
10.1007/978-3-540-45257-7_19
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Hidenori Muramatsu
中科院分区：
文献类型：
--
作者：
Y. Sakakibara;Hidenori Muramatsu
在本文中，我们考虑的问题，归纳学习上下文无关文法从部分结构化的例子。一个结构化的例子由一个字符串表示，其中插入了一些括号来指示语法的派生树的形状。我们表明，部分结构化的例子有助于提高学习算法的效率。我们采用基于GA的学习算法上下文无关文法使用表表示Sakakibara和Kondo以前提出的[7]，并提出了一种算法，以消除不必要的非终结符和产生式规则使用部分结构化的例子在基于GA的学习算法的初始阶段。我们还表明，我们的学习算法从部分结构化的例子可以识别一个上下文无关的语法具有预期的结构，是更灵活和适用的学习方法，从完全结构化的例子[5]。
In this paper, we consider the problem of inductively learning context-free grammars from partially structured examples. A structured example is represented by a string with some parentheses inserted to indicate the shape of the derivation tree of a grammar. We show that the partially structured examples contribute to improving the efficiency of the learning algorithm. We employ the GA-based learning algorithm for context-free grammars using tabular representations which Sakakibara and Kondo have proposed previously [7], and present an algorithm to eliminate unnecessary nonterminals and production rules using the partially structured examples at the initial stage of the GA-based learning algorithm. We also show that our learning algorithm from partially structured examples can identify a context-free grammar having the intended structure and is more flexible and applicable than the learning methods from completely structured examples [5].