Learning Cover Context-Free Grammars from Structural Data

Scientific Annals of Computer Science

article

M. Marin¹  G. Istrate² 

[1] Department of Computer Science, West University of Timi¸soara;Department of Computer Science, West University of Timi¸soara and eAustria Research Institute

关键词: automata theory and formal languages;    grammatical inference;    structural descriptions;   

DOI  :  10.7561/SACS.2014.2.253

来源: Alexandru Ioan Cuza University of Iasi

【 摘 要 】

We consider the problem of learning an unknown context-free grammar from its structural descriptions with depth at most `. The structural descriptions of the context-free grammar are its unlabelled derivation trees. The goal is to learn a cover context-free grammar (CCFG) with respect to `, that is, a CFG whose structural descriptions with depth at most ` agree with those of the unknown CFG. We propose an algorithm, called LA` , that efficiently learns a CCFG using two types of queries: structural equivalence and structural membership. The learning protocol is based on what is called in the literature a “minimally adequate teacher.” We show that LA` runs in time polynomial in the number of states of a minimal deterministic finite cover tree automaton (DCTA) with respect to `. This number is often much smaller than the number of states of a minimum deterministic finite tree automaton for the structural descriptions of the unknown grammar.

【 授权许可】

CC BY-ND