LEARNING CONTEXT-FREE GRAMMARS FROM STRUCTURAL DATA IN POLYNOMIAL-TIME
LEARNING CONTEXT-FREE GRAMMARS FROM STRUCTURAL DATA IN POLYNOMIAL-TIME
复制标题
DOI：
10.1016/0304-3975(90)90017-c
复制
发表时间：
1990-11-21
影响因子：
1.1
通讯作者：
SAKAKIBARA, Y
中科院分区：
文献类型：
--
作者：
SAKAKIBARA, Y
我们考虑从结构描述中学习上下文无关文法的问题。上下文无关文法的结构描述是文法的无标号导出树。我们提出了一个有效的算法学习上下文无关的语法使用两种类型的查询：结构等价查询和结构成员查询。学习协议是基于什么是所谓的“最小适当的老师”，它表明，语法学习算法不仅是一个正确的语法，即等价于未知的语法，但也结构上等价于它。此外，该算法在最小前沿到最小前沿的状态数中以时间多项式运行，未知语法的结构描述集的根树自动机和由结构等价查询返回的任何反例的最大大小。
We consider the problem of learning a context-free grammar from its structural descriptions. Structural descriptions of a context-free grammar are unlabelled derivation trees of the grammar. We present an efficient algorithm for learning context-free grammars using two types of queries: structural equivalence queries and structural membership queries. The learning protocol is based on what is called “minimally adequate teacher”, and it is shown that a grammar learned by the algorithm is not only a correct grammar, i.e. equivalent to the unknown grammar but also structurally equivalent to it. Furthermore, the algorithm runs in time polynomial in the number of states of the minimum frontier-to-root tree automaton for the set of structural descriptions of the unknown grammar and the maximum size of any counter-example returned by a structural equivalence query.