Abstract: We survey methods for learning context-free languages (CFL's) in the theoretical computer science literature. We first present some important negative results. Then, we consider five types of methods: those that take text as input, those that take structural information as input, those that rely on CFL formalisms that are not based on context-free grammars, those which learn subclasses of CFL's, and stochastic methods. A description of the subclasses of CFL's considered is provided, as is an extensive bibliography.

Paper formats: ps, pdf, ps.gz

BibTeX entry:

@TechReport{Lee:96a,
  author =	 "Lillian Lee",
  title =	 "Learning of Context-Free Languages: A Survey of the
                  Literature",
  institution =	 "Harvard University",
  year =	 1996,
  number =	 "TR-12-96",
  note =	 "Available via ftp,
                  ftp://deas-ftp.harvard.edu/techreports/tr-12-96.ps.gz",
  comment =	 {Written in 1994.}
}