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, pointer to Harvard-hosted pdf

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",
  url =	 "https://www.cs.cornell.edu/home/llee/papers/learncfls.pdf",
  comment =	 {Written in 1994.  Official Harvard pdf at http://nrs.harvard.edu/urn-3:HUL.InstRepos:25104425}
}