  Recently, deep learning has revolutionized the field of natural language
processing, with neural language models proving to be very effective for
next-word prediction. However, a rigorous theoretical explanation for their
success in the context of formal language theory has not yet been developed, as
it is unclear why neural language models can learn the combinatorial rules that
govern the next-word prediction task. In this paper, we study a class of formal
languages that can be used to model real-world examples of English sentences.
We construct neural language models can solve the next-word prediction task in
this context with zero error. Our proof highlights the different roles of the
embedding layer and the fully connected component within the neural language
model.
