Towards a theory of how the structure of language is acquired by deep neural networks

Francesco Cagnetta, Matthieu Wyart

How much data is required to learn the structure of a language via next-token prediction? We study this question for synthetic datasets generated via a Probabilistic Context-Free G…