Benchmarking Neural Networks on Formal Language Classes

Understanding the computational abilities of neural networks is key to predicting their performance on real-world tasks, and formal language theory offers a mature, rigorous framework for characterizing what kinds of problems they can solve. A large body of theoretical work has sought to pin down which formal language classes they can express, but this work relies on various simplifications (e.g., hard attention) that differ from practice. Empirical studies that use unsimplified architectures therefore provide an important supplement to this work, but they typically evaluate models on small sets of hand-picked languages, leaving the rest of a class drastically underexplored. To remedy this, we evaluate transformers, simple RNNs, and LSTMs on formal languages sampled randomly from a hierarchy of pertinent classes: $\mathcal{R}$-trivial, star-free, regular, and context-free languages. We sample from distributions with full support over each class, so expanding the coverage of a class is simply a matter of scale. We also develop a novel algorithm for efficiently sampling a string of a target length from a probabilistic context-free grammar. Transformers appear to agree with predictions based on unique hard attention: they recognize some non-$\mathcal{R}$-trivial star-free languages but no non-star-free languages. All models learn to approximate context-free languages well but struggle to recognize them perfectly. We have publicly released our code.