Abstract
Characterizing the computational power of neural network architectures interms of formal language theory remains a crucial line of research, as itdescribes lower and upper bounds on the reasoning capabilities of modern AI.However, when empirically testing these bounds, existing work often leaves adiscrepancy between experiments and the formal claims they are meant tosupport. The problem is that formal language theory pertains specifically torecognizers: machines that receive a string as input and classify whether itbelongs to a language. On the other hand, it is common instead to evaluatelanguage models on proxy tasks, e.g., language modeling or sequence-to-sequencetransduction, that are similar in only an informal sense to the underlyingtheory. We correct this mismatch by training and evaluating neural networksdirectly as binary classifiers of strings, using a general method that can beapplied to a wide variety of languages. As part of this, we extend an algorithmrecently proposed by Sn{\ae}bjarnarson et al. (2025) for efficientlength-controlled sampling of strings from regular languages. We provideresults on a variety of languages across the Chomsky hierarchy for three neuralarchitectures: a simple RNN, an LSTM, and a causally-masked transformer. Wefind that the RNN and LSTM often outperform the transformer, and that auxiliarytraining objectives such as language modeling can help, although no singleobjective uniformly improves performance across languages and architectures.Our contributions will facilitate theoretically sound empirical testing oflanguage recognition claims in future work. We have released our datasets as abenchmark called FLaRe (Formal Language Recognition), along with our code.