3 ms·

> It's well understood that CFGs can not be induced from examples I think you mean something more specific (e.g. polynomial in a particular sense). + Automati

> It's well understood that CFGs can not be induced from examples I think you mean something more specific (e.g. polynomial in a particular sense). + Automatic Learning of Context-Free Grammar (Chen et al.): http://www.aclweb.org/anthology/O06-1004 http://www.aclweb.org/anthology/O06-1004 + Learning context-free grammars from structural data in polynomial time (Sakakibara, 1994): http://www.sciencedirect.com/science/article/pii/030439759090017C http://www.sciencedirect.com/science/article/pii/03043975909... (uses positive skeletons) Nice overview: http://staff.icar.cnr.it/staff/ruffolo/public_html/progetti/projects/07.Learning%20di%20SCFG/SCFG%20learning/index-c1.pdf http://staff.icar.cnr.it/staff/ruffolo/public_html/progetti/...

avmich 9y ago
Also http://nbviewer.jupyter.org/url/norvig.com/ipython/xkcd1313.ipynb http://nbviewer.jupyter.org/url/norvig.com/ipython/xkcd1313.... , considering regexes are a subset of CFGs.
- YeGoblynQueenne 9y ago
  From a quick glance, the example doesn't quite learn regular grammars - rather, it reduces them to finite grammars (e.g. the finite grammar of all US presidential winners and losers) and learns (or, more accurately, invents) a regular expression for them. Finite grammar induction from positive examples only is feasible in polynomial time, so Peter Norvig's notebook will not cause the fabric of the space-time continuum to be torn asunder, I am sure.
YeGoblynQueenne 9y ago
Aw man! That 1994 paper by Sakakibara is a piece of history! It concludes by saying that it's "part of the work in the major R&D of the Fifth Generation Computer Project conducted under the program set up by MITI" [1]. Plus, Sakakibara is one of my grammar induction heroes :0 However- his algorithm learns CFGs from structural data, which is to say, derivation trees (think parse trees). So it's completely irrelevant to the example in the article, that attempts to learn a^nb^n from examples of its derivations -which remains impossible. As to the other paper, by Chen, Tseng and Chen, that's about learning a CFG that reproduces the strings in a corpus- so learning a CFG of a corpus as opposed to the grammar of a context-free language (therefore, a context-free grammar) which, again, remains impossible. _____________ [1] https://en.wikipedia.org/wiki/Fifth_generation_computer https://en.wikipedia.org/wiki/Fifth_generation_computer

avmich 9y ago

Also http://nbviewer.jupyter.org/url/norvig.com/ipython/xkcd1313.ipynb http://nbviewer.jupyter.org/url/norvig.com/ipython/xkcd1313.... , considering regexes are a subset of CFGs.

YeGoblynQueenne 9y ago
From a quick glance, the example doesn't quite learn regular grammars - rather, it reduces them to finite grammars (e.g. the finite grammar of all US presidential winners and losers) and learns (or, more accurately, invents) a regular expression for them. Finite grammar induction from positive examples only is feasible in polynomial time, so Peter Norvig's notebook will not cause the fabric of the space-time continuum to be torn asunder, I am sure.

YeGoblynQueenne 9y ago

Aw man! That 1994 paper by Sakakibara is a piece of history! It concludes by saying that it's "part of the work in the major R&D of the Fifth Generation Computer Project conducted under the program set up by MITI" [1]. Plus, Sakakibara is one of my grammar induction heroes :0 However- his algorithm learns CFGs from structural data, which is to say, derivation trees (think parse trees). So it's completely irrelevant to the example in the article, that attempts to learn a^nb^n from examples of its derivations -which remains impossible. As to the other paper, by Chen, Tseng and Chen, that's about learning a CFG that reproduces the strings in a corpus- so learning a CFG of a corpus as opposed to the grammar of a context-free language (therefore, a context-free grammar) which, again, remains impossible. _____________ [1] https://en.wikipedia.org/wiki/Fifth_generation_computer https://en.wikipedia.org/wiki/Fifth_generation_computer