<p>de la Higuera's book focuses mostly on the classical theory of Angluin style learning of finite state automata and related results. This theory has been lifted to the class of context free grammars and beyond to multiple context free grammars etc. using what is called "distributional learning" which in its modern form started with Clark &amp; Eyraud paper in JMLR 2007 (I was the first author). The most recent papers in this line of research are  Chihiro Shibata, Ryo Yoshinaka:
Probabilistic learnability of context-free grammars with basic distributional properties from positive examples. Theor. Comput. Sci. 620: 46-72 (2016) which looks at learning when the samples are generated by a PCFG.
There are analogues of the basic Angluin results using membership queries etc as well, and results for strong learning where you want to recover a CFG which generates the same trees as the target grammar (Learning Trees from Strings, Clark JMLR 2013). 
(Apologies for the self citations) </p>

<p>I wasn't familiar with the Bastani paper, but it seems to be a heuristic paper with no theoretical guarantees. </p>

CC BY-SA 4.0
2018-11-29T12:03:42.383Z
Thank you so much for the answer, and the hints on which papers to look at. (I was wondering why the paper by Bastani et al. was comparing to L-Star and RPNI, both of which are algorithms on identifying automata, and some what old at this point. They do cite (Higuera 2010), but miss out on a lot of important work such as yours).
Rahul Gopinath
CC BY-SA 4.0
2018-11-28T09:53:59.753Z
2018-11-29T16:05:48.970Z
2018-11-29T16:05:48.970Z
Alexander Clark
<p>Note that there is now a replication study (coauthored by Rahul Gopinath) of the 2017 paper <em>Synthesizing Program Input Grammars</em>, see <a href="https://publications.cispa.saarland/3607/1/pldi2022glade.pdf" rel="nofollow noreferrer">https://publications.cispa.saarland/3607/1/pldi2022glade.pdf</a></p>
<p>Two survey articles that might be relevant.</p>
<ul>
<li>A. D'Ulizia, F. Ferri, P. Grifoni, <em>A survey of grammatical inference methods for natural language learning.</em> (2011)</li>
<li>V. Muralidaran, I. Spasic, D. Knight, <em>A systematic review of unsupervised approaches to grammar induction.</em> (2021)</li>
</ul>

CC BY-SA 4.0
2023-10-13T10:17:58.360Z
2023-10-13T10:30:42.313Z
2023-10-13T10:30:42.313Z
Martin Berger
<p><a href="https://en.wikipedia.org/wiki/Grammar_induction" rel="nofollow noreferrer">Grammar induction</a> of <em>Context Free Languages</em> seems to be a very well researched field. I would like to know the current state of the art in inducing a <em>Context Free Grammar</em> (I am reading up Higuera's Grammatical Inference book, and looking through previous papers). What is the current bound on inducing a Context Free Grammar given unstructured (non parenthesized) input?</p>

<p>In particular, I would like to know the community's opinion on the paper by Bastani et al. <a href="https://obastani.github.io/docs/pldi17.pdf" rel="nofollow noreferrer">Synthesizing Program Input Grammars</a>. How it compares to existing work. Does it improve the algorithmic bounds?</p>

CC BY-SA 4.0
2018-11-23T10:07:07.167Z
I do not have the privilege for creating tags: I wish these tags were added: grammar-inference grammar-induction
Rahul Gopinath
<lg.learning><grammars><context-free>
What is the current state of the art in black-box grammar induction?
Rahul Gopinath
# What is the current state of the art in black-box grammar induction?

(Asked by: username_0 on 2018-11-23)

[Grammar induction](https://en.wikipedia.org/wiki/Grammar_induction) of *Context Free Languages* seems to be a very well researched field. I would like to know the current state of the art in inducing a *Context Free Grammar* (I am reading up Higuera's Grammatical Inference book, and looking through previous papers). What is the current bound on inducing a Context Free Grammar given unstructured (non parenthesized) input?

In particular, I would like to know the community's opinion on the paper by Bastani et al. [Synthesizing Program Input Grammars](https://obastani.github.io/docs/pldi17.pdf). How it compares to existing work. Does it improve the algorithmic bounds?

**Tags:** lg.learning, grammars, context-free

> **Comments:**
> **username_0**: I do not have the privilege for creating tags: I wish these tags were added: grammar-inference grammar-induction  

---

## 2 answers

### Answer by username_1 on 2018-11-28. Score: 2 | Accepted answer

de la Higuera's book focuses mostly on the classical theory of Angluin style learning of finite state automata and related results. This theory has been lifted to the class of context free grammars and beyond to multiple context free grammars etc. using what is called "distributional learning" which in its modern form started with Clark & Eyraud paper in JMLR 2007 (I was the first author). The most recent papers in this line of research are Chihiro Shibata, Ryo Yoshinaka:
Probabilistic learnability of context-free grammars with basic distributional properties from positive examples. Theor. Comput. Sci. 620: 46-72 (2016) which looks at learning when the samples are generated by a PCFG.
There are analogues of the basic Angluin results using membership queries etc as well, and results for strong learning where you want to recover a CFG which generates the same trees as the target grammar (Learning Trees from Strings, Clark JMLR 2013).
(Apologies for the self citations)

I wasn't familiar with the Bastani paper, but it seems to be a heuristic paper with no theoretical guarantees.

> **Comments:**
> **username_0**: Thank you so much for the answer, and the hints on which papers to look at. (I was wondering why the paper by Bastani et al. was comparing to L-Star and RPNI, both of which are algorithms on identifying automata, and some what old at this point. They do cite (Higuera 2010), but miss out on a lot of important work such as yours).  

---

### Answer by username_2 on 2023-10-13. Score: 2

Note that there is now a replication study (coauthored by username_0) of the 2017 paper *Synthesizing Program Input Grammars*, see <https://publications.cispa.saarland/3607/1/pldi2022glade.pdf>

Two survey articles that might be relevant.

* A. D'Ulizia, F. Ferri, P. Grifoni, *A survey of grammatical inference methods for natural language learning.* (2011)
* V. Muralidaran, I. Spasic, D. Knight, *A systematic review of unsupervised approaches to grammar induction.* (2021)


---

