Learnability and Overgeneration in Computational Syntax

Proceedings of the Society for Computation in Linguistics

Venue: SCiL
Type: Workshop
Formal Languages
Learning Theory

Sophie Hao

Yale University


January 5, 2019

This paper addresses the hypothesis that unnatural patterns generated by grammar formalisms can be eliminated on the grounds that they are unlearnable. I consider three examples of formal languages thought to represent dependencies unattested in natural language syntax, and show that all three can be learned by grammar induction algorithms following the Distributional Learning paradigm of Clark and Eyraud (2007). While learnable language classes are restrictive by necessity (Gold, 1967), these facts suggest that learnability alone may be insufficient for addressing concerns of overgeneration in syntax.