[edit]

# Beyond Chomsky Normal Form: Extending Strong Learning Algorithms for PCFGs

*Proceedings of the Fifteenth International Conference on Grammatical Inference*, PMLR 153:4-17, 2021.

#### Abstract

We extend a recent consistent strong learning algorithm for a subclass of probabilistic context-free grammars in Chomsky normal form, (Clark and Fijalkow, 2020) to a much larger class of grammars by weakening the normal form constraints to allow for a richer class of derivation structures that are not necessarily binary branching, including among other possibilities unary branching trees which introduce some technical difficulties. By modifying the structural conditions appropriately we obtain an algorithm which is computationally efficient, and a consistent estimator for the class of grammars defined.