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.
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.
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
+ Learning context-free grammars from structural data in polynomial time (Sakakibara, 1994): http://www.sciencedirect.com/science/article/pii/03043975909... (uses positive skeletons)
Nice overview: http://staff.icar.cnr.it/staff/ruffolo/public_html/progetti/...