## Learning Trees from Strings: A Strong Learning Algorithm for some Context-Free Grammars

*Alexander Clark*; 14(Dec):3537−3559, 2013.

### Abstract

Standard models of language learning are concerned with weak
learning: the learner, receiving as input only information about
the strings in the language, must learn to generalise and to
generate the correct, potentially infinite, set of strings
generated by some target grammar. Here we define the
corresponding notion of strong learning: the learner, again only
receiving strings as input, must learn a grammar that generates
the correct set of structures or parse trees. We formalise this
using a modification of Gold's identification in the limit
model, requiring convergence to a grammar that is isomorphic to
the target grammar. We take as our starting point a simple
learning algorithm for substitutable context-free languages,
based on principles of distributional learning, and modify it so
that it will converge to a canonical grammar for each language.
We prove a corresponding strong learning result for a subclass
of context-free grammars.

[abs][pdf][bib]