Constructing CFGs from examples.

Has there been any work done on algorithms for
constructing CFGs from example strings? For example,
given strings bb, bab, baab, and baaab, we might
produce a CFG (guessing that an infinite number of
a's is, in fact, OK)
      <S> ::= b<A>b
      <A> ::= a <A> | empty.
Obviously there are other possibilities, such as
the trivial solution
      <S> ::= bb | bab | baab | baaab,
but we'd like to go with the "smallest" grammar with
highest generative power.


I'm guessing this problem is related to work done
in the Machine Learning community, but I'd be
grateful for any relevant references.


Thanks.


Christian


___________________________________________________________________________
Christian Collberg | Email: c_collberg@cs.auckland.ac.nz
Computer Science Dept | Fax: +64-9-373-7453
University of Auckland | Phone: +64-9-373-7599 x 6137
Private Bag 92019, | WWW: http://www.cs.auckland.ac.nz/~collberg/
Auckland, NZ |
--

Return to the comp.compilers page.
Search the comp.compilers archives again.