Scientific Annals of Computer Science | |
Learning Cover Context-Free Grammars from Structural Data | |
article | |
M. Marin1  G. Istrate2  | |
[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
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO202106050001089ZK.pdf | 494KB | download |