Training Neural Networks as Recognizers of Formal Languages

## Abstract

Abstract Characterizing the computational power of neural network architectures in terms of formal language theory remains a crucial line of research, as it describes lower and upper bounds on the reasoning capabilities of modern AI. However, when empirically testing these bounds, existing work often leaves a discrepancy between experiments and the formal claims they are meant to support. The problem is that formal language theory pertains specifically to recognizers: machines that receive a string as input and classify whether it belongs to a language. On the other hand, it is common to instead use proxy tasks that are similar in only an informal sense, such as language modeling or sequence-to-sequence transduction. We correct this mismatch by training and evaluating neural networks directly as binary classifiers of strings, using a general method that can be applied to a wide variety of languages. As part of this, we extend an algorithm recently proposed by Snæbjarnarson et al. ( 2024 ) to do length-controlled sampling of strings from regular languages, with much better asymptotic time complexity than previous methods. We provide results on a variety of languages across the Chomsky hierarchy for three neural architectures: a simple RNN, an LSTM, and a causally-masked transformer. We find that the RNN and LSTM often outperform the transformer, and that auxiliary training objectives such as language modeling can help, although no single objective uniformly improves performance across languages and architectures. Our contributions will facilitate theoretically sound empirical testing of language recognition claims in future work. We have released our datasets as a benchmark called FLaRe 1 1 1 https://github.com/rycolab/flare (Formal Language Recognition), along with our code. 2 2 2 https://github.com/rycolab/neural-network-recognizers

## 1 Introduction

Neural network-based AI systems, including large language models (LLMs), have been hailed for their emergent reasoning abilities. What exactly are these abilities? The precise scope of what has emerged is hard to pin down. Fortunately, formal language theory gives us a vocabulary for ascribing hard limits to the kinds of computations neural networks can perform, enabling a much-needed formal characterization. For example, results from formal language theory allow us to know with certainty that a transformer LM (with no extra chain-of-thought timesteps) cannot determine whether two regular expressions with repetition operators are equivalent; a transformer LM runs in quadratic time, but the aforementioned problem provably requires exponential time (Sipser, ).

A long line of research has attempted to precisely describe the class of problems neural architectures can solve in terms of formal languages. It consists of two parts: formal results that mathematically prove language class bounds, often under simplifying assumptions; and empirical results that, in complementary fashion, provide evidence of these bounds under real settings. Simplifying assumptions for the transformer architecture have included the absence of layer normalization, the use of hard attention, or the use of special positional encodings (see Strobl et al. () for a survey). Formal expressivity results also typically do not comment on whether solutions are practically reachable through training, even though the bias imposed by the training algorithm may render the set of solvable problems much smaller than suggested by formal expressivity results. Empirical results are therefore important for validating formal results under unsimplified conditions.

The purpose of this paper is to reconcile a subtle but important disconnect between empirical results and claims about computational power. Formal language theory deals in recognizers: machines that receive a string as input and classify whether it is a member of a language. The Chomsky hierarchy and the classes P and NP are defined in terms of this paradigm. Consider, for example, the recent study by Delétang et al. (): its core claims are about the Chomsky hierarchy, but the supporting experiments train language models and evaluate them as string-to-string functions. While the experiments do validate the authors’ claims about a memory-based hierarchy in an informal sense, formally, the experiments do not demonstrate claims about the Chomsky hierarchy of *languages*, but an analogous hierarchy of *functions*. There are multiple ways to fix this mismatch: one could change the theoretical claims to those of a hierarchy of language models (Icard, ; Borenstein et al., ) or string-to-string functions (Strobl et al., ); or one could change the experiments to recognition to match the Chomsky hierarchy. In this paper, we explore the latter approach.

We propose an experimental setup for training neural networks as recognizers of formal languages that only requires language-specific algorithms for positive sampling and membership testing. In contrast to most prior work, we generate adversarial negative examples without requiring language-specific rules (cf. Weiss et al., ; Someya et al., ; Bhattamishra et al., ). Like Delétang et al. (), we focus on length generalization, and we include two sets of experiments that carefully distinguish between tests of inductive bias and expressivity. We extend recent work by Snæbjarnarson et al. () to implement a scalable algorithm for length-controlled sampling from finite automata, with a preprocessing step that is asymptotically faster than a standard approach by a factor of ${{O}({n_{\mathrm{max}}}^{2})}$, where ${n_{\mathrm{max}}}$ is the maximum string length. In order to explore the effectiveness of other training objectives used in past work while remaining within the recognition paradigm, we experiment with auxiliary loss terms in a multi-task learning setup. Although they do aid certain architectures on specific tasks, they do not have a consistent effect across architectures and languages, and a simple binary cross-entropy objective is often very effective. We compare three architectures: a simple RNN, an LSTM, and a causally-masked transformer. We experiment on a variety of formal languages across the Chomsky hierarchy and show that the transformer often underperforms the RNN and LSTM. We also see evidence of recent claims that transformers prefer low-sensitivity Boolean functions (Hahn & Rofin, ). We have publicly released our datasets as a benchmark called FLaRe (Formal Language Recognition), along with our code.

## 2 Method

We start with some basic definitions. An alphabet, often denoted with the variable ${\Sigma}$, is a non-empty finite set of elements called symbols. A string over ${\Sigma}$ is a finite sequence of symbols in ${\Sigma}$. We use ${\varepsilon}$ to denote the empty string. A language (or formal language) over ${\Sigma}$ is a (possibly infinite) set of strings over ${\Sigma}$. Let ${{\Sigma}^{\ast}}$ denote the language of all strings over ${\Sigma}$. If a machine works by receiving a string as input and producing a decision to accept or reject it as output, then we call it a recognizer, and we say that it recognizes the language of strings that it accepts. A language class is a (possibly infinite) set of languages. Throughout the rest of this section, let us assume we are dealing with a specific language ${L}$ over alphabet ${\Sigma}$. For any string ${w}\in{{\Sigma}^{\ast}}$, we call the proposition ${w}\in{L}$ the label of ${w}$.

We now describe a general, effective method for sampling datasets from formal languages and training neural networks as recognizers. We address a number of challenges cited in past work, namely negative sampling, length-constrained sampling, and the paucity of the training signal when training on binary labels. We provide particularly efficient solutions for regular languages.

### 2.1 Dataset generation

Suppose we want to sample a set of ${N}$ string-label pairs, where the length of every string is in the range ${[{n_{\mathrm{min}}},{n_{\mathrm{max}}}]}$. Assume that we have available to us
(a) an algorithm for sampling a string ${w}$ from ${L}$ such that $|{w}|\in{[{n_{\mathrm{min}}},{n_{\mathrm{max}}}]}$, and
(b) an algorithm for determining whether a string ${w}\in{{\Sigma}^{\ast}}$ is a member of ${L}$.
(^3^33This is directly comparable to the classical learning theory of Gold (), which assumes the availability of a “text” of positive examples and an “informant” that provides labels.) We do the following ${N}$ times. We uniformly sample a label from $\{0,1\}$, ensuring a balanced dataset. If the label is $1$, we sample a string from ${L}$ using the algorithm assumed by item (a). If the label is 0 0, we propose a random string ${w}$ as a negative example. Since it is possible that ${w}$ is inadvertently a member of ${L}$, we test whether it is in ${L}$ using the algorithm assumed by item (b). If ${w}\in{L}$, we propose a new string until we get a confirmed negative example.

We propose negative strings in one of two ways, with uniform probability. Half the time, we propose a uniform negative example by uniformly sampling a length ${n}$ from ${[{n_{\mathrm{min}}},{n_{\mathrm{max}}}]}$, then uniformly sampling a string from ${\Sigma}^{{n}}$. For many languages, this is very likely to produce a negative example, but one that is so superficially dissimilar to positive examples that the classification problem becomes too easy and fails to demonstrate the underlying algorithm. Prior work, therefore, typically uses language-specific rules to generate adversarial negative samples (Weiss et al., ; Bhattamishra et al., ; Someya et al., ). To keep our methodology more general, the other half of the time, we propose a perturbed negative example by sampling a positive example and perturbing it with random edits (cf. Weiss et al., ). More precisely, we (1) sample the number of edits ${K}$ from a geometric distribution that heavily favors small ${K}$, and (2) iteratively apply ${K}$ uniformly-sampled edits (single-symbol insertion, replacement, or deletion). We describe this procedure in more detail in App. A. Typically, this is much more likely to produce negative examples that are difficult to distinguish from positive ones (see also our analysis in Figure 1).

### 2.2 Efficient length-constrained sampling for regular languages

We now turn to efficient length-constrained sampling for regular languages. Any regular language can be expressed as a simple state machine called a deterministic finite automaton (DFA).

###### Definition 1 .

A partial deterministic finite automaton (partial DFA) is a tuple ${{\mathcal{A}}}=({Q},{\Sigma},{\delta},{{q_{0}}},{F})$ where
(i) ${Q}$is a finite set of states;
(ii) ${\Sigma}$is an alphabet;
(iii) ${\delta}\colon{Q}\times{\Sigma}\rightarrow{Q}\cup\{{\emptyset}\}$is the transition function, where ${\emptyset}$ indicates the absence of a transition;
(iv) ${{q_{0}}}\in{Q}$is the start state; and
(v) ${F}\subseteq{Q}$is the set of accept states.
If ${\delta}({{q}},{a})={r}$, we say that ${{\mathcal{A}}}$ has a transition from ${{q}}$ to ${r}$ that scans ${a}$, and we write ${{q}}\xrightarrow{{a}}{r}\in{\delta}$.

Our definition of DFA is *partial* in the sense that we do not require an outgoing transition to be defined for all $({{q}},{a})\in{Q}\times{\Sigma}$. For simplicity, from now on, we will simply refer to partial DFAs as DFAs. We call a sequence ${\pi}$ of connecting states and transitions a path. If ${\pi}$’s transitions scan ${a}_{1},\ldots,{a}_{{n}}$, we say that ${\pi}$ scans the string ${a}_{1}\cdots{a}_{{n}}$. For any string ${w}\in{{\Sigma}^{\ast}}$, if there is a path that starts in ${{q_{0}}}$, scans ${w}$, and ends in an accept state, we say that ${{\mathcal{A}}}$ accepts ${w}$ and rejects it otherwise. This leads to a straightforward ${{O}({n})}$-time membership testing algorithm: start in the initial state, follow the unique ${w}$-scanning path (if it exists), and accept if it ends in an accept state. We say that ${{\mathcal{A}}}$ recognizes the language $\{{w}\in{{\Sigma}^{\ast}}\mid{{\mathcal{A}}}\text{ accepts }{w}\}$. If all states in a DFA are reachable from the start state and can lead to an accept state, we call it trimmed.

We present an algorithm for length-constrained sampling from a DFA’s language that is asymptotically much more efficient than a standard approach. To facilitate the exposition of this algorithm (and other algorithms in this paper), we first introduce semirings and weighted DFAs.

###### Definition 2 .

A monoid is a tuple $({{\mathbb{K}}},\mathbin{{\odot}},{\textbf{I}})$, where ${{\mathbb{K}}}$ is a set, $\mathbin{{\odot}}$ is an associative binary operation, and ${\textbf{I}}\in{{\mathbb{K}}}$, called the identity element, satisfies ${\textbf{I}}\mathbin{{\odot}}a=a\mathbin{{\odot}}{\textbf{I}}=a$ for all $a\in{{\mathbb{K}}}$. If $a\mathbin{{\odot}}b=b\mathbin{{\odot}}a$ for all $a,b\in{{\mathbb{K}}}$, we say that the monoid is commutative.

###### Definition 3 .

A semiring is a tuple $({{\mathbb{K}}},\oplus,\otimes,{\bm{0}},{\bm{1}})$ where $({{\mathbb{K}}},\oplus,{\bm{0}})$ is a commutative monoid and $({{\mathbb{K}}},\otimes,{\bm{1}})$ is a monoid. Additionally, $\otimes$ distributes over $\oplus$: $a\otimes(b\oplus c)=(a\otimes b)\oplus(a\otimes c)$ and $(a\oplus b)\otimes c=(a\otimes c)\oplus(b\otimes c)$; and ${\bm{0}}$ is absorbing with respect to $\otimes$: ${\bm{0}}\otimes a=a\otimes{\bm{0}}={\bm{0}}$. Furthermore, let $a^{\otimes i}=\bigotimes_{j=1}^{i}a$, and ${a^{\ast}}=\bigoplus_{i=0}^{\infty}a^{\otimes i}$. If ${a^{\ast}}$ is defined and in ${{\mathbb{K}}}$ for all $a\in{{\mathbb{K}}}$, we say the semiring is closed.

A weighted DFA is a DFA with semiring-weighted transitions. The weights can, for example, be probabilities. Some of our algorithms are variants of existing algorithms over a different semiring.

###### Definition 4 .

A weighted deterministic finite automaton (WDFA) over a semiring $({{\mathbb{K}}},\oplus,\otimes,{\bm{0}},{\bm{1}})$ is a tuple ${{\mathcal{A}}}=({Q},{\Sigma},{\delta},{{q_{0}}},{\rho})$ such that
(i) ${Q}$, ${\Sigma}$, and ${{q_{0}}}$ are defined as in Def. 1;
(ii) ${\delta}\colon{Q}\times{\Sigma}\rightarrow({Q}\times{{\mathbb{K}}})\cup\{{
\emptyset}\}$is the transition function; and
(iii) ${\rho}\colon{Q}\rightarrow{{\mathbb{K}}}$is the accept weight function.
If ${\delta}({{q}},{a})=({r},{w})$, we say that ${{\mathcal{A}}}$ has a transition from ${{q}}$ to ${r}$ that scans ${a}$ with weight ${w}$, and we write ${{q}}\xrightarrow{{a}/{w}}{r}\in{\delta}$. We call $\{{q}\in{Q}\mid{\rho}({q})\neq{\bm{0}}\}$ the set of accept states.

Rather than simply accepting or rejecting a string, a WDFA assigns it a weight. The weight of a path is the product of the weights of its transitions and accept state, and the weight of a string is the weight of the path that scans it, or ${\bm{0}}$ if one does not exist. We can assign probabilities to strings with the probability semiring $([0,1],+,\times,0,1)$ or, for numerical stability, the log semiring $({\mathbb{R}}\cup\{-\infty\},\log(\exp(\cdot)+\exp(\cdot)),+,-\infty,0)$. For random sampling, a probability semiring-weighted DFA must have transition and accept weights that are locally normalized per state.

###### Definition 5 .

A WDFA ${{\mathcal{A}}}=({Q},{\Sigma},{\delta},{{q_{0}}},{\rho})$ over the probability semiring is called a probabilistic DFA (PDFA) if for all ${{q}}\in{Q}$, $\left(\sum_{{{q}}\xrightarrow{{a}/{p}}{r}\in{\delta}}{p}\right)+{\rho}({{q}})=1$.

Now that we have set up the necessary definitions, we describe our procedure for length-constrained sampling from a regular language ${L}$. Let ${\mathcal{A}}$ be a trimmed DFA that recognizes ${L}$. We convert ${\mathcal{A}}$ to a PDFA ${{\mathcal{A}}^{\prime}}$ by assigning uniform probabilities to its transitions and accept states. More precisely, for each state ${{q}}\in{Q}$, let ${k}_{{{q}}}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}|\{{a}\in{
\Sigma}\mid\exists{r}\in{Q},~{}{{q}}\xrightarrow{{a}}{r}\in{\delta}\}|+{
\mathbbm{1}\!\left[{q}\in{F}\right]}$. We set the probability of each outgoing transition to $\frac{1}{{k}_{{q}}}$, and the accept probability to $\frac{1}{{k}_{{q}}}{\mathbbm{1}\!\left[{q}\in{F}\right]}$.
Let ${p_{{{\mathcal{A}}^{\prime}}}}$ denote the probability distribution defined by ${{\mathcal{A}}^{\prime}}$, and w a ${p_{{{\mathcal{A}}^{\prime}}}}$-distributed string-valued random variable. Mathematically (without getting into algorithmic details yet), our length-constrained sampling algorithm will do the following. Let ${N_{{{\mathcal{A}}^{\prime}}}}\mathrel{\stackrel{{\scriptstyle\textnormal{def}
}}{{=}}}\{{n}\in{[{n_{\mathrm{min}}},{n_{\mathrm{max}}}]}\mid\exists{w}\in{
\Sigma}^{{n}},~{}{p_{{{\mathcal{A}}^{\prime}}}}({w})>0\}$. We sample a length ${n}$ uniformly from ${N_{{{\mathcal{A}}^{\prime}}}}$. Then, we sample a string from the posterior distribution ${p_{{{\mathcal{A}}^{\prime}}}}({{\textnormal{w}}}\mid|{{\textnormal{w}}}|={n})$. This amounts to sampling from the distribution

$$ $p({w})=\frac{1}{|{N_{{{\mathcal{A}}^{\prime}}}}|}{p_{{{\mathcal{A}}^{\prime}}} }({{\textnormal{w}}}={w}\mid|{{\textnormal{w}}}|=|{w}|).$ (1) $$

How do we compute ${N_{{{\mathcal{A}}^{\prime}}}}$ and sample from the posterior distribution efficiently? One approach would be to construct a WDFA for the distribution ${p_{{{\mathcal{A}}^{\prime}}}}({{\textnormal{w}}}={w}\mid|{{\textnormal{w}}}|=
|{w}|)$. We could do this by intersecting ${{\mathcal{A}}^{\prime}}$ with a DFA that recognizes ${\Sigma}^{{n}}$, a procedure that would take ${{O}({|{Q}|}{n})}$ time (cf. van der Poel et al., ). This would result in a WDFA that is not necessarily probabilistic, so as a prerequisite for sampling, we would need to renormalize its weights to locally sum to 1 (Def. 5), using a procedure known as weight pushing (Mohri, ) that runs in ${{O}(({|{Q}|}{n})^{3})}$ time. Supposing ${n_{\mathrm{min}}}=0$, it would take ${{O}({|{Q}|}^{3}{n_{\mathrm{max}}}^{4})}$ time to do this for all lengths. This would not be scalable for our experiments, in which we sample strings up to length ${n_{\mathrm{max}}}=500$. Fortunately, we can improve this by a factor of ${{O}({n_{\mathrm{max}}}^{2})}$ using a tool proposed by Snæbjarnarson et al. () called the counting semiring. The key idea is to *share* computation among the different lengths by running a version of the weight pushing algorithm—only once—that computes the normalized weights for all lengths. Instead of weighting the DFA with probabilities, we use *vectors* that bin probabilities by each length in $[0,{n_{\mathrm{max}}}]$.

###### Definition 6 .

Let ${\mathcal{W}}=({{\mathbb{K}}},\mathbin{{\oplus}},\mathbin{{\otimes}},{\bm{0}},
{\bm{1}})$ be a semiring, and let ${D}\in{\mathbb{Z}_{\geq 0}}$. For ${\bm{v}}\in{{\mathbb{K}}^{{D}+1}}$, we write ${\bm{v}}=({\bm{v}}_{0},{\bm{v}}_{1},\ldots,{\bm{v}}_{{D}})$. The ${D}$^th-order counting semiring with respect to the base semiring ${\mathcal{W}}$ is the semiring ${{\mathcal{W}}^{{D}}}=({{\mathbb{K}}^{{D}+1}},\mathbin{{\leavevmode\hbox to
11.04pt{\vbox to11.04pt{\pgfpicture\makeatletter\hbox{\hskip 5.51933pt\lower-5
.51933pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{
pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}
\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.31934pt}{0.0pt}\pgfsys@curveto{5.31934pt}{2.93782pt}{
2.93782pt}{5.31934pt}{0.0pt}{5.31934pt}\pgfsys@curveto{-2.93782pt}{5.31934pt}{
-5.31934pt}{2.93782pt}{-5.31934pt}{0.0pt}\pgfsys@curveto{-5.31934pt}{-2.93782
pt}{-2.93782pt}{-5.31934pt}{0.0pt}{-5.31934pt}\pgfsys@curveto{2.93782pt}{-5.31
934pt}{5.31934pt}{-2.93782pt}{5.31934pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-3.8889pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb
}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathbin{{\oplus}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}},\mathbin{{\leavevmode\hbox to11.04pt{\vbox
to
11.04pt{\pgfpicture\makeatletter\hbox{\hskip 5.51933pt\lower-5.51933pt\hbox to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{
0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill
{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }
\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.31934pt}{0.0pt}\pgfsys@curveto{5.31934pt}{2.93782pt}{
2.93782pt}{5.31934pt}{0.0pt}{5.31934pt}\pgfsys@curveto{-2.93782pt}{5.31934pt}{
-5.31934pt}{2.93782pt}{-5.31934pt}{0.0pt}\pgfsys@curveto{-5.31934pt}{-2.93782
pt}{-2.93782pt}{-5.31934pt}{0.0pt}{-5.31934pt}\pgfsys@curveto{2.93782pt}{-5.31
934pt}{5.31934pt}{-2.93782pt}{5.31934pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-3.8889pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb
}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathbin{{\otimes}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}},{\leavevmode\hbox to8.93pt{\vbox to8.93pt{
\pgfpicture\makeatletter\hbox{\hskip 4.46367pt\lower-4.46367pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{4.26367pt}{0.0pt}\pgfsys@curveto{4.26367pt}{2.35478pt}{
2.35478pt}{4.26367pt}{0.0pt}{4.26367pt}\pgfsys@curveto{-2.35478pt}{4.26367pt}{
-4.26367pt}{2.35478pt}{-4.26367pt}{0.0pt}\pgfsys@curveto{-4.26367pt}{-2.35478
pt}{-2.35478pt}{-4.26367pt}{0.0pt}{-4.26367pt}\pgfsys@curveto{2.35478pt}{-4.26
367pt}{4.26367pt}{-2.35478pt}{4.26367pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{${\bm{0}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}},{\leavevmode\hbox to8.93pt{\vbox to8.93pt{
\pgfpicture\makeatletter\hbox{\hskip 4.46367pt\lower-4.46367pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{4.26367pt}{0.0pt}\pgfsys@curveto{4.26367pt}{2.35478pt}{
2.35478pt}{4.26367pt}{0.0pt}{4.26367pt}\pgfsys@curveto{-2.35478pt}{4.26367pt}{
-4.26367pt}{2.35478pt}{-4.26367pt}{0.0pt}\pgfsys@curveto{-4.26367pt}{-2.35478
pt}{-2.35478pt}{-4.26367pt}{0.0pt}{-4.26367pt}\pgfsys@curveto{2.35478pt}{-4.26
367pt}{4.26367pt}{-2.35478pt}{4.26367pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{${\bm{1}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}})$, where:

$$ $\displaystyle({\bm{u}}\mathbin{{\leavevmode\hbox to11.04pt{\vbox to11.04pt{ \pgfpicture\makeatletter\hbox{\hskip 5.51933pt\lower-5.51933pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.31934pt}{0.0pt}\pgfsys@curveto{5.31934pt}{2.93782pt}{ 2.93782pt}{5.31934pt}{0.0pt}{5.31934pt}\pgfsys@curveto{-2.93782pt}{5.31934pt}{ -5.31934pt}{2.93782pt}{-5.31934pt}{0.0pt}\pgfsys@curveto{-5.31934pt}{-2.93782 pt}{-2.93782pt}{-5.31934pt}{0.0pt}{-5.31934pt}\pgfsys@curveto{2.93782pt}{-5.31 934pt}{5.31934pt}{-2.93782pt}{5.31934pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-3.8889pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb }{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathbin{{\oplus}}$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}}{\bm{v}})_{{i}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}{\bm{u}}_ {{i}}\mathbin{{\oplus}}{\bm{v}}_{{i}}$ $\displaystyle({\bm{u}},{\bm{v}}\in{{\mathbb{K}}^{{D}+1}};0\leq{i}\leq{D})$ (2a) $\displaystyle({\bm{u}}\mathbin{{\leavevmode\hbox to11.04pt{\vbox to11.04pt{ \pgfpicture\makeatletter\hbox{\hskip 5.51933pt\lower-5.51933pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.31934pt}{0.0pt}\pgfsys@curveto{5.31934pt}{2.93782pt}{ 2.93782pt}{5.31934pt}{0.0pt}{5.31934pt}\pgfsys@curveto{-2.93782pt}{5.31934pt}{ -5.31934pt}{2.93782pt}{-5.31934pt}{0.0pt}\pgfsys@curveto{-5.31934pt}{-2.93782 pt}{-2.93782pt}{-5.31934pt}{0.0pt}{-5.31934pt}\pgfsys@curveto{2.93782pt}{-5.31 934pt}{5.31934pt}{-2.93782pt}{5.31934pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-3.8889pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb }{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathbin{{\otimes}}$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}}{\bm{v}})_{{i}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\bigoplus _{{j}=0}^{{i}}{\bm{u}}_{{j}}\mathbin{{\otimes}}{\bm{v}}_{{i}-{j}}$ $\displaystyle({\bm{u}},{\bm{v}}\in{{\mathbb{K}}^{{D}+1}};0\leq{i}\leq{D})$ (2b) ${\bm{0}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}({\bm{0}} ,\ldots,{\bm{0}})$ $\displaystyle{\leavevmode\hbox to8.93pt{\vbox to8.93pt{\pgfpicture \makeatletter\hbox{\hskip 4.46367pt\lower-4.46367pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.26367pt}{0.0pt}\pgfsys@curveto{4.26367pt}{2.35478pt}{ 2.35478pt}{4.26367pt}{0.0pt}{4.26367pt}\pgfsys@curveto{-2.35478pt}{4.26367pt}{ -4.26367pt}{2.35478pt}{-4.26367pt}{0.0pt}\pgfsys@curveto{-4.26367pt}{-2.35478 pt}{-2.35478pt}{-4.26367pt}{0.0pt}{-4.26367pt}\pgfsys@curveto{2.35478pt}{-4.26 367pt}{4.26367pt}{-2.35478pt}{4.26367pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{${\bm{1}}$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}\mathrel{\stackrel{{\scriptstyle\textnormal{ def}}}{{=}}}({\bm{1}},{\bm{0}},\ldots,{\bm{0}})$ (2c) $$

If ${\mathcal{W}}$ is closed, so is ${{\mathcal{W}}^{{D}}}$. We write ${\bm{v}}^{{\leavevmode\hbox to5.58pt{\vbox to5.58pt{\pgfpicture\makeatletter
\hbox{\hskip 2.79033pt\lower-2.79033pt\hbox to0.0pt{\pgfsys@beginscope
\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{2.59033pt}{0.0pt}\pgfsys@curveto{2.59033pt}{1.43062pt}{
1.43062pt}{2.59033pt}{0.0pt}{2.59033pt}\pgfsys@curveto{-1.43062pt}{2.59033pt}{
-2.59033pt}{1.43062pt}{-2.59033pt}{0.0pt}\pgfsys@curveto{-2.59033pt}{-1.43062
pt}{-1.43062pt}{-2.59033pt}{0.0pt}{-2.59033pt}\pgfsys@curveto{1.43062pt}{-2.59
033pt}{2.59033pt}{-1.43062pt}{2.59033pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-1.75pt}{-1.62846pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\ast$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}}\mathrel{\stackrel{{\scriptstyle\textnormal
{def}}}{{=}}}\operatorname*{\scalerel*{\mathbin{{\leavevmode\hbox to11.04pt{
\vbox to11.04pt{\pgfpicture\makeatletter\hbox{\hskip 5.51933pt\lower-5.51933pt
\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}
\pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.31934pt}{0.0pt}\pgfsys@curveto{5.31934pt}{2.93782pt}{
2.93782pt}{5.31934pt}{0.0pt}{5.31934pt}\pgfsys@curveto{-2.93782pt}{5.31934pt}{
-5.31934pt}{2.93782pt}{-5.31934pt}{0.0pt}\pgfsys@curveto{-5.31934pt}{-2.93782
pt}{-2.93782pt}{-5.31934pt}{0.0pt}{-5.31934pt}\pgfsys@curveto{2.93782pt}{-5.31
934pt}{5.31934pt}{-2.93782pt}{5.31934pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-3.8889pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb
}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathbin{{\oplus}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}}}{\sum}}_{{j}=0}^{\infty}{\bm{v}}^{\mathbin
{{\leavevmode\hbox to7.96pt{\vbox to7.96pt{\pgfpicture\makeatletter\hbox{
\hskip 3.97978pt\lower-3.97978pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke
{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{3.77979pt}{0.0pt}\pgfsys@curveto{3.77979pt}{2.08754pt}{
2.08754pt}{3.77979pt}{0.0pt}{3.77979pt}\pgfsys@curveto{-2.08754pt}{3.77979pt}{
-3.77979pt}{2.08754pt}{-3.77979pt}{0.0pt}\pgfsys@curveto{-3.77979pt}{-2.08754
pt}{-2.08754pt}{-3.77979pt}{0.0pt}{-3.77979pt}\pgfsys@curveto{2.08754pt}{-3.77
979pt}{3.77979pt}{-2.08754pt}{3.77979pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.72223pt}{-1.75pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathbin{{\otimes}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}}{j}}$; see Eq. 11 for a closed-form solution. The indexes of the vectors in the ${D}$^th-order counting semiring represent the values of an integer counter from 0 0 to ${D}$; the meaning of the counter depends on how the semiring is used. We will use the counter to keep track of the number of symbols scanned by a DFA, i.e., the length of a sampled string. Say the base semiring is the probability semiring. In this case, ${\bm{v}}_{{i}}$ is the probability of scanning a length-${i}$ string. This interpretation applies to anything with a weight, including transitions, accept states, paths, and strings. Notice that if ${\bm{u}}$ is a vector whose only non-zero element is ${\bm{u}}_{{i}}$, and ${\bm{v}}$ is a vector whose only non-zero element is ${\bm{v}}_{{j}}$, then ${\bm{u}}\mathbin{{\leavevmode\hbox to11.04pt{\vbox to11.04pt{\pgfpicture
\makeatletter\hbox{\hskip 5.51933pt\lower-5.51933pt\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.31934pt}{0.0pt}\pgfsys@curveto{5.31934pt}{2.93782pt}{
2.93782pt}{5.31934pt}{0.0pt}{5.31934pt}\pgfsys@curveto{-2.93782pt}{5.31934pt}{
-5.31934pt}{2.93782pt}{-5.31934pt}{0.0pt}\pgfsys@curveto{-5.31934pt}{-2.93782
pt}{-2.93782pt}{-5.31934pt}{0.0pt}{-5.31934pt}\pgfsys@curveto{2.93782pt}{-5.31
934pt}{5.31934pt}{-2.93782pt}{5.31934pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-3.8889pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb
}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathbin{{\otimes}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}}{\bm{v}}$ is a vector with the value ${\bm{u}}_{{i}}\mathbin{{\otimes}}{\bm{v}}_{{j}}$ at index ${i}+{j}$ and ${\bm{0}}$ elsewhere. More generally, Eq. 2b convolves the two vectors, in effect marginalizing over all ways of reaching a count of ${i}$ for each $0\leq{i}\leq{D}$.

To use the counting semiring for length-constrained sampling from a PDFA ${{\mathcal{A}}^{\prime}}$, we lift ${{\mathcal{A}}^{\prime}}$ to a ${n_{\mathrm{max}}}$^th-order counting semiring-weighted DFA ${{\mathcal{A}}_{{D}}}$ as follows. For every transition ${{q}}\xrightarrow{{a}/{p}}{r}$ in ${{\mathcal{A}}^{\prime}}$, we set the weight of ${{q}}\xrightarrow{{a}}{r}$ in ${{\mathcal{A}}_{{D}}}$ to $({\bm{0}},{p},{\bm{0}},\ldots,{\bm{0}})$, indicating that the transition scans exactly one symbol with probability ${p}$. For every state with accept weight ${p}$, we set its accept weight in ${{\mathcal{A}}_{{D}}}$ to $({p},{\bm{0}},\ldots,{\bm{0}})$, indicating that it accepts (and scans no symbols) with probability ${p}$. The weight of any path in ${{\mathcal{A}}_{{D}}}$ is then a vector with at most one non-zero element, whose index is equal to the number of symbols the path scans, and whose value is the product of the original transition probabilities. We combine the weights of multiple paths by adding them elementwise (Eq. 2a). To avoid underflow, we use the log semiring as the base semiring instead of the probability semiring (see § B.2).

Running a semiring generalization of weight pushing on ${{\mathcal{A}}_{{D}}}$ allows us to compute exactly the quantities we need for efficient sampling from ${p_{{{\mathcal{A}}^{\prime}}}}({{\textnormal{w}}}\mid|{{\textnormal{w}}}|={n})$. At every state, and for every $0\leq{i}\leq{D}$, it computes a probability distribution over (1) outgoing transitions and (2) whether to accept, conditioned on scanning exactly ${i}$ symbols in the future, according to the probabilities of ${{\mathcal{A}}^{\prime}}$. It does this by computing (1) for every transition, the sum of the weights of all paths in ${{\mathcal{A}}_{{D}}}$ that start with that transition, and (2) for every state, the sum of the weights of all paths in ${{\mathcal{A}}_{{D}}}$ that start and end at that state. Once we have these weights, which are vectors, if we locally normalize them elementwise at each state, we get the aforementioned probability distributions. Now, a ${{O}({n})}$-time sampling algorithm for sampling a string of exactly length ${n}$ becomes straightforward. We start in ${{q_{0}}}$ and initialize a counter ${i}$ to ${n}$. Repeatedly, we sample transitions from the normalized distributions for index ${i}$ from the current state and decrement ${i}$ for every symbol scanned. We stop when we sample an accept action. The set of valid string lengths ${N_{{{\mathcal{A}}^{\prime}}}}$ is the set of all ${n}$ for which we can take any transition or accept at ${{q_{0}}}$, conditioned on scanning ${n}$ symbols in the future, with nonzero probability. See § B.2 for more details and pseudocode.

###### Definition 1 .

###### Definition 2 .

###### Definition 3 .

###### Definition 4 .

###### Definition 5 .

###### Definition 6 .

##### Time complexity.

With the log semiring as the base semiring, the $\mathbin{{\leavevmode\hbox to11.04pt{\vbox to11.04pt{\pgfpicture\makeatletter
\hbox{\hskip 5.51933pt\lower-5.51933pt\hbox to0.0pt{\pgfsys@beginscope
\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{5.31934pt}{0.0pt}\pgfsys@curveto{5.31934pt}{2.93782pt}{
2.93782pt}{5.31934pt}{0.0pt}{5.31934pt}\pgfsys@curveto{-2.93782pt}{5.31934pt}{
-5.31934pt}{2.93782pt}{-5.31934pt}{0.0pt}\pgfsys@curveto{-5.31934pt}{-2.93782
pt}{-2.93782pt}{-5.31934pt}{0.0pt}{-5.31934pt}\pgfsys@curveto{2.93782pt}{-5.31
934pt}{5.31934pt}{-2.93782pt}{5.31934pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-3.8889pt}{-2.5pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{rgb
}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathbin{{\otimes}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}}$ and ${}^{{\leavevmode\hbox to5.58pt{\vbox to5.58pt{\pgfpicture\makeatletter\hbox{
\hskip 2.79033pt\lower-2.79033pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke
{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{2.59033pt}{0.0pt}\pgfsys@curveto{2.59033pt}{1.43062pt}{
1.43062pt}{2.59033pt}{0.0pt}{2.59033pt}\pgfsys@curveto{-1.43062pt}{2.59033pt}{
-2.59033pt}{1.43062pt}{-2.59033pt}{0.0pt}\pgfsys@curveto{-2.59033pt}{-1.43062
pt}{-1.43062pt}{-2.59033pt}{0.0pt}{-2.59033pt}\pgfsys@curveto{1.43062pt}{-2.59
033pt}{2.59033pt}{-1.43062pt}{2.59033pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-1.75pt}{-1.62846pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\ast$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}}$ operations (Eqs. 2b and 11) can be computed in ${{O}({D}^{2})}$ time. Weight pushing requires ${{O}({|{Q}|}^{3})}$ multiplications and ${{O}({|{Q}|})}$ star operations, making the overall time complexity of this approach ${{O}({|{Q}|}^{3}{D}^{2})}={{O}({|{Q}|}^{3}{n_{\mathrm{max}}}^{2})}$. Moreover, the operations in Def. 6 and weight pushing are all amenable to vectorization, and we take advantage of this by accelerating it with PyTorch (Paszke et al., ).

### 2.3 Neural network architectures

We compare three neural network architectures:
(a) a multi-layer simple RNN (Elman, ) with a $\tanh$ activation function and learned initial hidden states,
(b) a multi-layer LSTM (Gers & Schmidhuber, ) with decoupled input and forget gates and learned initial hidden states, and
(c) a causally-masked transformer encoder (Vaswani et al., ) with pre-norm (Wang et al., ; Nguyen & Salazar, ) and sinusoidal positional encodings.
In all cases, the model receives a string of symbols ${w}={{w}_{1}}\cdots{{w}_{{n}}}\in{\Sigma}^{n}$ as input, converts it to a sequence of input embedding vectors ${\bm{x}_{1}},\ldots,{\bm{x}_{{n}}}\in{\mathbb{R}}^{d}$ using an embedding matrix ${\bm{E}}$, and produces a sequence of hidden vectors ${\bm{h}_{0}},{\bm{h}_{1}},\ldots,{\bm{h}_{{n}}}\in{\mathbb{R}}^{d}$, which are used to compute logits for loss terms. For the simple RNN and LSTM, the hidden vectors are the hidden states of the last layer. For the transformer, the hidden vectors are the outputs of the last layer, and we always prepend a reserved bos symbol to the input, whose corresponding output is ${\bm{h}_{0}}$. For more details, see App. C.

We apply a learned affine transformation, called the recognition head, to the last hidden vector to classify whether the string is a member of the language. Let ${p_{{M}}({w}\in{L})}$ denote the probability that ${w}$ is a member of ${L}$ according to the neural network model ${M}$, and let $\sigma(\cdot)$ be the logistic function.

$$ ${p_{{M}}({w}\in{L})}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}} \sigma({{\bm{W}}_{\mathrm{R}}}{\bm{h}_{{n}}}+{{\bm{b}}_{\mathrm{R}}})$ (3) $$

We say that the model accepts ${w}$ if ${p_{{M}}({w}\in{L})}\geq\frac{1}{2}$ and rejects it otherwise.

### 2.4 Training objectives

In all experiments, we train a neural network to classify whether an input string is in ${L}$ by minimizing the binary cross-entropy of the recognition head (cf. Weiss et al., ; Bhattamishra et al., ; van der Poel et al., ; Hahn & Rofin, ; Bhattamishra et al., ). For any probability ${p}$ and proposition ${\phi}$, we define the binary cross-entropy ${H}_{{\phi}}\!\left({p}\right)$ as follows.

$$ ${H}_{{\phi}}\!\left({p}\right)\mathrel{\stackrel{{\scriptstyle\textnormal{def} }}{{=}}}\begin{cases}-\log({p})&\text{if }{\phi}\\ -\log(1-{p})&\text{otherwise}\end{cases}$ (4) $$

We minimize the following loss function.

$$ ${{\mathcal{L}}_{\mathrm{R}}({M},{w})}\mathrel{\stackrel{{\scriptstyle \textnormal{def}}}{{=}}}{H}_{{w}\in{L}}\!\left({p_{{M}}({w}\in{L})}\right)$ (5) $$

Using ${{\mathcal{L}}_{\mathrm{R}}({M},{w})}$ as the only training objective may lead to some problems. For one, it might be difficult to learn to orchestrate a large number of internal computational steps given only a single bit of information per example. Moreover, gradient originates only from the last timestep, which is problematic for the RNN and LSTM, which are susceptible to the exploding and vanishing gradient problems. It is presumably for these reasons, in addition to the need for negative sampling, that most prior work has shied away from a pure language recognition training objective. One way to alleviate these issues is to provide the model with hints about the expected intermediate computational steps at all timesteps. Indeed, a common setup in past work is to have the model predict, for each timestep ${t}$, the set of symbols that may appear at position ${t}$ given the prefix ${{w}_{1}}\cdots{{w}_{{t}-1}}$ (Cleeremans et al., ; Gers et al., ; Schmidhuber et al., ; Rodriguez & Wiles, ; Suzgun et al., ; ; ; Bhattamishra et al., ; ; Ebrahimi et al., ).

To this end, we include experiments that add one or both of the following auxiliary loss terms to the training objective for positive examples:
(a) a language modeling loss term (cf. Hewitt et al., ; DuSell & Chiang, ; ; ; ; Liu et al., ; Akyürek et al., ; Someya et al., ; Borenstein et al., ), which requires the model to learn a distribution over next symbols at each position; and
(b) a next symbol prediction(^4^44This is often called next character prediction in prior work.) loss term, which requires the model to predict *whether* each symbol may appear next at each position, given the prefix of ${w}$ seen so far.

When we include the language modeling loss term, we add a language modeling head to the model that computes logits from the hidden vectors. The weights of the language modeling head are tied to the embedding matrix ${\bm{E}}$. We always require the head to predict eos as the last symbol, and we add an embedding for eos to ${\bm{E}}$. We average cross-entropy over timesteps to get the loss term. Let ${{\Sigma}_{{\textsc{eos}}}}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{
{=}}}{\Sigma}\cup\{{\textsc{eos}}\}$, and let ${\bm{E}}_{{{\Sigma}_{{\textsc{eos}}}}}$ denote the sub-slice of ${\bm{E}}$ that only contains embeddings for symbols in ${{\Sigma}_{{\textsc{eos}}}}$ (i.e., it does not contain the reserved bos embedding used by the transformer).

$$ $\displaystyle{p_{{M}}({{w}_{{t}}}\mid{w}_{<{t}})}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\mathrm{ softmax}(({\bm{E}}_{{{\Sigma}_{{\textsc{eos}}}}})^{T}{\bm{h}_{{t}-1}})_{{{w}_{ {t}}}}$ $\displaystyle(1\leq{t}\leq{n}+1)$ (6a) $\displaystyle{{\mathcal{L}}_{\mathrm{LM}}({M},{w})}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\frac{1}{ {n}+1}\sum_{{t}=1}^{{n}+1}-\log{p_{{M}}({{w}_{{t}}}\mid{w}_{<{t}})}$ $\displaystyle{{w}_{{n}+1}}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{ =}}}{\textsc{eos}}$ (6b) $$

Likewise, when we include the next symbol prediction loss term, we add a next symbol prediction head. For any string ${u}\in{{\Sigma}^{\ast}}$, we define the set of valid next symbols as follows.

$$ ${\textsc{Next}}_{{L}}({u})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{ =}}}\{{a}\in{{\Sigma}_{{\textsc{eos}}}}\mid\exists{v}\in{({{\Sigma}_{{\textsc{ eos}}}})^{\ast}}~{}{u}{a}{v}\in{L}\mathbin{{\circ}}\{{\textsc{eos}}\}\}$ (7) $$

We use binary cross-entropy to train the model to discern whether each symbol in ${{\Sigma}_{{\textsc{eos}}}}$ is in ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$. We average cross-entropy over symbol types and timesteps to get the loss term.

$$ $\displaystyle{p_{{M}}({{a}\in{{\textsc{Next}}_{{L}}({{w}_{<{t}}})}})}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sigma({{ \bm{W}}_{\mathrm{NS}}}{\bm{h}_{{t}-1}}+{{\bm{b}}_{\mathrm{NS}}})_{{a}}$ $\displaystyle(1\leq{t}\leq{n}+1;{a}\in{{\Sigma}_{{\textsc{eos}}}})$ (8) $$

$$ ${{\mathcal{L}}_{\mathrm{NS}}({M},{w})}\mathrel{\stackrel{{\scriptstyle \textnormal{def}}}{{=}}}\frac{1}{{n}+1}\sum_{{t}=1}^{{n}+1}\frac{1}{|{{\Sigma} _{{\textsc{eos}}}}|}\sum_{{a}\in{{\Sigma}_{{\textsc{eos}}}}}{H}_{{{a}\in{{ \textsc{Next}}_{{L}}({{w}_{<{t}}})}}}\!\left({p_{{M}}({{a}\in{{\textsc{Next}}_ {{L}}({{w}_{<{t}}})}})}\right)$ (9) $$

We say that at each timestep ${t}$, the model predicts the set $\{{a}\in{{\Sigma}_{{\textsc{eos}}}}\mid{p_{{M}}({{a}\in{{\textsc{Next}}_{{L}}(
{{w}_{<{t}}})}})}\geq\frac{1}{2}\}$. Unlike language modeling, next symbol prediction adds additional information to the training data, as ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$ can include information about unobserved strings. Because of the presence of eos, it also requires the model to predict whether every *prefix* of ${w}$ is in ${L}$. For trimmed partial DFAs, we can easily precompute the set of valid next symbols for each state based on the outgoing transitions (Algorithm 6). We use language-specific rules for non-regular languages (App. E). The full loss function with all auxiliary loss terms is

$$ ${{\mathcal{L}}({M},{w})}\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=} }}{{\mathcal{L}}_{\mathrm{R}}({M},{w})}+{{\lambda}_{\mathrm{LM}}}{{\mathcal{L} }_{\mathrm{LM}}({M},{w})}+{{\lambda}_{\mathrm{NS}}}{{\mathcal{L}}_{\mathrm{NS} }({M},{w})}$ (10) $$

where ${{\lambda}_{\mathrm{LM}}},{{\lambda}_{\mathrm{NS}}}\in{{{\mathbb{R}}_{\geq 0}}}$ are coefficients that determine the importance of each auxiliary loss term. Whenever an auxiliary loss term is not included, this is equivalent to setting ${{\lambda}_{\mathrm{LM}}}$ or ${{\lambda}_{\mathrm{NS}}}$ to 0. Note that we never include them for negative examples. When computing the loss for a whole minibatch of examples, we average the loss ${{\mathcal{L}}({M},{w})}$ of the individual examples.

## 3 Experiments

We test the performance of the three architectures in § 2.3 on a variety of formal languages (Table 1) that have proven to be of particular interest in prior work, and that come from various levels of the Chomsky hierarchy. These include analogs of the transduction tasks used by Delétang et al. (). For each regular language, we generate datasets using a hand-crafted DFA and the algorithms described in § 2.2. For the other languages, we use language-specific algorithms for length-constrained sampling and membership testing. We describe all languages in more detail in App. E. We call this collection of datasets FLaRe (Formal Language Recognition).

**Table 1: Formal languages tested in this paper and included in FLaRe. For each language, we show the language class that it belongs to: regular (R), deterministic context-free (DCF), context-free (CF), or context-sensitive (CS). Each language does not belong to the previous language classes. Let $c_{{u}}({w})$ be the number of times substring ${u}$ occurs in ${w}$, let ${w}_{i\rightarrow{a}}$ be ${w}$ with its $i$^th symbol replaced with ${a}$, and let $\langle{x}\rangle$ be the little-endian binary encoding of $x\in{\mathbb{Z}_{\geq 0}}$. See App. E for details.**
| Class | Language | Description | Example String |
| --- | --- | --- | --- |
| R | Even Pairs | $\{{w}\in{\{\texttt{0},\texttt{1}\}^{\ast}}\mid c_{\texttt{01}}({w})+c_{\texttt<br>{10}}({w})\text{ is even}\}$ | 010110 |
|  |  | $=\{{a}{u}{a}\mid{a}\in\{\texttt{0},\texttt{1}\},{u}\in{\{\texttt{0},\texttt{1}<br>\}^{\ast}}\}\cup\{{\varepsilon},\texttt{0},\texttt{1}\}$ |  |
|  | Repeat 01 | $\{(\texttt{01})^{n}\mid n\geq 0\}$ | 010101 |
|  | Parity | $\{{w}\in{\{\texttt{0},\texttt{1}\}^{\ast}}\mid c_{\texttt{1}}({w})\text{ is<br>odd}\}$ | 11011001 |
|  | Cycle Navigation | A sequence of left (<), right (>), stay (=) moves on a 5-position cycle, then the final position (0-indexed). | >>=<>2 |
|  | Modular Arithmetic | Expression involving $\{+,-,\times\}$ and $\{0,\ldots,4\}$, then the result mod 5. No operator precedence. | 1-3×2=1 |
|  | Dyck-$(2,3)$ | Strings of balanced brackets with 2 bracket types and a maximum depth of 3. | [()([])]() |
|  | First | $\{\texttt{1}{w}\mid{w}\in{\{\texttt{0},\texttt{1}\}^{\ast}}\}$ | 100010 |
| DCF | Majority | $\{{w}\in{\{\texttt{0},\texttt{1}\}^{\ast}}\mid c_{\texttt{1}}({w})>c_{\texttt{<br>0}}({w})\}$ | 101101 |
|  | Stack Manipulation | A stack from bottom to top, a sequence of push and pop operations, and the resulting stack from top to bottom. | 011 pop =10 |
|  | Marked Reversal | $\{{w}\texttt{\#}{w}^{R}\mid{w}\in{\{\texttt{0},\texttt{1}\}^{\ast}}\}$ | 001#100 |
| CF | Unmarked Reversal | $\{{w}{w}^{R}\mid{w}\in{\{\texttt{0},\texttt{1}\}^{\ast}}\}$ | 001100 |
| CS | Marked Copy | $\{{w}\texttt{\#}{w}\mid{w}\in{\{\texttt{0},\texttt{1}\}^{\ast}}\}$ | 001#001 |
|  | Missing Duplicate | $\{({w}{w})_{i\rightarrow\texttt{\char 95\relax}}\mid{w}\in{\{\texttt{0},<br>\texttt{1}\}^{\ast}},1\leq i\leq 2|{w}|,({w}{w})_{i}=\texttt{1}\}$ | 1_011101 |
|  | Odds First | $\{a_{1}b_{1}\cdots a_{n}b_{n}a\texttt{\#}a_{1}\cdots a_{n}ab_{1}\cdots b_{n}\mid$ | 01010=00011 |
|  |  | $\qquad n\geq 0;a_{i},b_{i}\in\{\texttt{0},\texttt{1}\};a\in\{\texttt{0},<br>\texttt{1},{\varepsilon}\}\}$ |  |
|  | Binary Addition | $\{\langle{x}\rangle\texttt{0}^{i}\texttt{+}\langle{y}\rangle\texttt{0}^{j}<br>\texttt{=}\langle{x+y}\rangle\texttt{0}^{k}\mid x,y,i,j,k\in{\mathbb{Z}_{\geq 0<br>}}\}$ | 110+01=10100 |
|  | Binary Multiplication | $\{\langle{x}\rangle\texttt{0}^{i}\texttt{\texttimes}\langle{y}\rangle\texttt{0<br>}^{j}\texttt{=}\langle{xy}\rangle\texttt{0}^{k}\mid x,y,i,j,k\in{\mathbb{Z}_{<br>\geq 0}}\}$ | 110×0100=011 |
|  | Compute Sqrt | $\{\langle{x}\rangle\texttt{0}^{i}\texttt{=}\langle{\lfloor\sqrt{x}\rfloor}<br>\rangle\texttt{0}^{j}\mid x,i,j\in{\mathbb{Z}_{\geq 0}}\}$ | 01010=1100 |
|  | Bucket Sort | Sequence of integers in $\{1,\ldots,5\}$, then # and the sorted sequence. | 45134#13445 |

For each language, we sample a single, fixed training set of 10k examples with lengths in $[0,40]$. We run separate experiments with two different validation sets that are designed to address different scientific questions, each with 1k examples: a short validation set with string lengths in $[0,40]$, and a long validation set with string lengths in $[0,80]$. For any finite training set of strings, there are infinitely many valid ways of extrapolating to longer strings; we refer to the way that a neural network architecture disambiguates these possible solutions as its inductive bias. The short validation set reveals an architecture’s inductive bias in the absence of any disambiguating information about how it should generalize to longer lengths, as in the experiments of Delétang et al. (). The long validation set, on the other hand, does include longer strings, and so the model’s performance on strings that are longer than those in the training set modulates the learning rate schedule, early stopping schedule, and model selection. In this way, it is more in line with expressivity work that seeks to understand whether an architecture admits a certain solution at all, regardless of its inductive bias.

Each architecture consists of multiple layers; in all experiments, we use 5 layers. We automatically adjust the hidden vector size ${d}$ so that the number of parameters in each model is as close as possible to 64k, excluding extra parameters for language modeling and next symbol prediction heads. This ensures that all models are of comparable size across architectures and languages. For the simple RNN and LSTM, ${d}$ is the size of the hidden state vectors. For the transformer, ${d}$ is the model size $d_{\mathrm{model}}$. In the transformer, we use 8 attention heads in each layer, and we set the number of hidden units in each feedforward layer to $4{d}$. Every time we train a model, we randomly sample certain hyperparameters (Bergstra & Bengio, ), namely initial learning rate, minibatch size, and (when required) ${{\lambda}_{\mathrm{LM}}}$ and ${{\lambda}_{\mathrm{NS}}}$. For every combination of architecture, loss function variant, and type of validation set, we train 10 models. We use four loss function variants: recognition with(out) language modeling and with(out) next symbol prediction. Therefore, for every architecture and validation set, we train 40 models. For more details, see App. D.

## 4 Results

To test whether a model has learned the underlying recognition algorithm, our evaluation focuses on the ability to generalize to inputs that are longer than those seen in training (cf. Delétang et al., ). In Table 2, we show recognition accuracy on a test set with string lengths in $[0,500]$. It has 5,010 examples, or an average of 10 examples per length. Under “Inductive Bias,” we select the loss function with the highest mean accuracy on the test set from among the models trained on the short validation set, and we report this mean accuracy. Although we could select a single model based on performance on the validation set, this would result in noise due to the vagaries of model selection; we find that the mean accuracy that each architecture converges to when aggregated across multiple runs is more informative. Under “Expressivity,” we show the maximum test accuracy across all 40 models trained on the long validation set. See unabridged results and additional metrics in App. F.

**Table 2: Accuracy on a test set with strings in the length range $[0,500]$. The training data is in the length range $[0,40]$. “Inductive Bias” uses validation data in the length range $[0,40]$. We show mean accuracy across 10 runs for the loss function with the highest mean accuracy on the test set. “Expressivity” uses validation data in the length range $[0,80]$. We show maximum accuracy across all 10 runs of all 4 loss functions. “Tf” = transformer, “RNN” = simple RNN, “LSTM” = LSTM.**
|  | Inductive Bias | Expressivity |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Language | Tf | RNN | LSTM | Tf | RNN | LSTM |
| Even Pairs | 0.99 | 0.60 | 0.83 | 1.00 | 1.00 | 1.00 |
| Repeat 01 | 0.72 | 0.97 | 0.97 | 0.86 | 1.00 | 1.00 |
| Parity | 0.56 | 0.71 | 0.90 | 0.60 | 1.00 | 1.00 |
| Cycle Navigation | 0.84 | 0.93 | 0.90 | 0.93 | 0.93 | 0.93 |
| Modular Arithmetic | 0.69 | 1.00 | 0.98 | 0.88 | 1.00 | 1.00 |
| Dyck-$(2,3)$ | 0.70 | 0.95 | 0.91 | 0.82 | 1.00 | 0.98 |
| First | 0.98 | 0.80 | 0.94 | 1.00 | 1.00 | 1.00 |
| Majority | 0.97 | 0.90 | 0.95 | 1.00 | 0.95 | 1.00 |
| Stack Manipulation | 0.66 | 0.84 | 0.75 | 0.87 | 0.93 | 0.91 |
| Marked Reversal | 0.64 | 0.70 | 0.74 | 0.87 | 0.95 | 0.95 |
| Unmarked Reversal | 0.58 | 0.72 | 0.76 | 0.63 | 0.81 | 0.88 |
| Marked Copy | 0.63 | 0.76 | 0.69 | 0.86 | 0.95 | 0.95 |
| Missing Duplicate | 0.66 | 0.82 | 0.85 | 0.86 | 0.95 | 0.94 |
| Odds First | 0.59 | 0.79 | 0.67 | 0.86 | 0.95 | 0.96 |
| Binary Addition | 0.64 | 0.74 | 0.74 | 0.88 | 0.92 | 0.92 |
| Binary Multiplication | 0.70 | 0.74 | 0.78 | 0.92 | 0.92 | 0.92 |
| Compute Sqrt | 0.67 | 0.78 | 0.84 | 0.86 | 0.89 | 0.89 |
| Bucket Sort | 0.63 | 0.84 | 0.69 | 0.88 | 0.96 | 0.83 |

We find that the RNN and LSTM outperform the transformer in most cases. In the inductive bias experiments, the transformer outperforms the RNN and LSTM only on Even Pairs, First, and Majority; in the expressivity experiments, it is never the best, and it only outperforms the RNN on Bucket Sort. We do see differences based on a language’s sensitivity, i.e., the tendency that changing a bit in a string changes its label. Transformers struggle on high-sensitivity languages (Repeat 01, Parity) and do well on low-sensitivity languages (Even Pairs, First), in accordance with prior work (Hahn, ; Bhattamishra et al., ; Hahn & Rofin, ). The LSTM outperforms the RNN on some languages that involve long-range dependencies (Even Pairs, First), likely thanks to its memory cell. The LSTM can use its memory cell as a set of counters, which is useful for certain languages (Weiss et al., ); accordingly, we see that it outperforms the RNN on Majority, but surprisingly not on Bucket Sort. Although Yao et al. () gave a construction showing that the transformer can recognize bounded Dyck languages, we see that it struggles on Dyck-$(2,3)$.

Although it is possible, in principle, for a model’s inductive bias to differ substantially from its expressivity, we see a remarkable consistency between inductive bias and expressivity. As expected, all expressivity scores are higher than the corresponding inductive bias score. However, the ranking of the architectures remains the same between inductive bias and expressivity for almost all languages; it only changes slightly for Missing Duplicate and Odds First, and more noticeably for Bucket Sort.

Certain auxiliary loss terms do help in isolated cases: for example, next symbol prediction is crucial for the RNN to learn Even Pairs (Table 4). However, we see that no term has a consistently positive or negative impact across languages and architectures (Table 3). In fact, recognition alone is the most frequent best loss function, followed by next symbol prediction; loss functions that include a language modeling term help the least often. Remarkably, the RNN gets a mean accuracy of 100% in the inductive bias experiments for Modular Arithmetic, using only a recognition training objective.

**Table 3: The best loss functions, corresponding to the accuracy scores reported in Table 2. “R” = recognition; “LM” = language modeling; “NS” = next symbol prediction. No single loss function consistently results in the best performance; the most frequent winner is just R.**
|  | Inductive Bias | Expressivity |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Language | Tf | RNN | LSTM | Tf | RNN | LSTM |
| Even Pairs | R | R+LM+NS | R | R | R+NS | R |
| Repeat 01 | R | R+NS | R | R | R | R |
| Parity | R+NS | R+NS | R+NS | R+NS | R+LM | R |
| Cycle Navigation | R+LM+NS | R | R | R | R | R |
| Modular Arithmetic | R | R | R | R+NS | R | R |
| Dyck-$(2,3)$ | R+LM | R+LM+NS | R | R+NS | R+NS | R+NS |
| First | R+NS | R+LM | R+LM | R | R | R |
| Majority | R+LM | R+NS | R+NS | R+LM | R+LM+NS | R+LM+NS |
| Stack Manipulation | R | R+NS | R | R+LM+NS | R | R+LM |
| Marked Reversal | R+NS | R+NS | R | R+LM | R+LM | R+LM |
| Unmarked Reversal | R | R+NS | R+NS | R | R+NS | R+NS |
| Marked Copy | R+NS | R+LM | R | R+NS | R | R |
| Missing Duplicate | R+LM+NS | R | R | R+LM+NS | R+LM+NS | R+LM |
| Odds First | R | R | R | R+LM+NS | R | R+LM+NS |
| Binary Addition | R | R+NS | R | R+LM | R+NS | R+NS |
| Binary Multiplication | R+NS | R | R+NS | R+NS | R+LM | R+NS |
| Compute Sqrt | R | R | R | R | R | R |
| Bucket Sort | R | R+LM+NS | R | R+NS | R+NS | R+LM+NS |

We see accuracy ceilings in the expressivity results for Cycle Navigation, Binary Addition, Binary Multiplication, and Compute Sqrt. To investigate this, we looked at the examples with the highest cross-entropy. For Cycle Navigation, all architectures struggle on negative examples that have the right format but the wrong digit at the end; in contrast, the RNN and LSTM were able to get perfect accuracy on a related task in Delétang et al. (). For Binary Addition, the transformer and RNN/LSTM fail for different reasons. The RNN/LSTM only misclassify negative examples that have the right format but incorrect arithmetic, but the transformer also misclassifies positive examples and negative examples that have extra +, ×, or = symbols. The RNN and LSTM fail on Compute Sqrt for dissimilar reasons; the RNN sometimes accepts invalid formats.

How does treating neural networks as recognizers instead of string-to-string functions affect performance? The most comparable sets of experiments are those of Delétang et al. (, Tables B.1 and B.5) and our inductive bias experiments. Whereas they found that transformers struggle on Even Pairs and the RNN/LSTM excel, we see the opposite. Both our results show that transformers struggle on Parity. Whereas they showed that the RNN/LSTM can perfectly solve Cycle Navigation, our results show they cannot, perhaps because in our version, the model must additionally validate the format of the string rather than emit a single digit. We see the same model ranking on Stack Manipulation, but we see differences on Marked Reversal, Odds First, Binary Addition, Binary Multiplication, Compute Sqrt, and Bucket Sort. Notably, we see that the RNN overperforms in our experiments, possibly due to our use of dropout, multiple layers, and a different activation function.

In order to examine how the similarity of negative examples to positive examples affects classification difficulty, for Repeat 01 and Dyck-$(2,3)$, we plot the transformer’s recognition cross-entropy vs. the minimum edit distance between a string and any string in the language in Figure 1 (we do not plot the RNN and LSTM because they get almost 100% accuracy). Note that the number of edits ${K}$ performed in § 2.1 is an upper bound for, but necessarily equal to, the true edit distance. We give formal definitions and algorithms for computing edit distance in App. G. We do see that for both languages, the lower the edit distance is, the more the transformer struggles, particularly near 1 and 2 edits. This confirms that strings with few perturbations are indeed adversarial (cf. van der Poel et al., ), even when the training distribution is highly skewed toward few edits.

Figure: (a) Repeat 01

## 5 Conclusion

We have proposed a general method for training neural networks as recognizers of formal languages, filling a crucial gap between formal results and experiments designed to support them. Moreover, we have developed a new algorithm for length-constrained sampling of strings from regular languages that is much more efficient than standard methods. We provided results for RNNs, LSTMs, and transformers on a wide range of formal languages commonly used in prior work, showing that RNNs and LSTMs often outperform transformers. An interesting question to address in future work is why transformers perform so much better on natural language than on formal languages. Finally, we trained all our models using additional loss terms that have been previously used as a proxy for recognition and found that these do not improve model performance reliably. We have publicly released our datasets as a benchmark called FLaRe (Formal Language Recognition).

#### Acknowledgments

We thank Leonardo Nevali, Vésteinn Snæbjarnarson, and Paul Soulos for helpful discussions. Anej Svete is supported by the ETH AI Center Doctoral Fellowship. Josef Valvoda is funded by the Nordic Programme for Interdisciplinary Research Grant 105178 and the Danish National Research Foundation Grant no. DNRF169.

## Appendix A Details of perturbation sampling

We perform perturbation sampling as follows. Given a positive string ${w}\in{L}$ with $|{w}|\in{[{n_{\mathrm{min}}},{n_{\mathrm{max}}}]}$, we first sample a number of edits ${K}$ from a geometric distribution with a success probability of $p=\frac{1}{2}$. Note that this is highly skewed toward small ${K}$, ensuring that strings with few edits (i.e., similar to positive examples) are well-represented in the dataset. Then, ${K}$ times, we randomly apply an edit as follows. Let ${{w}^{\prime}}$ be the current edited version of ${w}$. We uniformly sample a type of edit: insertion, replacement, or deletion. We disallow insertion if it would increase $|{{w}^{\prime}}|$ beyond ${n_{\mathrm{max}}}$, and deletion if it would decrease it below ${n_{\mathrm{min}}}$. We disallow replacement if $|{\Sigma}|=1$. For each insertion, we uniformly sample an insertion position from $\{1,\ldots,|{{w}^{\prime}}|+1\}$ and a symbol to insert from ${\Sigma}$. For each replacement, we uniformly sample a replacement position ${i}$ from $\{1,\ldots,|{{w}^{\prime}}|\}$ and a new symbol from ${\Sigma}\setminus\{{{w}_{{i}}^{\prime}}\}$. For each deletion, we uniformly sample a deletion position from $\{1,\ldots,|{{w}^{\prime}}|\}$.

## Appendix B Details of length-constrained sampling for regular languages

### B.1 Implementation of the star operation

The closed-form solution to ${\bm{v}}^{{\leavevmode\hbox to5.58pt{\vbox to5.58pt{\pgfpicture\makeatletter
\hbox{\hskip 2.79033pt\lower-2.79033pt\hbox to0.0pt{\pgfsys@beginscope
\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{2.59033pt}{0.0pt}\pgfsys@curveto{2.59033pt}{1.43062pt}{
1.43062pt}{2.59033pt}{0.0pt}{2.59033pt}\pgfsys@curveto{-1.43062pt}{2.59033pt}{
-2.59033pt}{1.43062pt}{-2.59033pt}{0.0pt}\pgfsys@curveto{-2.59033pt}{-1.43062
pt}{-1.43062pt}{-2.59033pt}{0.0pt}{-2.59033pt}\pgfsys@curveto{1.43062pt}{-2.59
033pt}{2.59033pt}{-1.43062pt}{2.59033pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-1.75pt}{-1.62846pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\ast$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}}$ in the ${D}$^th-order counting semiring is as follows.

$$ $\displaystyle({\bm{v}}^{{\leavevmode\hbox to5.58pt{\vbox to5.58pt{\pgfpicture \makeatletter\hbox{\hskip 2.79033pt\lower-2.79033pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{2.59033pt}{0.0pt}\pgfsys@curveto{2.59033pt}{1.43062pt}{ 1.43062pt}{2.59033pt}{0.0pt}{2.59033pt}\pgfsys@curveto{-1.43062pt}{2.59033pt}{ -2.59033pt}{1.43062pt}{-2.59033pt}{0.0pt}\pgfsys@curveto{-2.59033pt}{-1.43062 pt}{-1.43062pt}{-2.59033pt}{0.0pt}{-2.59033pt}\pgfsys@curveto{1.43062pt}{-2.59 033pt}{2.59033pt}{-1.43062pt}{2.59033pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-1.62846pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\ast$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}})_{{i}}={\bm{v}}_{0}^{\ast}\mathbin{{ \otimes}}\left({\leavevmode\hbox to8.93pt{\vbox to8.93pt{\pgfpicture \makeatletter\hbox{\hskip 4.46367pt\lower-4.46367pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{4.26367pt}{0.0pt}\pgfsys@curveto{4.26367pt}{2.35478pt}{ 2.35478pt}{4.26367pt}{0.0pt}{4.26367pt}\pgfsys@curveto{-2.35478pt}{4.26367pt}{ -4.26367pt}{2.35478pt}{-4.26367pt}{0.0pt}\pgfsys@curveto{-4.26367pt}{-2.35478 pt}{-2.35478pt}{-4.26367pt}{0.0pt}{-4.26367pt}\pgfsys@curveto{2.35478pt}{-4.26 367pt}{4.26367pt}{-2.35478pt}{4.26367pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{${\bm{1}}$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}_{{i}}\mathbin{{\oplus}}\bigoplus_{{j}=1}^{{ i}}{\bm{v}}_{{j}}\mathbin{{\otimes}}({\bm{v}}^{{\leavevmode\hbox to5.58pt{ \vbox to5.58pt{\pgfpicture\makeatletter\hbox{\hskip 2.79033pt\lower-2.79033pt \hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt} \pgfsys@invoke{ }\nullfont\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{2.59033pt}{0.0pt}\pgfsys@curveto{2.59033pt}{1.43062pt}{ 1.43062pt}{2.59033pt}{0.0pt}{2.59033pt}\pgfsys@curveto{-1.43062pt}{2.59033pt}{ -2.59033pt}{1.43062pt}{-2.59033pt}{0.0pt}\pgfsys@curveto{-2.59033pt}{-1.43062 pt}{-1.43062pt}{-2.59033pt}{0.0pt}{-2.59033pt}\pgfsys@curveto{1.43062pt}{-2.59 033pt}{2.59033pt}{-1.43062pt}{2.59033pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-1.75pt}{-1.62846pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\ast$}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}}})_{{i}-{j}}\right)$ $\displaystyle(0\leq{i}\leq{D})$ (11) $$

A derivation is given by Snæbjarnarson et al. (). The elements $({\bm{v}}^{{\leavevmode\hbox to5.58pt{\vbox to5.58pt{\pgfpicture\makeatletter
\hbox{\hskip 2.79033pt\lower-2.79033pt\hbox to0.0pt{\pgfsys@beginscope
\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0}
\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}
{0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to
0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{2.59033pt}{0.0pt}\pgfsys@curveto{2.59033pt}{1.43062pt}{
1.43062pt}{2.59033pt}{0.0pt}{2.59033pt}\pgfsys@curveto{-1.43062pt}{2.59033pt}{
-2.59033pt}{1.43062pt}{-2.59033pt}{0.0pt}\pgfsys@curveto{-2.59033pt}{-1.43062
pt}{-1.43062pt}{-2.59033pt}{0.0pt}{-2.59033pt}\pgfsys@curveto{1.43062pt}{-2.59
033pt}{2.59033pt}{-1.43062pt}{2.59033pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-1.75pt}{-1.62846pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\ast$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}})_{{i}}$ can be computed in order of increasing ${i}$. The total time complexity is ${{O}({D}^{2})}$, since it involves ${{O}({D})}$ iterations, each of which takes ${{O}({D})}$ time. When the base semiring is the probability semiring, then ${\bm{v}}_{0}^{\ast}=\frac{1}{1-{\bm{v}}_{0}}$. When the base semiring is the log semiring, then ${\bm{v}}_{0}^{\ast}=\log\frac{1}{1-\exp{\bm{v}}_{0}}=-\log(1-\exp({\bm{v}}_{0}))$.

### B.2 Algorithms

Here, we describe our algorithms for sampling strings from regular languages in more detail. Given a DFA ${\mathcal{A}}$ and length range ${[{n_{\mathrm{min}}},{n_{\mathrm{max}}}]}$, we run the following steps once and for all for each language:

- 1.
convert ${\mathcal{A}}$ to a PDFA ${{\mathcal{A}}^{\prime}}$, then convert ${{\mathcal{A}}^{\prime}}$ to a WDFA ${{\mathcal{A}}_{{D}}}$ over the ${n_{\mathrm{max}}}$^th-order counting semiring with respect to the log semiring (Algorithm 1);
- 2.
push the weights of ${{\mathcal{A}}_{{D}}}$ to get a new WDFA ${{\mathcal{A}}^{\prime}_{{D}}}$ with respect to the real semiring (Algorithm 2), using the backward algorithm (Algorithm 3) and Lehmann’s algorithm (Algorithm 4);
- 3.
compute the subset of valid lengths ${N_{{{\mathcal{A}}^{\prime}}}}\subseteq{[{n_{\mathrm{min}}},{n_{\mathrm{max}}}]}$ (Algorithm 5);
- 4.
precompute the next symbol sets for each state (Algorithm 6).

Afterwards, we can sample strings as many times as desired as follows:

- 1.
uniformly sample a length ${n}$ from ${N_{{{\mathcal{A}}^{\prime}}}}$;
- 2.
sample a string of length ${n}$ using Algorithm 7, with next symbol sets.

Figure: Algorithm 1 Convert a partial DFA ${\mathcal{A}}$ to a WDFA ${{\mathcal{A}}_{{D}}}$ over the ${n_{\mathrm{max}}}$^th-order counting semiring with respect to the log semiring. This implicitly creates an intermediate PDFA ${{\mathcal{A}}^{\prime}}$ over the probability semiring with uniform probabilities.

Figure: Algorithm 2 Weight pushing on ${{\mathcal{A}}_{{D}}}$, where ${{\mathcal{A}}_{{D}}}$ is a WDFA over the ${D}$^th-order counting semiring with respect to the log semiring. Given ${{\mathcal{A}}_{{D}}}$, produce a WDFA ${{\mathcal{A}}^{\prime}_{{D}}}$ over the ${D}$^th-order counting semiring with respect to the probability semiring that is suitable for length-constrained sampling (Algorithm 7). Also return the allsum weight ${\bm{z}}$, which can be used to compute the set of valid lengths (Algorithm 5).

Figure: Algorithm 3 Backward algorithm on a WDFA ${{\mathcal{A}}}$ over the closed semiring $({{\mathbb{K}}},\oplus,\otimes,{\bm{0}},{\bm{1}})$. Time complexity: ${{O}({|{Q}|}^{3})}$.

Figure: Algorithm 4 Lehmann’s algorithm for inverting matrix $A\in{{\mathbb{K}}}^{N\times N}$ in the closed semiring $({{\mathbb{K}}},\oplus,\otimes,{\bm{0}},{\bm{1}})$. Time complexity: ${{O}(N^{3})}$.

Figure: Algorithm 5 Given an allsum weight ${\bm{z}}\in({\mathbb{R}}\cup\{-\infty\})^{{D}}$, a minimum length ${n_{\mathrm{min}}}$, and a maximum length ${n_{\mathrm{max}}}$, where ${D}\geq{n_{\mathrm{max}}}$, compute the set of valid lengths ${N_{{{\mathcal{A}}^{\prime}}}}$. The allsum weight ${\bm{z}}$ must be the second output of Algorithm 2.

Figure: Algorithm 6 Given a trimmed partial DFA ${\mathcal{A}}$, precompute the next symbol set for each state.

Figure: Algorithm 7 Sample a string of length ${n}$ from a WDFA ${{\mathcal{A}}^{\prime}_{{D}}}$ over the ${D}$^th-order counting semiring with respect to the probability semiring, where ${D}\geq{n}$. Also output a sequence of ${n}+1$ next symbol sets. The DFA ${{\mathcal{A}}^{\prime}_{{D}}}$ must be the first output of Algorithm 2, and Next must be the output of Algorithm 6.

### B.3 Explanation and details

Let us define a path in a WDFA as follows (cf. Def. 11).

###### Definition 7 .

For any WDFA ${{\mathcal{A}}}=({Q},{\Sigma},{\delta},{{q_{0}}},{\rho})$, a path is a sequence of states and transitions

$$ ${\pi}={r}_{0}\xrightarrow{{a}_{1}/{w}_{1}}{r}_{1}\cdots{r}_{{m}-1}\xrightarrow {{a}_{{m}}/{w}_{{m}}}{r}_{{m}}$ (12) $$

such that for all $i=0,\ldots,{m}-1$, ${r}_{i}\xrightarrow{{a}_{i+1}/{w}_{i+1}}{r}_{i+1}\in{\delta}$. We say that ${\pi}$ scans the string ${a}_{1}\cdots{a}_{{m}}$ and that the inner path weight of ${\pi}$ is

$$ ${\mathbf{w}_{\mathrm{I}}}({\pi})\mathrel{\stackrel{{\scriptstyle\textnormal{ def}}}{{=}}}\left(\bigotimes_{i=1}^{{m}}{w}_{i}\right).$ (13) $$

The path weight of ${\pi}$ is

$$ ${\mathbf{w}}({\pi})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}{ \mathbf{w}_{\mathrm{I}}}({\pi})\otimes{\rho}({r}_{{m}}).$ (14) $$

Lehmann’s algorithm (Lehmann, ) computes the total inner weight of all paths between all pairs of states. When a WDFA ${{\mathcal{A}}}$ contains cycles, this set of paths can be infinite, so a closed semiring with a defined ^∗ operation is required. We give Lehmann’s algorithm a table $A$ indexed by ${Q}\times{Q}$ such that

$$ $\displaystyle A[{{q}},{r}]$ $\displaystyle=\bigoplus_{{{q}}\xrightarrow{{a}/{w}}{r}\in{\delta}}{w}$ $\displaystyle({{q}},{r}\in{Q}).$ (15) $$

Let ${\Pi}({{\mathcal{A}}},{{q}}\rightsquigarrow{r})$ denote the (infinite) set of all paths starting at ${{q}}$ and ending at ${r}$ in ${{\mathcal{A}}}$. Lehmann’s algorithm computes a table $A^{\prime}$ indexed by ${Q}\times{Q}$ where

$$ $\displaystyle A^{\prime}[{{q}},{r}]$ $\displaystyle=\bigoplus_{{\pi}\in{\Pi}({{\mathcal{A}}},{{q}}\rightsquigarrow{r })}{\mathbf{w}_{\mathrm{I}}}({\pi})$ $\displaystyle({{q}},{r}\in{Q}).$ (16) $$

This allows us to compute the backward weight of each state ${{q}}$, or the total weight of accepting if starting in ${{q}}$.

###### Definition 8 .

For a WDFA ${{\mathcal{A}}}$, the backward weight ${\bm{\beta}}[{{q}}]$ is the sum of the weights of all paths from ${{q}}$ to any other state.

$$ ${\bm{\beta}}[{{q}}]\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}} \bigoplus_{\begin{subarray}{c}{r}\in{Q},\\ {\pi}\in{\Pi}({{\mathcal{A}}},{{q}}\rightsquigarrow{r})\end{subarray}}{\mathbf {w}}({\pi}).$ (17) $$

The quantity ${\bm{z}}={\bm{\beta}}[{{q_{0}}}]$ is the total weight assigned by ${{\mathcal{A}}}$ to strings in ${{\Sigma}^{\ast}}$.
We call it the allsum.

We use the backward weights for weight pushing. Weight pushing redistributes the weights of ${{\mathcal{A}}_{{D}}}$ so that the weight of each transition in ${{\mathcal{A}}^{\prime}_{{D}}}$ is the (infinite) sum of the weights of all paths in ${{\mathcal{A}}_{{D}}}$ that start with that transition and accept (Algorithm 2, line 7). Note that unlike the standard weight pushing algorithm (Mohri, ), we do not “normalize” the weights by left-multiplying them by ${\bm{\beta}}[{{q}}]^{-1}$, where, in general, $a^{-1}\in{{\mathbb{K}}}$ is the solution to the equation $a^{-1}\otimes a={\bm{1}}$. Although it is possible to compute this in the counting semiring by solving a system of linear equations, this would result in weights that add up elementwise to ${\leavevmode\hbox to8.93pt{\vbox to8.93pt{\pgfpicture\makeatletter\hbox{\hskip
4
.46367pt\lower-4.46367pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }
\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}
\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{
\pgfsys@beginscope\pgfsys@invoke{ }{
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{
}{}{}{{}\pgfsys@moveto{4.26367pt}{0.0pt}\pgfsys@curveto{4.26367pt}{2.35478pt}{
2.35478pt}{4.26367pt}{0.0pt}{4.26367pt}\pgfsys@curveto{-2.35478pt}{4.26367pt}{
-4.26367pt}{2.35478pt}{-4.26367pt}{0.0pt}\pgfsys@curveto{-4.26367pt}{-2.35478
pt}{-2.35478pt}{-4.26367pt}{0.0pt}{-4.26367pt}\pgfsys@curveto{2.35478pt}{-4.26
367pt}{4.26367pt}{-2.35478pt}{4.26367pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto
{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ }
}{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1
.0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{
rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }
\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{${\bm{1}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss}
\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}}
\lxSVG@closescope\endpgfpicture}}}=({\bm{1}},{\bm{0}},\ldots,{\bm{0}})$, which would not be useful for our purposes. Instead, we normalize them by dividing them elementwise, which we do implicitly when we apply $\mathrm{softmax}$ (Algorithm 2, line 8).

In our Python/PyTorch implementation, we precompute the elementwise *cumulative sum* of the transition weights, which we pass to the python.choices function as the argument cum_weights in order to avoid recomputing it every time we call it.

###### Definition 7 .

###### Definition 8 .

## Appendix C Details of neural network architectures

In this section, we describe each of the neural network architectures referenced in § 2.3 in more detail. Our implementations for all three architectures are based on those provided by PyTorch (Paszke et al., ). Each architecture consists of a configurable number of layers ${L}$. Each architecture uses an embedding matrix ${\bm{E}}$ to map each symbol ${{w}_{{t}}}$ of the input string to an embedding ${\bm{x}_{{t}}}={\bm{E}}_{{{w}_{{t}}}}$. The size of the embeddings is always the same as the size of the hidden state. In the following, $\textsc{Dropout}(\cdot)$ indicates the application of dropout.

### C.1 Simple RNN

Let ${\bm{h}^{({\ell})}_{{t}}}$ denote the hidden state of the ${\ell}$^th layer at timestep ${t}$. We apply dropout to the input embeddings, the hidden states between layers, and the hidden states output from the last layer (Zaremba et al., ). Our simple RNN architecture is defined as follows.

$$ $\displaystyle{\bm{h}^{(0)}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}{\bm{x}_{ {t}}}={\bm{E}}_{{{w}_{{t}}}}$ $\displaystyle(1\leq{t}\leq{n})$ (18a) $\displaystyle{\bm{h}^{({\ell})}_{0}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\tanh({ \bm{w}_{\mathrm{0}}^{({\ell})}})\quad$ $\displaystyle(1\leq{\ell}\leq{L})$ (18b) $\displaystyle{\cancel{\bm{h}}^{({\ell})}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\textsc{ Dropout}({\bm{h}^{({\ell})}_{{t}}})$ $\displaystyle(0\leq{\ell}\leq{L};0\leq{t}\leq{n})$ (18c) $\displaystyle{\bm{h}^{({\ell})}_{t}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\tanh({{ \bm{W}}^{({\ell})}_{\mathrm{h}}}\begin{bmatrix}{\cancel{\bm{h}}^{({\ell}-1)}_{ {t}}}\\ {\bm{h}^{({\ell})}_{{t}-1}}\end{bmatrix}+{{\bm{b}}^{({\ell})}_{\mathrm{h}}})\quad$ $\displaystyle(1\leq{\ell}\leq{L};1\leq{t}\leq{n})$ (18d) $\displaystyle{\bm{h}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}{\cancel{ \bm{h}}^{({L})}_{{t}}}$ $\displaystyle(0\leq{t}\leq{n})$ (18e) $$

Here, ${\bm{w}_{\mathrm{0}}^{({\ell})}}\in{\mathbb{R}}^{{d}}$ is a learned parameter, making the initial hidden state ${\bm{h}^{({\ell})}_{0}}$ of each layer learned. Note that PyTorch’s RNN implementation includes redundant bias parameters $b_{ih}$ and $b_{hh}$; we have modified it to use a single bias parameter ${{\bm{b}}^{({\ell})}_{\mathrm{h}}}$ per layer instead.

### C.2 LSTM

As with the simple RNN, we apply dropout following Zaremba et al. (). Our LSTM architecture is defined as follows. Let $\mathbin{{\odot}}$ denote elementwise multiplication.

$$ $\displaystyle{\bm{h}^{(0)}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}{\bm{x}_{ {t}}}={\bm{E}}_{{{w}_{{t}}}}$ $\displaystyle(1\leq{t}\leq{n})$ (19a) $\displaystyle{\bm{h}^{({\ell})}_{0}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\tanh({ \bm{w}_{\mathrm{0}}^{({\ell})}})\quad$ $\displaystyle(1\leq{\ell}\leq{L})$ (19b) $\displaystyle{\cancel{\bm{h}}^{({\ell})}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\textsc{ Dropout}({\bm{h}^{({\ell})}_{{t}}})$ $\displaystyle(0\leq{\ell}\leq{L};0\leq{t}\leq{n})$ (19c) $\displaystyle{\bm{i}^{({\ell})}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sigma({{ \bm{W}}^{({\ell})}_{\mathrm{i}}}\begin{bmatrix}{\cancel{\bm{h}}^{({\ell}-1)}_{ {t}}}\\ {\bm{h}^{({\ell})}_{{t}-1}}\end{bmatrix}+{{\bm{b}}^{({\ell})}_{\mathrm{i}}})\quad$ $\displaystyle(1\leq{\ell}\leq{L};1\leq{t}\leq{n})$ (19d) $\displaystyle{\bm{f}^{({\ell})}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sigma({{ \bm{W}}^{({\ell})}_{\mathrm{f}}}\begin{bmatrix}{\cancel{\bm{h}}^{({\ell}-1)}_{ {t}}}\\ {\bm{h}^{({\ell})}_{{t}-1}}\end{bmatrix}+{{\bm{b}}^{({\ell})}_{\mathrm{f}}})\quad$ $\displaystyle(1\leq{\ell}\leq{L};1\leq{t}\leq{n})$ (19e) $\displaystyle{\bm{g}^{({\ell})}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\tanh({{ \bm{W}}^{({\ell})}_{\mathrm{g}}}\begin{bmatrix}{\cancel{\bm{h}}^{({\ell}-1)}_{ {t}}}\\ {\bm{h}^{({\ell})}_{{t}-1}}\end{bmatrix}+{{\bm{b}}^{({\ell})}_{\mathrm{g}}})\quad$ $\displaystyle(1\leq{\ell}\leq{L};1\leq{t}\leq{n})$ (19f) $\displaystyle{\bm{o}^{({\ell})}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\sigma({{ \bm{W}}^{({\ell})}_{\mathrm{o}}}\begin{bmatrix}{\cancel{\bm{h}}^{({\ell}-1)}_{ {t}}}\\ {\bm{h}^{({\ell})}_{{t}-1}}\end{bmatrix}+{{\bm{b}}^{({\ell})}_{\mathrm{o}}})\quad$ $\displaystyle(1\leq{\ell}\leq{L};1\leq{t}\leq{n})$ (19g) $\displaystyle{\bm{c}^{({\ell})}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}{\bm{f}^{ ({\ell})}_{{t}}}\mathbin{{\odot}}{\bm{c}^{({\ell})}_{{t}-1}}+{\bm{i}^{({\ell}) }_{{t}}}\mathbin{{\odot}}{\bm{g}^{({\ell})}_{{t}}}\quad$ $\displaystyle(1\leq{\ell}\leq{L};1\leq{t}\leq{n})$ (19h) $\displaystyle{\bm{h}^{({\ell})}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}{\bm{o}^{ ({\ell})}_{{t}}}\mathbin{{\odot}}\tanh({\bm{c}^{({\ell})}_{{t}}})\quad$ $\displaystyle(1\leq{\ell}\leq{L};1\leq{t}\leq{n})$ (19i) $\displaystyle{\bm{c}^{({\ell})}_{0}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}{\bm{0}}\quad$ $\displaystyle(1\leq{\ell}\leq{L})$ (19j) $\displaystyle{\bm{h}_{{t}}}$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}{\cancel{ \bm{h}}^{({L})}_{{t}}}$ $\displaystyle(0\leq{t}\leq{n})$ (19k) $$

Here, ${\bm{w}_{\mathrm{0}}^{({\ell})}}\in{\mathbb{R}}^{{d}}$ is a learned parameter, making the initial hidden state ${\bm{h}^{({\ell})}_{0}}$ of each layer learned. Note that PyTorch’s LSTM implementation includes pairs of redundant bias parameters: $b_{ii}$ and $b_{hi}$, $b_{if}$ and $b_{hf}$, $b_{ig}$ and $b_{hg}$, and $b_{io}$ and $b_{ho}$. We have modified it so that each pair is replaced with a single bias parameter per layer.

### C.3 Transformer

We use PyTorch’s transformer implementation. Following Vaswani et al. (), we map input symbols to vectors of size ${d}$ with a scaled embedding layer and add sinusoidal positional encodings. Note that Delétang et al. () found that the type of positional encoding does not seem to have a large impact on the transformer performance, while Ruoss et al. () found that transformers with *randomized* positional encodings perform better on the same set of tasks. We use pre-norm instead of post-norm and apply layer norm to the output of the last layer. We use the same dropout rate throughout the transformer. We apply it in the same places as Vaswani et al. (), and, as implemented by PyTorch, we also apply it to the hidden units of feedforward sublayers and to the attention probabilities of scaled dot-product attention operations. We always use bos as the first input symbol to the transformer, which has been shown to improve performance on formal languages (Ebrahimi et al., ).

## Appendix D Details of experiments

Here, we provide additional details about the models and training procedures used in § 3.

Wherever dropout is applicable, we use a dropout rate of 0.1. For the transformer, when adjusting ${d}$ to accommodate the parameter budget, we round it to the nearest multiple of 8, as PyTorch requires it to be a multiple of the number of attention heads. We use Xavier uniform initialization (Glorot & Bengio, ) to initialize the fully-connected layers in the recognition and next symbol prediction heads. For layer norm, we initialize weights to 1 and biases to 0. We initialize all other parameters by sampling uniformly from $[-0.1,0.1]$.

For each epoch, we randomly shuffle the training set and group strings of similar lengths into the same minibatch, enforcing an upper limit of ${B}$ symbols per batch, including padding, bos, and eos symbols. We train each model by minimizing the loss function defined in § 2.4 using Adam (Kingma & Ba, ). We clip gradients with a threshold of 5 using $L^{2}$ norm rescaling. We take a checkpoint every 10k examples (i.e., at the end of each epoch), at which point we evaluate the model on the validation set and update the learning rate and early stopping schedules. We multiply the learning rate by 0.5 after 5 checkpoints of no decrease in recognition cross-entropy on the validation set, and we stop early after 10 checkpoints of no decrease. We select the checkpoint with the lowest recognition cross-entropy on the validation set when reporting results. We train for a maximum of 1k epochs.

Every time we train a model, we randomly sample a number of hyperparameters. We randomly sample the batch size ${B}$ from a uniform distribution over $[128,4096]$. We randomly sample the initial learning rate from a log-uniform distribution over $[0.0001,0.01]$. We randomly sample the loss term coefficients ${{\lambda}_{\mathrm{LM}}}$ and ${{\lambda}_{\mathrm{NS}}}$, when they are needed, from a log-uniform distribution over $[0.01,10]$.

Our experiments are small enough that we are able to run them in CPU mode, without GPU acceleration.

## Appendix E Details of languages

Here, we give more detailed descriptions of the languages listed in Table 1. For each language, we indicate whether it is regular (R), deterministic context-free (DCF), context-free (CF), or context-sensitive (CS); this also indicates that the language does not belong to previous classes.

##### Even Pairs (R).

Binary strings where the total number of 01 and 10 substrings is even. Equivalently, this is the language of binary strings that have the same first and last symbol, or strings with fewer than two symbols. This is a low-sensitivity language, since only changing the first or last bit changes membership. This language corresponds to the Even Pairs task of Delétang et al. (). This language is given as an example in Sipser (, Chapter 1.4); see also Example 1.11.

| Positive Examples | Negative Examples |
| --- | --- |
| ${\varepsilon}$<br>0<br>11<br>010100<br>11101101 | 01<br>10100<br>100110 |

##### Repeat 01 (R).

The string 01 repeated any number of times. This is a high-sensitivity language, since changing any bit changes membership.

| Positive Examples | Negative Examples |
| --- | --- |
| ${\varepsilon}$<br>01<br>0101 | 0<br>10101<br>011001 |

##### Parity (R).

Binary strings with an odd number of 1s. This is a high-sensitivity language, since changing any bit changes membership. It appears commonly in the theoretical literature on the representational capacity of transformers since the high sensitivity makes it difficult for transformers to represent the language (Hahn, ; Chiang & Cholak, ; Bhattamishra et al., ; ; Hahn & Rofin, ). However, it can easily be learned by RNNs and scrathpad-augmented transformers (Liu et al., ; Hahn & Rofin, ). This language corresponds to the Parity Check task of Delétang et al. ().

| Positive Examples | Negative Examples |
| --- | --- |
| 1<br>01011 | ${\varepsilon}$<br>101110 |

##### Cycle Navigation (R).

Suppose an agent is on a 5-state cycle, numbered from 0 to 4, starting at state 0. Strings in this language consist of a sequence of moves—move right (>), move left (<), or stay (=)—followed by the integer corresponding to the state reached after executing the sequence of moves. This language corresponds to the Cycle Navigation task of Delétang et al. ().

| Positive Examples | Negative Examples |
| --- | --- |
| 0<br>>=>><2<br><=<>=<3<br>>=>==<1 | 3<br>>=>><4<br><=<>=<<br>4=31< |

##### Modular Arithmetic (R).

An expression involving the digits $\{\texttt{0},\ldots,\texttt{4}\}$ and the operators $\{\texttt{+},\texttt{-},\texttt{\texttimes}\}$, then the result of evaluating that expression in modulo 5 arithmetic. All operators are left-associative infix operators with equal precedence. Note that this is different from the Modular Arithmetic (Simple) task of Delétang et al. (), which gives higher precedence to ×, which would result in a more complex DFA.

| Positive Examples | Negative Examples |
| --- | --- |
| 3=3<br>2+4+0-3=3<br>1-3×2=1 | ${\varepsilon}$<br>1=4<br>2+4+0-3=2<br>1-3×2=0<br>-1=4<br>=×3+-0+ |

##### Dyck- ( 2 , 3 ) 2 3 (2,3) ( 2 , 3 ) (R).

In general, the language Dyck-$(k,m)$ contains strings of balanced brackets of $k$ types with a maximum nesting depth of $m$. We specifically test $k=2$ and $m=3$. Bounded Dyck languages have been studied for RNNs (Hewitt et al., ) and transformers (Ebrahimi et al., ; Bhattamishra et al., ; Yao et al., ; Wen et al., ) both in terms of (empirical) representational capacity as well as interpretability. These languages are star-free (Strobl et al., ), and the language Dyck-$(k,m)$ has a dot-depth of $m$. In this sense, bounded Dyck languages span the (infinite) hierarchy of star-free languages, which have been closely linked to transformers (Yang et al., ). Bhattamishra et al. () argue that transformers struggle to learn languages beyond dot-depth 1.

| Positive Examples | Negative Examples |
| --- | --- |
| ${\varepsilon}$<br>([])<br>[()]<br>([()]())[()] | ](]))[(]<br>([]<br>[(])<br>([(())]())[()]<br>)][( |

##### First (R).

Binary strings that start with 1. This is a low-sensitivity language, since only changing the first bit changes membership. More concretely, it is a special case of a $1$-Parity language, i.e., the Parity language restricted to a single position (Hahn & Rofin, ). Bhattamishra et al. () refer to such functions as $1$-Sparse functions. Transformers have been shown to learn such sparse functions well (Edelman et al., ; Bhattamishra et al., ; Hahn & Rofin, ).

| Positive Examples | Negative Examples |
| --- | --- |
| 1<br>101110 | ${\varepsilon}$<br>0<br>0111010 |

##### Majority (DCF).

Binary strings with more 1s than 0s. It is between low- and high-sensitivity, since strings membership flips only when the number of 1s equals half of the string length. This language has been studied by Pérez et al. (); Merrill et al. (); Bhattamishra et al. (); Strobl (). Although it lies higher on the Chomsky hierarchy than the sensitive Parity and Even Pairs, its lower sensitivity makes it easier for transformers to learn (Bhattamishra et al., ; Hahn & Rofin, ).

| Positive Examples | Negative Examples |
| --- | --- |
| 1<br>110<br>011011010 | ${\varepsilon}$<br>001<br>1100 |

We generate a positive example by first sampling a length ${n}$ uniformly from $[\max({n_{\mathrm{min}}},1),{n_{\mathrm{max}}}]$, then a number of 1s $c_{\texttt{1}}$ uniformly from $[\lfloor{n}/2\rfloor+1,{n}]$. We compute the number of 0s as $c_{\texttt{0}}={n}-c_{\texttt{1}}$. We return a random permutation of the string $\texttt{0}^{c_{\texttt{0}}}\texttt{1}^{c_{\texttt{1}}}$.

To test whether a string is in the language, we simply return whether the number of 1s is greater than the number of 0s.

To compute ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$, we always include $\{\texttt{0},\texttt{1}\}$, and we add eos if ${{w}_{<{t}}}\in{L}$.

##### Stack Manipulation (DCF).

Each string starts with a binary string representing the contents of a stack, written bottom to top. Then, there is a sequence of operations to be performed on the stack, where popping is indicated with pop, pushing 0 is indicated with the string push 0, and pushing 1 is indicated with the string push 1. Popping from an empty stack is not allowed. Finally, there is a =, and the contents of the resulting stack are written top to bottom (if the stack were not reversed, this language would not be context-free). This language corresponds to the Stack Manipulation task of Delétang et al. (); note that their version treats popping from an empty stack as a no-op.

| Positive Examples | Negative Examples |
| --- | --- |
| =<br>01011 pop push 0 push 1=101010<br>11 pop push 0=01<br>01 pop pop push 0 push 1=10 | ${\varepsilon}$<br>01011 pop push 0 push 1=010101<br>11= pop push =01<br>01 pop pop pop push 0 push 1=10 |

To generate a positive example, we first sample the number of original stack symbols $n_{\mathrm{stack}}$ and then the number of push operations $n_{\mathrm{push}}$. Let $n_{\mathrm{pop}}$ be the number of pop operations. Note that the length of the resulting stack is $n_{\mathrm{stack}}+n_{\mathrm{push}}-n_{\mathrm{pop}}$, and the total length of the string is ${n}=n_{\mathrm{stack}}+2n_{\mathrm{push}}+n_{\mathrm{pop}}+1+n_{\mathrm{push}}
-n_{\mathrm{pop}}=2n_{\mathrm{stack}}+3n_{\mathrm{push}}+1$. The minimum value of $n_{\mathrm{push}}$ is 0. So, following simple algebra, we sample $n_{\mathrm{stack}}$ uniformly from $\left[\max(0,\lceil\frac{{n_{\mathrm{min}}}-1}{2}\rceil),\lfloor\frac{{n_{
\mathrm{max}}}-1}{2}\rfloor\right]$, and then we sample $n_{\mathrm{push}}$ uniformly from $\left[\max(0,\lceil\frac{{n_{\mathrm{min}}}-2n_{\mathrm{stack}}-1}{3}\rceil),
\lfloor\frac{{n_{\mathrm{max}}}-2n_{\mathrm{stack}}-1}{3}\rfloor\right]$. We sample an initial stack uniformly from $\{\texttt{0},\texttt{1}\}^{n_{\mathrm{stack}}}$. We then sample a sequence of operations while counting the number of pushes generated so far and simulating the stack actions. At each step, we sample an action uniformly from $\{{\framebox{\raisebox{0.0pt}[6.45831pt][1.07639pt]{$\textsc{push}$}}},{
\framebox{\raisebox{0.0pt}[6.45831pt][1.07639pt]{$\textsc{pop}$}}}\}$. We disallow pop if the stack is empty. If we sample push, we uniformly sample a pushed symbol from $\{\texttt{0},\texttt{1}\}$. We stop when we sample a push and $n_{\mathrm{push}}$ pushes have already been generated (this allows pop to occur after the last push). We then add = and the resulting stack.

To test whether a string is in the language, we scan it from left to right while checking that it has the right format and simulating the stack actions. We push all 0s and 1s at the beginning to a stack. We scan push and pop commands and perform them on the stack, until we scan =. We reject if push is not followed by 0 or 1, or if we attempt to pop from an empty stack. We then check that the rest of the string is equal to the resulting stack.

To compute ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$, we scan ${w}$ in order of increasing ${t}$ while simulating the stack actions, as above. If ${{w}_{<{t}}}$ ends within the initial stack part, we set it to $\{\texttt{0},\texttt{1},{\framebox{\raisebox{0.0pt}[6.45831pt][1.07639pt]{$
\textsc{pop}$}}},{\framebox{\raisebox{0.0pt}[6.45831pt][1.07639pt]{$\textsc{
push}$}}},\texttt{=}\}$. If ${{w}_{<{t}}}$ ends with pop, or a 0 or 1 after a push, we include =, and we include push if fewer than $n_{\mathrm{push}}$ pushes have been seen, and we include pop if the stack is not empty. If ${{w}_{<{t}}}$ ends with push, we set it to $\{\texttt{0},\texttt{1}\}$. There is only one correct string for the final stack; if ${{w}_{<{t}}}$ ends within the final stack part, we set it to $\{\texttt{0}\}$, $\{\texttt{1}\}$, or $\{{\textsc{eos}}\}$ depending on what the correct string is.

##### Marked Reversal (DCF).

Strings of the form ${u}\texttt{\#}{u}^{R}$, where ${u}$ is a binary string. This is a classic example of a deterministic context-free language (Hopcroft et al., ). This corresponds to the Reverse String task of Delétang et al. (), which explicitly marks the point when a model should stop reading ${w}$ and start generating ${w}^{R}$. This is a high-sensitivity language, since changing any symbol changes membership. DuSell & Chiang (; ; ; ) showed that LSTM and transformer language models struggle on this language compared to stack-augmented neural networks.

| Positive Examples | Negative Examples |
| --- | --- |
| #<br>011#110<br>0#0<br>01001#10010 | ${\varepsilon}$<br>011#101101<br>011#11<br>0#11#110#<br>011110 |

Let ${m}=|{u}|$. To generate a positive example, we first sample ${m}$ uniformly from $[\lceil\max(0,\frac{{n_{\mathrm{min}}}-1}{2})\rceil,\lfloor\frac{{n_{\mathrm{
max}}}-1}{2}\rfloor]$, then we sample ${u}$ uniformly from $\{\texttt{0},\texttt{1}\}^{{m}}$. We then return the string ${u}\texttt{\#}{u}^{R}$. Notice that the string is guaranteed to be in the desired length range.

To test whether a string is in the language, we check whether there is a single #, and whether the substring after the marker is the reverse of the substring before the marker.

To compute ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$, we scan ${w}$ in order of increasing ${t}$. If ${{w}_{<{t}}}$ ends within the first half (before the # symbol), then the set of next valid symbols is set to $\{\texttt{0},\texttt{1},\texttt{\#}\}$. The rest of the string is deterministic based on ${w}$, and we use one of $\{\texttt{0}\}$, $\{\texttt{1}\}$, or $\{{\textsc{eos}}\}$ as needed.

##### Unmarked Reversal (CF).

Strings of the form ${u}{u}^{R}$, where ${u}$ is a binary string. This is a classic example of a nondeterministic context-free language (Hopcroft et al., , p. 254). DuSell & Chiang (; ; ) showed that LSTM and transformer language models struggle on this language compared to stack-augmented neural networks.

| Positive Examples | Negative Examples |
| --- | --- |
| ${\varepsilon}$<br>011110<br>00<br>0100110010 | 1<br>01110<br>011100<br>11110 |

Let ${m}=|{u}|$. To generate a positive example, we first sample ${m}$ uniformly from $[\lceil\frac{{n_{\mathrm{min}}}}{2}\rceil,\lfloor\frac{{n_{\mathrm{max}}}}{2}\rfloor]$, then we sample ${u}$ uniformly from $\{\texttt{0},\texttt{1}\}^{{m}}$. We then return the string ${u}{u}^{R}$.

To test whether a string is in the language, we check whether the length of the string is even and whether the second half is the reverse of the first half.

To compute ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$, we always include $\{\texttt{0},\texttt{1}\}$, and we include eos if ${{w}_{<{t}}}\in{L}$.

##### Marked Copy (CS).

Strings of the form ${u}\texttt{\#}{u}$, where ${u}$ is a binary string. This is a classic example of a mildly context-sensitive language (Joshi, ). This is a high-sensitivity language, since changing any symbol changes membership. This language is somewhat similar to the Duplicate String task of Delétang et al. (), which requires a model to read ${u}$ and output ${u}{u}$, which is more like the language $\{{u}\texttt{\#}{u}{u}\mid{u}\in{\{\texttt{0},\texttt{1}\}^{\ast}}\}$. Jelassi et al. () showed both theoretically and empirically that transformers are better at copying than modern recurrent architectures, since the latter are constrained by their hidden state bottleneck. This language is also analogous to the String Equality task in Bhattamishra et al. (), who also found that transformers outperform both modern and classic recurrent architectures. DuSell & Chiang () showed that LSTM language models struggle on this task compared to certain stack-augmented LSTMs.

| Positive Examples | Negative Examples |
| --- | --- |
| #<br>011#011<br>0#0<br>01001#01001 | ${\varepsilon}$<br>011#01<br>011011<br>0##11#01#1 |

We generate positive examples, test membership, and compute ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$ similarly to Marked Reversal.

##### Missing Duplicate (CS).

This language contains strings of the form ${u}{u}$, where ${u}$ is a binary string, but where one of the symbols in ${u}{u}$ has been replaced with _, and where the replaced symbol was a 1. This language corresponds to the Missing Duplicate task of Delétang et al. (), which does not explicitly mark the boundary between the two ${u}$s.

| Positive Examples | Negative Examples |
| --- | --- |
| _1<br>001000_0<br>11_01001110100 | ${\varepsilon}$<br>00100_10<br>11101001110100<br>_01_1_00 |

To generate a positive example, we sample ${m}=|{u}|$ uniformly from $[\max(1,\lceil\frac{{n_{\mathrm{min}}}}{2}\rceil),\lfloor\frac{{n_{\mathrm{max
}}}}{2}\rfloor]$. To ensure that ${u}$ contains at least one 1, we first sample a string ${u}^{\prime}$ uniformly from $\{\texttt{0},\texttt{1}\}^{{m}}$, then we uniformly at random replace one of its symbols with 1 to get ${u}$. We uniformly at random pick one of the 1s in ${u}{u}$ and replace it with _ to get the final string ${w}$.

To test whether a string is in the language, we check if its length is even and if it contains exactly one _. We replace the _ with 1 and check if the first half is the same as the second half.

To compute ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$, if ${{w}_{<{t}}}$ does not contain _, we set it to $\{\texttt{0},\texttt{1},\texttt{\char 95\relax}\}$. If ${{w}_{<{t}}}$ does contain _, we include $\{\texttt{0},\texttt{1}\}$, and we add eos if ${{w}_{<{t}}}\in{L}$.

##### Odds First (CS).

A binary string ${u}$, then #, then a string ${v}={u}_{\mathrm{odd}}{u}_{\mathrm{even}}$, where ${u}_{\mathrm{odd}}$ is all the symbols in ${u}$ at odd positions, and ${u}_{\mathrm{even}}$ is all the symbols in ${u}$ at even positions. In other words, strings in this language are of the form ${u}^{\prime}{a}\texttt{\#}{u}^{\prime}_{\mathrm{odd}}{a}{u}_{\mathrm{even}}$, where ${u}^{\prime}$ is the perfect shuffle of ${u}^{\prime}_{\mathrm{odd}},{u}_{\mathrm{even}}\in{\{\texttt{0},\texttt{1}\}^{
\ast}}$, and ${a}\in\{\texttt{0},\texttt{1},{\varepsilon}\}$. This corresponds to the Odds First language of Delétang et al. ().

| Positive Examples | Negative Examples |
| --- | --- |
| #<br>1#1<br>010101#000111<br>0101010#0000111<br>10011011#10110101 | ${\varepsilon}$<br>010101#000110<br>010101000111<br>0#1## |

To generate a positive example, we first sample a string ${u}$ as in Marked Reversal. We then return ${u}\texttt{\#}{u}_{\mathrm{odd}}{u}_{\mathrm{even}}$.

To test whether a string is in the language, we first check whether it contains exactly one #. We let the string to the left of # be ${u}$, and we check if the string to the right is equal to ${u}_{\mathrm{odd}}{u}_{\mathrm{even}}$.

To compute ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$, if ${{w}_{<{t}}}$ ends before #, we set it to $\{\texttt{0},\texttt{1},\texttt{\#}\}$. The rest of the string is deterministic based on the value of ${u}$, and we use either $\{\texttt{0}\}$, $\{\texttt{1}\}$, or $\{{\textsc{eos}}\}$ to match ${u}_{\mathrm{odd}}{u}_{\mathrm{even}}$.

##### Binary Addition (CS).

Strings of the form ${u}_{x}\texttt{+}{u}_{y}\texttt{=}{u}_{z}$, where ${u}_{x},{u}_{y},{u}_{z}$ are little-endian binary encodings (possibly with trailing 0s) of integers $x,y,z\in{\mathbb{Z}_{\geq 0}}$, and $x+y=z$. The number 0 is encoded as 0, but not ${\varepsilon}$. This language corresponds to the Binary Addition task of Delétang et al. ().

| Positive Examples | Negative Examples |
| --- | --- |
| 0+0=0<br>001+1=101<br>001000+100=1010000<br>101+01011=11111<br>1+11=001 | ${\varepsilon}$<br>+=<br>001+1=011<br>100+1=101<br>0011101<br>=0+10=1+ |

We generate a positive example as follows. Note that, in general, binary encodings must have at least one bit, and a binary string of length ${m}$ can only encode integers in $[0,2^{{m}}-1]$. Let $n_{x}=|{u}_{x}|,n_{y}=|{u}_{y}|,n_{z}=|{u}_{z}|$. We first sample $n_{x},n_{y},n_{z}$, then we sample $x,y,z$ that satisfy $x\leq 2^{n_{x}}-1,y\leq 2^{n_{y}}-1,z=x+y\leq 2^{n_{z}}-1$. We sample a total string length ${n}$ uniformly from $[\max(5,{n_{\mathrm{min}}}),{n_{\mathrm{max}}}]$. Let $n_{x}=n^{\prime}_{x}+1,n_{y}=n^{\prime}_{y}+1,n_{z}=n^{\prime}_{z}+1$. We sample $n^{\prime}_{x},n^{\prime}_{y},n^{\prime}_{z}$ using a Dirichlet distribution with parameters $(1,1,1)$ so that $n_{x},n_{y},n_{z}$ are equally distributed and always sum to ${n}-2$. If $n_{y}>n_{x}$, we swap them, so that $n_{x}\leq n_{y}$; this will make the distribution over $x$ less restrictive on $y$, because it reduces cases where $x$ is so large that few $y$ can be chosen that satisfy the constraint on $z$. We sample $x$ uniformly from $[0,\min(2^{n_{x}}-1,2^{n_{z}}-1)]$, and $y$ uniformly from $[0,\min(2^{n_{y}}-1,2^{n_{z}}-1-x)]$. We encode $x,y,z=x+y$ as ${u}_{x},{u}_{y},{u}_{z}$, padding them with 0s as needed to reach lengths of exactly $n_{x},n_{y},n_{z}$. In order to avoid bias in the distribution of $x$ vs. $y$, with probability $\frac{1}{2}$, we swap ${u}_{x}$ and ${u}_{y}$. We return ${u}_{x}\texttt{+}{u}_{y}\texttt{=}{u}_{z}$.

To test whether a string is in the language, we simply check that it has the expected format, parse $x,y,z$, and check that $x+y=z$.

To compute ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$, we scan ${w}$ in order of increasing ${t}$. Before ${u}_{x}$, we set it to $\{\texttt{0},\texttt{1}\}$. After any symbol in ${u}_{x}$, we set it to $\{\texttt{0},\texttt{1},\texttt{+}\}$. Similarly, before ${u}_{y}$, we set it to $\{\texttt{0},\texttt{1}\}$, and after any symbol in ${u}_{y}$, we set it to $\{\texttt{0},\texttt{1},\texttt{=}\}$. After =, we must deterministically generate $\langle{z}\rangle$, so we set it to $\{\texttt{0}\}$ or $\{\texttt{1}\}$ as needed. After $\langle{z}\rangle$, and after any trailing 0s, we set it to $\{\texttt{0},{\textsc{eos}}\}$.

##### Binary Multiplication (CS).

Strings of the form ${u}_{x}\texttt{\texttimes}{u}_{y}\texttt{=}{u}_{z}$, where, like Binary Addition, ${u}_{x},{u}_{y},{u}_{z}$ are binary encodings of integers $x,y,z\in{\mathbb{Z}_{\geq 0}}$, and $xy=z$. This language corresponds to the Binary Multiplication task of Delétang et al. ().

| Positive Examples | Negative Examples |
| --- | --- |
| 0×0=0<br>001×11=0011<br>001000×1100=0011000<br>1001×0111=0111111 | ${\varepsilon}$<br>×=<br>001×11=1011<br>100×1010=0101000<br>0011101<br>=0×10=1× |

We generate a positive example similarly to Binary Addition. We first sample $n_{x},n_{y},n_{z}$, then we sample $x,y,z$ that satisfy $x\leq 2^{n_{x}}-1,y\leq 2^{n_{y}}-1,z=xy\leq 2^{n_{z}}-1$. We sample ${n},n_{x},n_{y},n_{z}$ in the same way as Binary Addition, except the Dirichlet distribution has parameters $(1,1,2)$. This means $n_{z}$ tends to be twice as big as $n_{x}$ or $n_{y}$; we do this because the number of bits required for $xy$ is approximately the sum of the bits required for $x$ and $y$. Note that guaranteeing $n_{x}\leq n_{y}$ is particularly important here for a good distribution of $y$. We sample $x$ uniformly from $[0,2^{n_{x}}-1]$. If $x>0$, we sample $y$ uniformly from $[0,\min(2^{n_{y}}-1,\lfloor\frac{2^{n_{z}}-1}{x}\rfloor)]$. Otherwise, we sample $y$ uniformly from $[0,2^{n_{y}}-1]$. The rest is like Binary Addition, except we return ${u}_{x}\texttt{\texttimes}{u}_{y}\texttt{=}{u}_{z}$.

We test whether a string is in the language and compute ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$ like Binary Addition, except we use $xy=z$ instead of $x+y=z$, and × instead of +.

##### Compute Sqrt (CS).

Strings of the form ${u}_{x}\texttt{=}{u}_{z}$, where, similarly to Binary Addition and Binary Multiplication, ${u}_{x},{u}_{z}$ are binary encodings of integers $x,z\in{\mathbb{Z}_{\geq 0}}$, and $\lfloor\sqrt{x}\rfloor=z$. This language corresponds to the Compute Sqrt task of Delétang et al. ().

| Positive Examples | Negative Examples |
| --- | --- |
| 0=0<br>011=11<br>00101=001<br>00101000=00100 | ${\varepsilon}$<br>=<br>011=01<br>0=11=1 |

We generate a positive example similarly to Binary Addition and Binary Multiplication. Let $n_{x}=|{u}_{x}|,n_{z}=|{u}_{z}|$. We first sample $n_{x},n_{z}$, then we sample $x,z$ that satisfy $x\leq 2^{n_{x}}-1,z=\lfloor\sqrt{x}\rfloor\leq 2^{n_{z}}-1$. We sample a total string length ${n}$ uniformly from $[\max(3,{n_{\mathrm{min}}}),{n_{\mathrm{max}}}]$. Let $n_{x}=n^{\prime}_{x}+1,n_{z}=n^{\prime}_{z}+1$. We sample $n^{\prime}_{x},n^{\prime}_{z}$ using a Dirichlet distribution with parameters $(2,1)$, so that $n_{x}$ and $n_{z}$ sum to ${n}-2$, and $n_{x}$ tends to be twice as big as $n_{z}$. We do this because the number of bits required for $\lfloor\sqrt{x}\rfloor$ is about half of that required for $x$. We sample $x$ uniformly from $[0,\min(2^{n_{x}}-1,2^{2n_{z}}-1)]$. We encode $x,z=\lfloor\sqrt{x}\rfloor$ as ${u}_{x},{u}_{z}$, padding them with 0s as needed to reach lengths of exactly $n_{x},n_{z}$. We return ${u}_{x}\texttt{=}{u}_{z}$.

To test whether a string is in the language, we simply check that it has the expected format, parse $x,z$, and check that $\lfloor\sqrt{x}\rfloor=z$.

To compute ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$, we scan ${w}$ in order of increasing ${t}$. Before ${u}_{x}$, we set it to $\{\texttt{0},\texttt{1}\}$. After any symbol in ${u}_{x}$, we set it to $\{\texttt{0},\texttt{1},\texttt{=}\}$. After =, we must deterministically generate $\langle{z}\rangle$, so we set it to $\{\texttt{0}\}$ or $\{\texttt{1}\}$ as needed. After $\langle{z}\rangle$, and after any trailing 0s, we set it to $\{\texttt{0},{\textsc{eos}}\}$.

##### Bucket Sort (CS).

A string ${u}\in{\{\texttt{1},\ldots,\texttt{5}\}^{\ast}}$, then #, then the digits of ${u}$ in sorted order. Note that it is only necessary to keep track of the counts of each type of digit to recognize this language. This language corresponds to the Bucket Sort task of Delétang et al. ().

| Positive Examples | Negative Examples |
| --- | --- |
| #<br>4512345#1234455<br>31204124#01122344<br>41#14 | ${\varepsilon}$<br>4512345#1434255<br>31204124#0112<br>1#2##12 |

Let ${m}=|{u}|$. To generate a positive example, we first sample ${m}$ as in Marked Reversal, then we sample ${u}$ uniformly from $\{\texttt{1},\ldots,\texttt{5}\}^{{m}}$. We then compute the sorted string ${u}^{\prime}$ and return the string ${u}\texttt{\#}{u}^{\prime}$.

To test whether a string is in the language, we check whether there is a single #, and whether the substring after the marker is the bucket sort of the substring before the marker.

To compute ${{\textsc{Next}}_{{L}}({{w}_{<{t}}})}$, we scan ${w}$ in order of increasing ${t}$. If ${{w}_{<{t}}}$ ends within the first half (before the # symbol), then the set of next valid symbols is set to $\{\texttt{1},\ldots,\texttt{5},\texttt{\#}\}$. The rest of the string is deterministic based on the value of ${u}$, and we use one of $\{\texttt{1}\},\ldots,\{\texttt{5}\},\{{\textsc{eos}}\}$ as needed.

## Appendix F Full results

We show unabridged versions of the results from § 4 for all languages in Tables 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 and 21
. Every row is aggregated across 10 runs. The scores shown in each row are of the model with the lowest recognition cross-entropy on the validation set (this value is shown under “Val. CE”; lower is better). All columns are accuracy scores except for “Val. CE.” We show the best score in each column in bold.

Here, we refer to the test set used in § 4, which has lengths in $[0,500]$, as the long test set. We also report accuracy on a short test set of 1k held-out examples with lengths in $[0,40]$. The short test set only includes examples that do not occur in the training set, short validation set, or long validation set; it tests how well a model generalizes to unseen strings within the same length distribution. For languages where the training and validation data already includes all possible strings, we leave this column blank. We also report accuracy on the training and validation sets to show how well the model fits the training data.

In order to see the effects of model selection, we also report the mean and maximum accuracy scores on the long test set across all runs, as it is often the case that the model that generalizes best to longer strings is not the one with the lowest recognition cross-entropy. Although this kind of test-set-based model selection is impossible in the wild, for our purposes it is useful for revealing when an architecture is capable of chancing upon a solution that generalizes, even if it cannot be reliably found with model selection.

In all rows, “+LM” means a language modeling loss term is added, “+NS” means a next symbol prediction loss term is added, “S” means a short validation set is used, and “L” means a long validation set is used. “Train” is accuracy on the training set, “Val. CE” is recognition cross-entropy on the validation set (which is used as the model selection criterion), “Val.” is accuracy on the validation set, “S. Test” is accuracy on the short test set, “L. Test” is accuracy on the long test set, “L. Test (Mean)” is “L. Test” averaged across runs with standard deviations, and “L. Test (Max)” is the maximum.

**Table 4: Full results on the Even Pairs language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.994 $\pm$ 0.01 | 1.000 |
| Tf (L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.999 $\pm$ 0.00 | 1.000 |
| Tf (+LM, S) | 1.000 | 0.000 | 1.000 | 1.000 | 0.997 | 0.978 $\pm$ 0.04 | 1.000 |
| Tf (+LM, L) | 1.000 | 0.000 | 1.000 | 1.000 | 0.923 | 0.956 $\pm$ 0.06 | 1.000 |
| Tf (+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 0.998 | 0.994 $\pm$ 0.01 | 1.000 |
| Tf (+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.996 $\pm$ 0.01 | 1.000 |
| Tf (+LM+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 0.992 | 0.959 $\pm$ 0.06 | 1.000 |
| Tf (+LM+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.992 $\pm$ 0.01 | 1.000 |
| RNN (S) | 0.549 | 0.673 | 0.565 | 0.513 | 0.512 | 0.504 $\pm$ 0.01 | 0.517 |
| RNN (L) | 0.542 | 0.680 | 0.527 | 0.480 | 0.509 | 0.508 $\pm$ 0.01 | 0.518 |
| RNN (+LM, S) | 0.541 | 0.674 | 0.559 | 0.520 | 0.505 | 0.506 $\pm$ 0.01 | 0.517 |
| RNN (+LM, L) | 0.576 | 0.658 | 0.607 | 0.575 | 0.640 | 0.523 $\pm$ 0.04 | 0.640 |
| RNN (+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.556 $\pm$ 0.15 | 1.000 |
| RNN (+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.621 $\pm$ 0.19 | 1.000 |
| RNN (+LM+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.601 $\pm$ 0.20 | 1.000 |
| RNN (+LM+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.614 $\pm$ 0.20 | 1.000 |
| LSTM (S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.831 $\pm$ 0.22 | 1.000 |
| LSTM (L) | 1.000 | 0.000 | 1.000 | 1.000 | 0.761 | 0.900 $\pm$ 0.15 | 1.000 |
| LSTM (+LM, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.554 $\pm$ 0.15 | 1.000 |
| LSTM (+LM, L) | 0.538 | 0.680 | 0.520 | 0.518 | 0.509 | 0.503 $\pm$ 0.01 | 0.515 |
| LSTM (+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.611 $\pm$ 0.20 | 1.000 |
| LSTM (+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.697 $\pm$ 0.22 | 1.000 |
| LSTM (+LM+NS, S) | 0.539 | 0.671 | 0.551 | 0.508 | 0.511 | 0.504 $\pm$ 0.01 | 0.516 |
| LSTM (+LM+NS, L) | 0.537 | 0.681 | 0.513 | 0.518 | 0.497 | 0.503 $\pm$ 0.01 | 0.517 |

**Table 5: Full results on the Repeat 01 language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.999 | 0.000 | 1.000 |  | 0.707 | 0.717 $\pm$ 0.09 | 0.844 |
| Tf (L) | 0.994 | 0.134 | 0.969 |  | 0.593 | 0.693 $\pm$ 0.10 | 0.857 |
| Tf (+LM, S) | 0.998 | 0.001 | 1.000 |  | 0.833 | 0.675 $\pm$ 0.12 | 0.847 |
| Tf (+LM, L) | 0.997 | 0.087 | 0.979 |  | 0.617 | 0.687 $\pm$ 0.08 | 0.838 |
| Tf (+NS, S) | 1.000 | 0.000 | 1.000 |  | 0.546 | 0.710 $\pm$ 0.10 | 0.842 |
| Tf (+NS, L) | 0.971 | 0.126 | 0.962 |  | 0.845 | 0.734 $\pm$ 0.10 | 0.845 |
| Tf (+LM+NS, S) | 0.999 | 0.003 | 1.000 |  | 0.681 | 0.659 $\pm$ 0.09 | 0.842 |
| Tf (+LM+NS, L) | 0.997 | 0.105 | 0.970 |  | 0.592 | 0.706 $\pm$ 0.10 | 0.850 |
| RNN (S) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.935 $\pm$ 0.10 | 1.000 |
| RNN (L) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.880 $\pm$ 0.10 | 1.000 |
| RNN (+LM, S) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.956 $\pm$ 0.09 | 1.000 |
| RNN (+LM, L) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.948 $\pm$ 0.08 | 1.000 |
| RNN (+NS, S) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.969 $\pm$ 0.07 | 1.000 |
| RNN (+NS, L) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.978 $\pm$ 0.07 | 1.000 |
| RNN (+LM+NS, S) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.911 $\pm$ 0.11 | 1.000 |
| RNN (+LM+NS, L) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.914 $\pm$ 0.10 | 1.000 |
| LSTM (S) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.972 $\pm$ 0.07 | 1.000 |
| LSTM (L) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.905 $\pm$ 0.13 | 1.000 |
| LSTM (+LM, S) | 1.000 | 0.000 | 1.000 |  | 0.864 | 0.928 $\pm$ 0.14 | 1.000 |
| LSTM (+LM, L) | 1.000 | 0.000 | 1.000 |  | 0.939 | 0.975 $\pm$ 0.02 | 1.000 |
| LSTM (+NS, S) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.921 $\pm$ 0.10 | 1.000 |
| LSTM (+NS, L) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.982 $\pm$ 0.05 | 1.000 |
| LSTM (+LM+NS, S) | 1.000 | 0.000 | 1.000 |  | 1.000 | 0.953 $\pm$ 0.13 | 1.000 |
| LSTM (+LM+NS, L) | 1.000 | 0.000 | 1.000 |  | 0.964 | 0.881 $\pm$ 0.20 | 1.000 |

**Table 6: Full results on the Parity language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.713 | 0.503 | 0.688 | 0.601 | 0.538 | 0.528 $\pm$ 0.01 | 0.544 |
| Tf (L) | 0.664 | 0.620 | 0.595 | 0.569 | 0.521 | 0.529 $\pm$ 0.01 | 0.543 |
| Tf (+LM, S) | 0.764 | 0.452 | 0.722 | 0.680 | 0.558 | 0.530 $\pm$ 0.01 | 0.558 |
| Tf (+LM, L) | 0.756 | 0.552 | 0.658 | 0.686 | 0.561 | 0.532 $\pm$ 0.01 | 0.561 |
| Tf (+NS, S) | 0.969 | 0.060 | 0.973 | 0.953 | 0.559 | 0.557 $\pm$ 0.03 | 0.630 |
| Tf (+NS, L) | 0.903 | 0.424 | 0.766 | 0.882 | 0.550 | 0.547 $\pm$ 0.02 | 0.599 |
| Tf (+LM+NS, S) | 0.909 | 0.198 | 0.895 | 0.874 | 0.579 | 0.552 $\pm$ 0.03 | 0.604 |
| Tf (+LM+NS, L) | 0.865 | 0.444 | 0.751 | 0.820 | 0.587 | 0.553 $\pm$ 0.03 | 0.591 |
| RNN (S) | 0.546 | 0.677 | 0.531 | 0.534 | 0.521 | 0.507 $\pm$ 0.01 | 0.525 |
| RNN (L) | 0.554 | 0.687 | 0.540 | 0.540 | 0.522 | 0.512 $\pm$ 0.01 | 0.541 |
| RNN (+LM, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.605 $\pm$ 0.20 | 1.000 |
| RNN (+LM, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.572 $\pm$ 0.15 | 1.000 |
| RNN (+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.712 $\pm$ 0.24 | 1.000 |
| RNN (+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.671 $\pm$ 0.19 | 1.000 |
| RNN (+LM+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.706 $\pm$ 0.24 | 1.000 |
| RNN (+LM+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.682 $\pm$ 0.21 | 1.000 |
| LSTM (S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.664 $\pm$ 0.22 | 1.000 |
| LSTM (L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.705 $\pm$ 0.24 | 1.000 |
| LSTM (+LM, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.599 $\pm$ 0.20 | 1.000 |
| LSTM (+LM, L) | 0.544 | 0.686 | 0.542 | 0.542 | 0.497 | 0.494 $\pm$ 0.00 | 0.497 |
| LSTM (+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.902 $\pm$ 0.20 | 1.000 |
| LSTM (+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.752 $\pm$ 0.25 | 1.000 |
| LSTM (+LM+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.613 $\pm$ 0.20 | 1.000 |
| LSTM (+LM+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.547 $\pm$ 0.15 | 1.000 |

**Table 7: Full results on the Cycle Navigation language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.931 | 0.250 | 0.911 | 0.946 | 0.811 | 0.836 $\pm$ 0.05 | 0.934 |
| Tf (L) | 0.923 | 0.192 | 0.938 | 0.946 | 0.901 | 0.844 $\pm$ 0.05 | 0.934 |
| Tf (+LM, S) | 0.931 | 0.249 | 0.911 | 0.946 | 0.805 | 0.804 $\pm$ 0.10 | 0.933 |
| Tf (+LM, L) | 0.926 | 0.191 | 0.938 | 0.946 | 0.923 | 0.866 $\pm$ 0.05 | 0.933 |
| Tf (+NS, S) | 0.984 | 0.074 | 0.973 | 0.987 | 0.767 | 0.812 $\pm$ 0.04 | 0.884 |
| Tf (+NS, L) | 0.950 | 0.169 | 0.943 | 0.957 | 0.776 | 0.819 $\pm$ 0.04 | 0.927 |
| Tf (+LM+NS, S) | 0.931 | 0.251 | 0.911 | 0.946 | 0.810 | 0.838 $\pm$ 0.05 | 0.932 |
| Tf (+LM+NS, L) | 0.924 | 0.192 | 0.938 | 0.946 | 0.932 | 0.838 $\pm$ 0.05 | 0.932 |
| RNN (S) | 0.930 | 0.255 | 0.910 | 0.946 | 0.934 | 0.930 $\pm$ 0.01 | 0.934 |
| RNN (L) | 0.928 | 0.192 | 0.939 | 0.946 | 0.934 | 0.917 $\pm$ 0.05 | 0.934 |
| RNN (+LM, S) | 0.929 | 0.254 | 0.910 | 0.946 | 0.934 | 0.915 $\pm$ 0.05 | 0.934 |
| RNN (+LM, L) | 0.931 | 0.189 | 0.941 | 0.946 | 0.934 | 0.904 $\pm$ 0.09 | 0.934 |
| RNN (+NS, S) | 0.930 | 0.256 | 0.910 | 0.946 | 0.934 | 0.900 $\pm$ 0.07 | 0.934 |
| RNN (+NS, L) | 0.929 | 0.190 | 0.940 | 0.946 | 0.934 | 0.877 $\pm$ 0.13 | 0.934 |
| RNN (+LM+NS, S) | 0.928 | 0.264 | 0.907 | 0.946 | 0.934 | 0.888 $\pm$ 0.11 | 0.934 |
| RNN (+LM+NS, L) | 0.929 | 0.192 | 0.940 | 0.946 | 0.934 | 0.839 $\pm$ 0.17 | 0.934 |
| LSTM (S) | 0.929 | 0.257 | 0.910 | 0.946 | 0.934 | 0.900 $\pm$ 0.04 | 0.934 |
| LSTM (L) | 0.929 | 0.190 | 0.940 | 0.946 | 0.927 | 0.914 $\pm$ 0.03 | 0.934 |
| LSTM (+LM, S) | 0.930 | 0.252 | 0.910 | 0.946 | 0.934 | 0.878 $\pm$ 0.13 | 0.934 |
| LSTM (+LM, L) | 0.929 | 0.191 | 0.940 | 0.946 | 0.934 | 0.828 $\pm$ 0.17 | 0.934 |
| LSTM (+NS, S) | 0.931 | 0.255 | 0.911 | 0.946 | 0.934 | 0.822 $\pm$ 0.16 | 0.934 |
| LSTM (+NS, L) | 0.929 | 0.193 | 0.940 | 0.946 | 0.923 | 0.880 $\pm$ 0.13 | 0.933 |
| LSTM (+LM+NS, S) | 0.935 | 0.237 | 0.912 | 0.947 | 0.884 | 0.874 $\pm$ 0.13 | 0.934 |
| LSTM (+LM+NS, L) | 0.929 | 0.189 | 0.940 | 0.946 | 0.933 | 0.798 $\pm$ 0.20 | 0.934 |

**Table 8: Full results on the Modular Arithmetic language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.977 | 0.093 | 0.976 | 0.979 | 0.643 | 0.686 $\pm$ 0.11 | 0.812 |
| Tf (L) | 0.978 | 0.117 | 0.963 | 0.981 | 0.829 | 0.698 $\pm$ 0.09 | 0.830 |
| Tf (+LM, S) | 0.983 | 0.085 | 0.980 | 0.980 | 0.531 | 0.659 $\pm$ 0.11 | 0.796 |
| Tf (+LM, L) | 0.929 | 0.270 | 0.889 | 0.919 | 0.559 | 0.676 $\pm$ 0.08 | 0.790 |
| Tf (+NS, S) | 0.984 | 0.085 | 0.981 | 0.981 | 0.740 | 0.654 $\pm$ 0.12 | 0.869 |
| Tf (+NS, L) | 0.975 | 0.100 | 0.969 | 0.976 | 0.884 | 0.706 $\pm$ 0.09 | 0.884 |
| Tf (+LM+NS, S) | 0.979 | 0.089 | 0.976 | 0.981 | 0.826 | 0.671 $\pm$ 0.12 | 0.852 |
| Tf (+LM+NS, L) | 0.972 | 0.122 | 0.965 | 0.973 | 0.582 | 0.612 $\pm$ 0.08 | 0.793 |
| RNN (S) | 0.986 | 0.080 | 0.982 | 0.978 | 0.997 | 0.996 $\pm$ 0.00 | 0.997 |
| RNN (L) | 0.988 | 0.062 | 0.987 | 0.984 | 0.997 | 0.989 $\pm$ 0.02 | 0.997 |
| RNN (+LM, S) | 0.987 | 0.081 | 0.982 | 0.980 | 0.997 | 0.882 $\pm$ 0.10 | 0.997 |
| RNN (+LM, L) | 0.988 | 0.062 | 0.987 | 0.984 | 0.997 | 0.964 $\pm$ 0.07 | 0.997 |
| RNN (+NS, S) | 0.987 | 0.079 | 0.982 | 0.980 | 0.997 | 0.950 $\pm$ 0.08 | 0.997 |
| RNN (+NS, L) | 0.988 | 0.062 | 0.987 | 0.984 | 0.996 | 0.965 $\pm$ 0.07 | 0.997 |
| RNN (+LM+NS, S) | 0.986 | 0.079 | 0.982 | 0.978 | 0.997 | 0.966 $\pm$ 0.07 | 0.997 |
| RNN (+LM+NS, L) | 0.988 | 0.062 | 0.987 | 0.984 | 0.997 | 0.955 $\pm$ 0.07 | 0.997 |
| LSTM (S) | 0.986 | 0.078 | 0.982 | 0.978 | 0.997 | 0.982 $\pm$ 0.03 | 0.997 |
| LSTM (L) | 0.985 | 0.063 | 0.987 | 0.978 | 0.997 | 0.955 $\pm$ 0.08 | 0.997 |
| LSTM (+LM, S) | 0.986 | 0.081 | 0.982 | 0.978 | 0.997 | 0.981 $\pm$ 0.03 | 0.997 |
| LSTM (+LM, L) | 0.988 | 0.061 | 0.987 | 0.984 | 0.997 | 0.995 $\pm$ 0.00 | 0.997 |
| LSTM (+NS, S) | 0.986 | 0.078 | 0.982 | 0.978 | 0.997 | 0.952 $\pm$ 0.09 | 0.997 |
| LSTM (+NS, L) | 0.988 | 0.061 | 0.987 | 0.984 | 0.997 | 0.957 $\pm$ 0.07 | 0.997 |
| LSTM (+LM+NS, S) | 0.986 | 0.081 | 0.982 | 0.978 | 0.964 | 0.918 $\pm$ 0.14 | 0.997 |
| LSTM (+LM+NS, L) | 0.988 | 0.062 | 0.987 | 0.984 | 0.996 | 0.950 $\pm$ 0.08 | 0.997 |

**Table 9: Full results on the Dyck-$(2,3)$ language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.968 | 0.119 | 0.969 | 0.968 | 0.585 | 0.630 $\pm$ 0.05 | 0.711 |
| Tf (L) | 0.965 | 0.146 | 0.953 | 0.967 | 0.804 | 0.690 $\pm$ 0.08 | 0.804 |
| Tf (+LM, S) | 0.998 | 0.010 | 0.998 | 0.994 | 0.604 | 0.702 $\pm$ 0.09 | 0.811 |
| Tf (+LM, L) | 0.979 | 0.157 | 0.950 | 0.975 | 0.599 | 0.652 $\pm$ 0.06 | 0.778 |
| Tf (+NS, S) | 0.998 | 0.002 | 1.000 | 0.995 | 0.596 | 0.622 $\pm$ 0.07 | 0.765 |
| Tf (+NS, L) | 0.964 | 0.163 | 0.941 | 0.969 | 0.756 | 0.687 $\pm$ 0.09 | 0.819 |
| Tf (+LM+NS, S) | 0.996 | 0.008 | 0.996 | 0.991 | 0.693 | 0.627 $\pm$ 0.05 | 0.734 |
| Tf (+LM+NS, L) | 0.994 | 0.123 | 0.959 | 0.989 | 0.788 | 0.693 $\pm$ 0.08 | 0.791 |
| RNN (S) | 0.972 | 0.093 | 0.976 | 0.977 | 0.980 | 0.907 $\pm$ 0.08 | 0.982 |
| RNN (L) | 0.972 | 0.092 | 0.979 | 0.976 | 0.972 | 0.929 $\pm$ 0.10 | 0.982 |
| RNN (+LM, S) | 0.999 | 0.005 | 1.000 | 0.998 | 0.991 | 0.941 $\pm$ 0.07 | 0.991 |
| RNN (+LM, L) | 0.999 | 0.014 | 0.998 | 0.998 | 0.826 | 0.945 $\pm$ 0.05 | 0.982 |
| RNN (+NS, S) | 0.999 | 0.005 | 0.999 | 0.999 | 0.957 | 0.952 $\pm$ 0.07 | 0.998 |
| RNN (+NS, L) | 0.998 | 0.014 | 0.998 | 0.997 | 0.988 | 0.923 $\pm$ 0.07 | 0.996 |
| RNN (+LM+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 0.999 | 0.953 $\pm$ 0.05 | 0.999 |
| RNN (+LM+NS, L) | 1.000 | 0.001 | 1.000 | 1.000 | 0.991 | 0.922 $\pm$ 0.09 | 0.996 |
| LSTM (S) | 0.971 | 0.097 | 0.975 | 0.978 | 0.982 | 0.907 $\pm$ 0.10 | 0.982 |
| LSTM (L) | 0.971 | 0.094 | 0.979 | 0.978 | 0.977 | 0.883 $\pm$ 0.10 | 0.977 |
| LSTM (+LM, S) | 0.971 | 0.100 | 0.975 | 0.978 | 0.982 | 0.835 $\pm$ 0.14 | 0.982 |
| LSTM (+LM, L) | 0.972 | 0.089 | 0.979 | 0.976 | 0.701 | 0.868 $\pm$ 0.10 | 0.980 |
| LSTM (+NS, S) | 0.972 | 0.097 | 0.975 | 0.977 | 0.982 | 0.882 $\pm$ 0.16 | 0.982 |
| LSTM (+NS, L) | 0.972 | 0.091 | 0.979 | 0.975 | 0.976 | 0.942 $\pm$ 0.07 | 0.983 |
| LSTM (+LM+NS, S) | 0.971 | 0.098 | 0.974 | 0.977 | 0.962 | 0.838 $\pm$ 0.19 | 0.983 |
| LSTM (+LM+NS, L) | 0.972 | 0.089 | 0.979 | 0.977 | 0.975 | 0.922 $\pm$ 0.10 | 0.982 |

**Table 10: Full results on the First language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.926 $\pm$ 0.12 | 1.000 |
| Tf (L) | 1.000 | 0.000 | 1.000 | 1.000 | 0.987 | 0.936 $\pm$ 0.10 | 1.000 |
| Tf (+LM, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.934 $\pm$ 0.08 | 1.000 |
| Tf (+LM, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.974 $\pm$ 0.04 | 1.000 |
| Tf (+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 0.952 | 0.982 $\pm$ 0.04 | 1.000 |
| Tf (+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.969 $\pm$ 0.08 | 1.000 |
| Tf (+LM+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 0.999 | 0.935 $\pm$ 0.14 | 1.000 |
| Tf (+LM+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.928 $\pm$ 0.12 | 1.000 |
| RNN (S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.629 $\pm$ 0.20 | 1.000 |
| RNN (L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.701 $\pm$ 0.24 | 1.000 |
| RNN (+LM, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.800 $\pm$ 0.24 | 1.000 |
| RNN (+LM, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.800 $\pm$ 0.24 | 1.000 |
| RNN (+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.703 $\pm$ 0.24 | 1.000 |
| RNN (+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.799 $\pm$ 0.25 | 1.000 |
| RNN (+LM+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.750 $\pm$ 0.25 | 1.000 |
| RNN (+LM+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.704 $\pm$ 0.24 | 1.000 |
| LSTM (S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.932 $\pm$ 0.15 | 1.000 |
| LSTM (L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 1.000 $\pm$ 0.00 | 1.000 |
| LSTM (+LM, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.938 $\pm$ 0.14 | 1.000 |
| LSTM (+LM, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.896 $\pm$ 0.15 | 1.000 |
| LSTM (+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.850 $\pm$ 0.23 | 1.000 |
| LSTM (+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.944 $\pm$ 0.09 | 1.000 |
| LSTM (+LM+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.850 $\pm$ 0.23 | 1.000 |
| LSTM (+LM+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 0.779 | 0.912 $\pm$ 0.15 | 1.000 |

**Table 11: Full results on the Majority language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 1.000 | 0.001 | 1.000 | 1.000 | 0.970 | 0.946 $\pm$ 0.07 | 0.990 |
| Tf (L) | 1.000 | 0.004 | 1.000 | 1.000 | 0.985 | 0.943 $\pm$ 0.07 | 0.995 |
| Tf (+LM, S) | 1.000 | 0.001 | 1.000 | 1.000 | 0.992 | 0.969 $\pm$ 0.04 | 0.992 |
| Tf (+LM, L) | 1.000 | 0.005 | 1.000 | 1.000 | 0.991 | 0.959 $\pm$ 0.05 | 0.996 |
| Tf (+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 0.992 | 0.961 $\pm$ 0.05 | 0.992 |
| Tf (+NS, L) | 1.000 | 0.005 | 0.998 | 1.000 | 0.985 | 0.966 $\pm$ 0.04 | 0.993 |
| Tf (+LM+NS, S) | 1.000 | 0.001 | 1.000 | 1.000 | 0.989 | 0.969 $\pm$ 0.02 | 0.989 |
| Tf (+LM+NS, L) | 1.000 | 0.007 | 0.998 | 1.000 | 0.991 | 0.975 $\pm$ 0.04 | 0.993 |
| RNN (S) | 1.000 | 0.003 | 1.000 | 1.000 | 0.913 | 0.868 $\pm$ 0.12 | 0.928 |
| RNN (L) | 1.000 | 0.025 | 0.997 | 1.000 | 0.926 | 0.834 $\pm$ 0.14 | 0.931 |
| RNN (+LM, S) | 1.000 | 0.000 | 1.000 | 1.000 | 0.918 | 0.875 $\pm$ 0.12 | 0.924 |
| RNN (+LM, L) | 1.000 | 0.021 | 0.996 | 1.000 | 0.916 | 0.880 $\pm$ 0.13 | 0.945 |
| RNN (+NS, S) | 0.999 | 0.005 | 0.999 | 0.998 | 0.899 | 0.896 $\pm$ 0.03 | 0.927 |
| RNN (+NS, L) | 0.999 | 0.030 | 0.994 | 0.998 | 0.934 | 0.916 $\pm$ 0.01 | 0.934 |
| RNN (+LM+NS, S) | 1.000 | 0.006 | 0.999 | 1.000 | 0.919 | 0.887 $\pm$ 0.07 | 0.927 |
| RNN (+LM+NS, L) | 1.000 | 0.021 | 0.997 | 1.000 | 0.927 | 0.877 $\pm$ 0.13 | 0.949 |
| LSTM (S) | 1.000 | 0.000 | 1.000 | 1.000 | 0.979 | 0.939 $\pm$ 0.04 | 0.997 |
| LSTM (L) | 1.000 | 0.000 | 1.000 | 1.000 | 0.973 | 0.943 $\pm$ 0.02 | 0.989 |
| LSTM (+LM, S) | 1.000 | 0.000 | 1.000 | 1.000 | 0.980 | 0.942 $\pm$ 0.04 | 0.998 |
| LSTM (+LM, L) | 1.000 | 0.000 | 1.000 | 1.000 | 0.990 | 0.946 $\pm$ 0.04 | 0.995 |
| LSTM (+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 0.999 | 0.952 $\pm$ 0.04 | 0.999 |
| LSTM (+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 0.989 | 0.862 $\pm$ 0.18 | 0.997 |
| LSTM (+LM+NS, S) | 1.000 | 0.000 | 1.000 | 1.000 | 1.000 | 0.913 $\pm$ 0.14 | 1.000 |
| LSTM (+LM+NS, L) | 1.000 | 0.000 | 1.000 | 1.000 | 0.991 | 0.963 $\pm$ 0.04 | 1.000 |

**Table 12: Full results on the Stack Manipulation language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.929 | 0.190 | 0.917 | 0.912 | 0.610 | 0.664 $\pm$ 0.14 | 0.869 |
| Tf (L) | 0.920 | 0.294 | 0.885 | 0.897 | 0.573 | 0.640 $\pm$ 0.13 | 0.868 |
| Tf (+LM, S) | 0.981 | 0.072 | 0.983 | 0.980 | 0.515 | 0.595 $\pm$ 0.13 | 0.854 |
| Tf (+LM, L) | 0.935 | 0.238 | 0.909 | 0.922 | 0.869 | 0.701 $\pm$ 0.14 | 0.869 |
| Tf (+NS, S) | 0.976 | 0.101 | 0.973 | 0.976 | 0.857 | 0.591 $\pm$ 0.14 | 0.868 |
| Tf (+NS, L) | 0.928 | 0.255 | 0.906 | 0.914 | 0.545 | 0.684 $\pm$ 0.14 | 0.869 |
| Tf (+LM+NS, S) | 0.981 | 0.059 | 0.985 | 0.979 | 0.515 | 0.571 $\pm$ 0.11 | 0.868 |
| Tf (+LM+NS, L) | 0.950 | 0.246 | 0.914 | 0.939 | 0.870 | 0.608 $\pm$ 0.13 | 0.870 |
| RNN (S) | 0.926 | 0.229 | 0.923 | 0.919 | 0.928 | 0.834 $\pm$ 0.12 | 0.929 |
| RNN (L) | 0.943 | 0.187 | 0.940 | 0.944 | 0.933 | 0.783 $\pm$ 0.17 | 0.933 |
| RNN (+LM, S) | 0.985 | 0.070 | 0.986 | 0.983 | 0.520 | 0.691 $\pm$ 0.18 | 0.930 |
| RNN (+LM, L) | 0.925 | 0.211 | 0.927 | 0.919 | 0.930 | 0.817 $\pm$ 0.12 | 0.930 |
| RNN (+NS, S) | 0.986 | 0.073 | 0.986 | 0.989 | 0.520 | 0.838 $\pm$ 0.16 | 0.930 |
| RNN (+NS, L) | 0.930 | 0.208 | 0.931 | 0.919 | 0.927 | 0.854 $\pm$ 0.12 | 0.930 |
| RNN (+LM+NS, S) | 0.988 | 0.050 | 0.991 | 0.990 | 0.523 | 0.762 $\pm$ 0.20 | 0.930 |
| RNN (+LM+NS, L) | 0.935 | 0.206 | 0.934 | 0.937 | 0.932 | 0.852 $\pm$ 0.11 | 0.932 |
| LSTM (S) | 0.989 | 0.047 | 0.991 | 0.993 | 0.987 | 0.746 $\pm$ 0.17 | 0.987 |
| LSTM (L) | 0.956 | 0.189 | 0.936 | 0.951 | 0.876 | 0.784 $\pm$ 0.07 | 0.885 |
| LSTM (+LM, S) | 0.987 | 0.045 | 0.991 | 0.992 | 0.551 | 0.568 $\pm$ 0.09 | 0.818 |
| LSTM (+LM, L) | 0.989 | 0.069 | 0.986 | 0.990 | 0.540 | 0.674 $\pm$ 0.14 | 0.906 |
| LSTM (+NS, S) | 0.987 | 0.051 | 0.988 | 0.992 | 0.664 | 0.669 $\pm$ 0.14 | 0.922 |
| LSTM (+NS, L) | 0.989 | 0.063 | 0.986 | 0.993 | 0.750 | 0.674 $\pm$ 0.10 | 0.799 |
| LSTM (+LM+NS, S) | 0.989 | 0.043 | 0.991 | 0.993 | 0.602 | 0.528 $\pm$ 0.03 | 0.602 |
| LSTM (+LM+NS, L) | 0.988 | 0.066 | 0.985 | 0.993 | 0.541 | 0.620 $\pm$ 0.13 | 0.896 |

**Table 13: Full results on the Marked Reversal language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.969 | 0.116 | 0.969 | 0.967 | 0.552 | 0.604 $\pm$ 0.11 | 0.847 |
| Tf (L) | 0.876 | 0.316 | 0.879 | 0.877 | 0.616 | 0.693 $\pm$ 0.08 | 0.758 |
| Tf (+LM, S) | 0.969 | 0.117 | 0.969 | 0.967 | 0.534 | 0.577 $\pm$ 0.08 | 0.740 |
| Tf (+LM, L) | 0.960 | 0.197 | 0.943 | 0.953 | 0.870 | 0.689 $\pm$ 0.13 | 0.870 |
| Tf (+NS, S) | 0.995 | 0.032 | 0.992 | 0.991 | 0.541 | 0.641 $\pm$ 0.12 | 0.827 |
| Tf (+NS, L) | 0.969 | 0.176 | 0.944 | 0.967 | 0.868 | 0.647 $\pm$ 0.12 | 0.868 |
| Tf (+LM+NS, S) | 0.993 | 0.027 | 0.995 | 0.994 | 0.539 | 0.580 $\pm$ 0.10 | 0.859 |
| Tf (+LM+NS, L) | 0.966 | 0.170 | 0.941 | 0.962 | 0.853 | 0.665 $\pm$ 0.09 | 0.853 |
| RNN (S) | 0.968 | 0.119 | 0.969 | 0.965 | 0.603 | 0.693 $\pm$ 0.17 | 0.947 |
| RNN (L) | 0.960 | 0.131 | 0.965 | 0.961 | 0.594 | 0.761 $\pm$ 0.15 | 0.947 |
| RNN (+LM, S) | 0.969 | 0.119 | 0.969 | 0.967 | 0.535 | 0.662 $\pm$ 0.14 | 0.911 |
| RNN (+LM, L) | 0.959 | 0.130 | 0.965 | 0.960 | 0.948 | 0.793 $\pm$ 0.11 | 0.948 |
| RNN (+NS, S) | 0.967 | 0.124 | 0.969 | 0.965 | 0.544 | 0.699 $\pm$ 0.18 | 0.948 |
| RNN (+NS, L) | 0.968 | 0.102 | 0.975 | 0.966 | 0.643 | 0.612 $\pm$ 0.12 | 0.947 |
| RNN (+LM+NS, S) | 0.968 | 0.119 | 0.969 | 0.967 | 0.538 | 0.651 $\pm$ 0.17 | 0.947 |
| RNN (+LM+NS, L) | 0.955 | 0.136 | 0.963 | 0.958 | 0.947 | 0.660 $\pm$ 0.14 | 0.947 |
| LSTM (S) | 0.969 | 0.116 | 0.969 | 0.967 | 0.954 | 0.744 $\pm$ 0.17 | 0.963 |
| LSTM (L) | 0.952 | 0.163 | 0.950 | 0.946 | 0.574 | 0.755 $\pm$ 0.13 | 0.859 |
| LSTM (+LM, S) | 0.999 | 0.001 | 1.000 | 0.992 | 0.584 | 0.552 $\pm$ 0.05 | 0.679 |
| LSTM (+LM, L) | 0.969 | 0.103 | 0.975 | 0.967 | 0.596 | 0.681 $\pm$ 0.16 | 0.947 |
| LSTM (+NS, S) | 0.969 | 0.117 | 0.969 | 0.967 | 0.561 | 0.653 $\pm$ 0.12 | 0.845 |
| LSTM (+NS, L) | 0.969 | 0.107 | 0.975 | 0.967 | 0.578 | 0.623 $\pm$ 0.10 | 0.852 |
| LSTM (+LM+NS, S) | 0.969 | 0.116 | 0.969 | 0.967 | 0.617 | 0.624 $\pm$ 0.11 | 0.946 |
| LSTM (+LM+NS, L) | 0.981 | 0.073 | 0.981 | 0.980 | 0.593 | 0.585 $\pm$ 0.05 | 0.674 |

**Table 14: Full results on the Unmarked Reversal language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.970 | 0.099 | 0.971 | 0.969 | 0.552 | 0.584 $\pm$ 0.03 | 0.632 |
| Tf (L) | 0.818 | 0.454 | 0.774 | 0.839 | 0.583 | 0.600 $\pm$ 0.04 | 0.631 |
| Tf (+LM, S) | 0.955 | 0.147 | 0.952 | 0.958 | 0.563 | 0.552 $\pm$ 0.04 | 0.617 |
| Tf (+LM, L) | 0.695 | 0.558 | 0.674 | 0.677 | 0.559 | 0.544 $\pm$ 0.04 | 0.623 |
| Tf (+NS, S) | 0.963 | 0.112 | 0.965 | 0.949 | 0.541 | 0.557 $\pm$ 0.02 | 0.612 |
| Tf (+NS, L) | 0.868 | 0.456 | 0.779 | 0.846 | 0.547 | 0.578 $\pm$ 0.04 | 0.630 |
| Tf (+LM+NS, S) | 0.959 | 0.127 | 0.957 | 0.940 | 0.540 | 0.539 $\pm$ 0.03 | 0.578 |
| Tf (+LM+NS, L) | 0.752 | 0.529 | 0.726 | 0.748 | 0.607 | 0.589 $\pm$ 0.04 | 0.630 |
| RNN (S) | 0.975 | 0.094 | 0.974 | 0.977 | 0.670 | 0.708 $\pm$ 0.09 | 0.763 |
| RNN (L) | 0.970 | 0.139 | 0.965 | 0.962 | 0.726 | 0.736 $\pm$ 0.05 | 0.763 |
| RNN (+LM, S) | 0.973 | 0.020 | 0.982 | 0.998 | 0.622 | 0.715 $\pm$ 0.05 | 0.763 |
| RNN (+LM, L) | 0.981 | 0.097 | 0.982 | 0.984 | 0.748 | 0.721 $\pm$ 0.05 | 0.763 |
| RNN (+NS, S) | 0.976 | 0.097 | 0.971 | 0.968 | 0.682 | 0.716 $\pm$ 0.08 | 0.766 |
| RNN (+NS, L) | 0.974 | 0.158 | 0.957 | 0.963 | 0.665 | 0.744 $\pm$ 0.05 | 0.813 |
| RNN (+LM+NS, S) | 0.961 | 0.061 | 0.973 | 0.984 | 0.636 | 0.712 $\pm$ 0.07 | 0.763 |
| RNN (+LM+NS, L) | 0.971 | 0.150 | 0.954 | 0.961 | 0.765 | 0.744 $\pm$ 0.04 | 0.765 |
| LSTM (S) | 0.963 | 0.150 | 0.954 | 0.944 | 0.610 | 0.685 $\pm$ 0.09 | 0.763 |
| LSTM (L) | 0.989 | 0.056 | 0.988 | 0.987 | 0.746 | 0.717 $\pm$ 0.08 | 0.763 |
| LSTM (+LM, S) | 0.786 | 0.440 | 0.774 | 0.751 | 0.763 | 0.711 $\pm$ 0.10 | 0.763 |
| LSTM (+LM, L) | 0.786 | 0.444 | 0.782 | 0.751 | 0.763 | 0.711 $\pm$ 0.10 | 0.763 |
| LSTM (+NS, S) | 0.966 | 0.145 | 0.953 | 0.934 | 0.743 | 0.761 $\pm$ 0.01 | 0.763 |
| LSTM (+NS, L) | 0.987 | 0.068 | 0.982 | 0.985 | 0.838 | 0.731 $\pm$ 0.12 | 0.884 |
| LSTM (+LM+NS, S) | 0.786 | 0.441 | 0.774 | 0.751 | 0.763 | 0.711 $\pm$ 0.10 | 0.763 |
| LSTM (+LM+NS, L) | 0.786 | 0.444 | 0.782 | 0.751 | 0.763 | 0.711 $\pm$ 0.10 | 0.763 |

**Table 15: Full results on the Marked Copy language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.970 | 0.113 | 0.970 | 0.977 | 0.548 | 0.565 $\pm$ 0.04 | 0.639 |
| Tf (L) | 0.859 | 0.327 | 0.866 | 0.872 | 0.795 | 0.698 $\pm$ 0.07 | 0.795 |
| Tf (+LM, S) | 0.970 | 0.114 | 0.970 | 0.977 | 0.542 | 0.614 $\pm$ 0.10 | 0.846 |
| Tf (+LM, L) | 0.949 | 0.206 | 0.937 | 0.955 | 0.625 | 0.646 $\pm$ 0.08 | 0.785 |
| Tf (+NS, S) | 0.991 | 0.035 | 0.992 | 0.991 | 0.588 | 0.627 $\pm$ 0.11 | 0.872 |
| Tf (+NS, L) | 0.950 | 0.213 | 0.922 | 0.950 | 0.843 | 0.693 $\pm$ 0.14 | 0.856 |
| Tf (+LM+NS, S) | 0.990 | 0.025 | 0.991 | 0.992 | 0.550 | 0.573 $\pm$ 0.08 | 0.827 |
| Tf (+LM+NS, L) | 0.963 | 0.226 | 0.944 | 0.970 | 0.573 | 0.612 $\pm$ 0.08 | 0.775 |
| RNN (S) | 0.970 | 0.118 | 0.970 | 0.977 | 0.602 | 0.723 $\pm$ 0.15 | 0.920 |
| RNN (L) | 0.958 | 0.134 | 0.964 | 0.965 | 0.946 | 0.710 $\pm$ 0.14 | 0.946 |
| RNN (+LM, S) | 0.970 | 0.115 | 0.970 | 0.977 | 0.545 | 0.756 $\pm$ 0.15 | 0.945 |
| RNN (+LM, L) | 0.959 | 0.135 | 0.965 | 0.969 | 0.595 | 0.730 $\pm$ 0.15 | 0.945 |
| RNN (+NS, S) | 0.970 | 0.115 | 0.970 | 0.977 | 0.677 | 0.755 $\pm$ 0.14 | 0.908 |
| RNN (+NS, L) | 0.960 | 0.133 | 0.965 | 0.967 | 0.946 | 0.757 $\pm$ 0.13 | 0.946 |
| RNN (+LM+NS, S) | 0.970 | 0.117 | 0.970 | 0.976 | 0.598 | 0.730 $\pm$ 0.15 | 0.946 |
| RNN (+LM+NS, L) | 0.961 | 0.127 | 0.966 | 0.968 | 0.591 | 0.728 $\pm$ 0.14 | 0.945 |
| LSTM (S) | 0.970 | 0.113 | 0.970 | 0.977 | 0.564 | 0.691 $\pm$ 0.15 | 0.946 |
| LSTM (L) | 0.970 | 0.099 | 0.976 | 0.977 | 0.649 | 0.717 $\pm$ 0.12 | 0.946 |
| LSTM (+LM, S) | 0.970 | 0.113 | 0.970 | 0.977 | 0.568 | 0.582 $\pm$ 0.07 | 0.781 |
| LSTM (+LM, L) | 0.970 | 0.098 | 0.976 | 0.977 | 0.596 | 0.656 $\pm$ 0.09 | 0.807 |
| LSTM (+NS, S) | 0.995 | 0.041 | 0.990 | 0.994 | 0.568 | 0.609 $\pm$ 0.12 | 0.962 |
| LSTM (+NS, L) | 0.970 | 0.098 | 0.976 | 0.977 | 0.721 | 0.664 $\pm$ 0.11 | 0.923 |
| LSTM (+LM+NS, S) | 0.970 | 0.113 | 0.970 | 0.977 | 0.631 | 0.604 $\pm$ 0.09 | 0.849 |
| LSTM (+LM+NS, L) | 0.970 | 0.098 | 0.976 | 0.977 | 0.657 | 0.600 $\pm$ 0.07 | 0.760 |

**Table 16: Full results on the Missing Duplicate language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.938 | 0.200 | 0.933 | 0.949 | 0.614 | 0.650 $\pm$ 0.09 | 0.781 |
| Tf (L) | 0.856 | 0.316 | 0.876 | 0.874 | 0.857 | 0.709 $\pm$ 0.10 | 0.857 |
| Tf (+LM, S) | 0.880 | 0.311 | 0.871 | 0.890 | 0.638 | 0.608 $\pm$ 0.05 | 0.687 |
| Tf (+LM, L) | 0.856 | 0.315 | 0.876 | 0.874 | 0.782 | 0.699 $\pm$ 0.09 | 0.796 |
| Tf (+NS, S) | 0.953 | 0.169 | 0.943 | 0.952 | 0.720 | 0.637 $\pm$ 0.10 | 0.857 |
| Tf (+NS, L) | 0.860 | 0.317 | 0.875 | 0.874 | 0.777 | 0.651 $\pm$ 0.07 | 0.777 |
| Tf (+LM+NS, S) | 0.955 | 0.166 | 0.948 | 0.956 | 0.696 | 0.661 $\pm$ 0.08 | 0.760 |
| Tf (+LM+NS, L) | 0.864 | 0.315 | 0.880 | 0.874 | 0.858 | 0.728 $\pm$ 0.11 | 0.858 |
| RNN (S) | 0.946 | 0.176 | 0.944 | 0.949 | 0.919 | 0.824 $\pm$ 0.10 | 0.944 |
| RNN (L) | 0.951 | 0.163 | 0.953 | 0.957 | 0.783 | 0.815 $\pm$ 0.07 | 0.937 |
| RNN (+LM, S) | 0.951 | 0.178 | 0.946 | 0.957 | 0.945 | 0.789 $\pm$ 0.10 | 0.945 |
| RNN (+LM, L) | 0.951 | 0.163 | 0.953 | 0.957 | 0.945 | 0.860 $\pm$ 0.07 | 0.945 |
| RNN (+NS, S) | 0.959 | 0.162 | 0.952 | 0.959 | 0.946 | 0.804 $\pm$ 0.14 | 0.946 |
| RNN (+NS, L) | 0.982 | 0.116 | 0.967 | 0.970 | 0.942 | 0.879 $\pm$ 0.10 | 0.945 |
| RNN (+LM+NS, S) | 0.950 | 0.179 | 0.946 | 0.957 | 0.945 | 0.790 $\pm$ 0.13 | 0.945 |
| RNN (+LM+NS, L) | 0.951 | 0.162 | 0.954 | 0.957 | 0.696 | 0.813 $\pm$ 0.15 | 0.946 |
| LSTM (S) | 0.951 | 0.178 | 0.946 | 0.957 | 0.926 | 0.852 $\pm$ 0.07 | 0.945 |
| LSTM (L) | 0.951 | 0.162 | 0.953 | 0.957 | 0.922 | 0.794 $\pm$ 0.07 | 0.922 |
| LSTM (+LM, S) | 0.951 | 0.179 | 0.946 | 0.957 | 0.945 | 0.795 $\pm$ 0.15 | 0.945 |
| LSTM (+LM, L) | 0.951 | 0.161 | 0.953 | 0.957 | 0.771 | 0.769 $\pm$ 0.12 | 0.945 |
| LSTM (+NS, S) | 0.958 | 0.163 | 0.951 | 0.957 | 0.946 | 0.821 $\pm$ 0.15 | 0.946 |
| LSTM (+NS, L) | 0.951 | 0.162 | 0.953 | 0.957 | 0.913 | 0.784 $\pm$ 0.13 | 0.945 |
| LSTM (+LM+NS, S) | 0.954 | 0.174 | 0.947 | 0.957 | 0.940 | 0.770 $\pm$ 0.18 | 0.945 |
| LSTM (+LM+NS, L) | 0.951 | 0.162 | 0.953 | 0.957 | 0.904 | 0.749 $\pm$ 0.15 | 0.904 |

**Table 17: Full results on the Odds First language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.966 | 0.122 | 0.968 | 0.966 | 0.537 | 0.592 $\pm$ 0.11 | 0.851 |
| Tf (L) | 0.835 | 0.345 | 0.853 | 0.849 | 0.850 | 0.730 $\pm$ 0.09 | 0.850 |
| Tf (+LM, S) | 0.969 | 0.116 | 0.969 | 0.968 | 0.536 | 0.559 $\pm$ 0.07 | 0.754 |
| Tf (+LM, L) | 0.958 | 0.207 | 0.924 | 0.959 | 0.561 | 0.613 $\pm$ 0.09 | 0.763 |
| Tf (+NS, S) | 0.993 | 0.048 | 0.991 | 0.993 | 0.545 | 0.537 $\pm$ 0.00 | 0.545 |
| Tf (+NS, L) | 0.941 | 0.236 | 0.919 | 0.944 | 0.861 | 0.724 $\pm$ 0.11 | 0.861 |
| Tf (+LM+NS, S) | 0.995 | 0.043 | 0.991 | 0.998 | 0.538 | 0.579 $\pm$ 0.08 | 0.799 |
| Tf (+LM+NS, L) | 0.955 | 0.182 | 0.937 | 0.952 | 0.864 | 0.693 $\pm$ 0.11 | 0.864 |
| RNN (S) | 0.966 | 0.119 | 0.968 | 0.966 | 0.544 | 0.793 $\pm$ 0.15 | 0.948 |
| RNN (L) | 0.957 | 0.137 | 0.962 | 0.959 | 0.948 | 0.795 $\pm$ 0.12 | 0.948 |
| RNN (+LM, S) | 0.968 | 0.119 | 0.969 | 0.968 | 0.542 | 0.708 $\pm$ 0.14 | 0.948 |
| RNN (+LM, L) | 0.959 | 0.137 | 0.963 | 0.959 | 0.948 | 0.766 $\pm$ 0.15 | 0.948 |
| RNN (+NS, S) | 0.959 | 0.138 | 0.963 | 0.959 | 0.948 | 0.789 $\pm$ 0.18 | 0.948 |
| RNN (+NS, L) | 0.967 | 0.116 | 0.972 | 0.967 | 0.594 | 0.712 $\pm$ 0.15 | 0.948 |
| RNN (+LM+NS, S) | 0.969 | 0.117 | 0.969 | 0.968 | 0.536 | 0.575 $\pm$ 0.08 | 0.777 |
| RNN (+LM+NS, L) | 0.957 | 0.138 | 0.961 | 0.959 | 0.669 | 0.758 $\pm$ 0.14 | 0.947 |
| LSTM (S) | 0.969 | 0.116 | 0.969 | 0.968 | 0.572 | 0.668 $\pm$ 0.14 | 0.921 |
| LSTM (L) | 0.969 | 0.102 | 0.974 | 0.968 | 0.838 | 0.718 $\pm$ 0.15 | 0.914 |
| LSTM (+LM, S) | 0.969 | 0.115 | 0.969 | 0.968 | 0.617 | 0.612 $\pm$ 0.10 | 0.857 |
| LSTM (+LM, L) | 0.969 | 0.103 | 0.974 | 0.968 | 0.701 | 0.687 $\pm$ 0.10 | 0.853 |
| LSTM (+NS, S) | 0.997 | 0.014 | 0.997 | 0.997 | 0.575 | 0.595 $\pm$ 0.13 | 0.936 |
| LSTM (+NS, L) | 0.969 | 0.104 | 0.974 | 0.968 | 0.611 | 0.673 $\pm$ 0.12 | 0.906 |
| LSTM (+LM+NS, S) | 0.997 | 0.027 | 0.995 | 0.993 | 0.565 | 0.597 $\pm$ 0.09 | 0.848 |
| LSTM (+LM+NS, L) | 0.969 | 0.103 | 0.974 | 0.968 | 0.964 | 0.696 $\pm$ 0.13 | 0.964 |

**Table 18: Full results on the Binary Addition language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.925 | 0.235 | 0.919 | 0.922 | 0.673 | 0.643 $\pm$ 0.13 | 0.913 |
| Tf (L) | 0.915 | 0.262 | 0.902 | 0.915 | 0.645 | 0.654 $\pm$ 0.09 | 0.778 |
| Tf (+LM, S) | 0.974 | 0.107 | 0.963 | 0.962 | 0.562 | 0.602 $\pm$ 0.10 | 0.913 |
| Tf (+LM, L) | 0.933 | 0.228 | 0.917 | 0.925 | 0.744 | 0.713 $\pm$ 0.09 | 0.876 |
| Tf (+NS, S) | 0.976 | 0.084 | 0.977 | 0.968 | 0.632 | 0.629 $\pm$ 0.13 | 0.914 |
| Tf (+NS, L) | 0.924 | 0.248 | 0.910 | 0.924 | 0.831 | 0.692 $\pm$ 0.10 | 0.831 |
| Tf (+LM+NS, S) | 0.975 | 0.094 | 0.968 | 0.966 | 0.577 | 0.615 $\pm$ 0.11 | 0.896 |
| Tf (+LM+NS, L) | 0.967 | 0.154 | 0.944 | 0.960 | 0.850 | 0.684 $\pm$ 0.11 | 0.854 |
| RNN (S) | 0.924 | 0.227 | 0.922 | 0.921 | 0.549 | 0.719 $\pm$ 0.10 | 0.879 |
| RNN (L) | 0.927 | 0.236 | 0.915 | 0.924 | 0.598 | 0.813 $\pm$ 0.08 | 0.878 |
| RNN (+LM, S) | 0.943 | 0.194 | 0.931 | 0.940 | 0.566 | 0.718 $\pm$ 0.15 | 0.893 |
| RNN (+LM, L) | 0.929 | 0.235 | 0.916 | 0.925 | 0.822 | 0.703 $\pm$ 0.14 | 0.914 |
| RNN (+NS, S) | 0.988 | 0.085 | 0.979 | 0.981 | 0.604 | 0.743 $\pm$ 0.12 | 0.915 |
| RNN (+NS, L) | 0.930 | 0.226 | 0.914 | 0.928 | 0.731 | 0.790 $\pm$ 0.12 | 0.915 |
| RNN (+LM+NS, S) | 0.978 | 0.094 | 0.974 | 0.968 | 0.604 | 0.675 $\pm$ 0.10 | 0.898 |
| RNN (+LM+NS, L) | 0.939 | 0.214 | 0.923 | 0.934 | 0.903 | 0.762 $\pm$ 0.12 | 0.914 |
| LSTM (S) | 0.929 | 0.220 | 0.925 | 0.925 | 0.595 | 0.745 $\pm$ 0.12 | 0.916 |
| LSTM (L) | 0.929 | 0.233 | 0.916 | 0.925 | 0.651 | 0.783 $\pm$ 0.09 | 0.915 |
| LSTM (+LM, S) | 0.989 | 0.081 | 0.979 | 0.969 | 0.685 | 0.702 $\pm$ 0.12 | 0.914 |
| LSTM (+LM, L) | 0.951 | 0.210 | 0.923 | 0.952 | 0.692 | 0.780 $\pm$ 0.09 | 0.915 |
| LSTM (+NS, S) | 0.988 | 0.083 | 0.981 | 0.976 | 0.648 | 0.709 $\pm$ 0.13 | 0.902 |
| LSTM (+NS, L) | 0.929 | 0.233 | 0.916 | 0.925 | 0.916 | 0.750 $\pm$ 0.14 | 0.916 |
| LSTM (+LM+NS, S) | 0.992 | 0.074 | 0.981 | 0.982 | 0.581 | 0.715 $\pm$ 0.12 | 0.866 |
| LSTM (+LM+NS, L) | 0.986 | 0.115 | 0.966 | 0.978 | 0.820 | 0.786 $\pm$ 0.11 | 0.916 |

**Table 19: Full results on the Binary Multiplication language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.959 | 0.118 | 0.958 | 0.952 | 0.563 | 0.616 $\pm$ 0.12 | 0.889 |
| Tf (L) | 0.933 | 0.216 | 0.916 | 0.928 | 0.720 | 0.705 $\pm$ 0.09 | 0.821 |
| Tf (+LM, S) | 0.973 | 0.082 | 0.974 | 0.968 | 0.627 | 0.573 $\pm$ 0.03 | 0.627 |
| Tf (+LM, L) | 0.932 | 0.255 | 0.899 | 0.931 | 0.582 | 0.688 $\pm$ 0.10 | 0.807 |
| Tf (+NS, S) | 0.975 | 0.071 | 0.977 | 0.958 | 0.760 | 0.700 $\pm$ 0.11 | 0.922 |
| Tf (+NS, L) | 0.952 | 0.165 | 0.941 | 0.949 | 0.723 | 0.703 $\pm$ 0.11 | 0.923 |
| Tf (+LM+NS, S) | 0.983 | 0.054 | 0.979 | 0.970 | 0.617 | 0.642 $\pm$ 0.12 | 0.884 |
| Tf (+LM+NS, L) | 0.972 | 0.169 | 0.933 | 0.961 | 0.615 | 0.637 $\pm$ 0.07 | 0.787 |
| RNN (S) | 0.937 | 0.168 | 0.944 | 0.930 | 0.606 | 0.745 $\pm$ 0.13 | 0.919 |
| RNN (L) | 0.936 | 0.194 | 0.934 | 0.931 | 0.889 | 0.801 $\pm$ 0.07 | 0.893 |
| RNN (+LM, S) | 0.980 | 0.063 | 0.980 | 0.969 | 0.604 | 0.672 $\pm$ 0.13 | 0.897 |
| RNN (+LM, L) | 0.936 | 0.192 | 0.934 | 0.931 | 0.597 | 0.736 $\pm$ 0.12 | 0.919 |
| RNN (+NS, S) | 0.963 | 0.122 | 0.958 | 0.955 | 0.559 | 0.684 $\pm$ 0.14 | 0.919 |
| RNN (+NS, L) | 0.935 | 0.195 | 0.934 | 0.931 | 0.645 | 0.750 $\pm$ 0.14 | 0.919 |
| RNN (+LM+NS, S) | 0.982 | 0.060 | 0.978 | 0.973 | 0.610 | 0.714 $\pm$ 0.15 | 0.919 |
| RNN (+LM+NS, L) | 0.956 | 0.190 | 0.937 | 0.945 | 0.910 | 0.784 $\pm$ 0.10 | 0.916 |
| LSTM (S) | 0.946 | 0.145 | 0.951 | 0.939 | 0.616 | 0.734 $\pm$ 0.10 | 0.902 |
| LSTM (L) | 0.937 | 0.189 | 0.933 | 0.933 | 0.774 | 0.712 $\pm$ 0.06 | 0.792 |
| LSTM (+LM, S) | 0.995 | 0.019 | 0.994 | 0.983 | 0.610 | 0.664 $\pm$ 0.10 | 0.898 |
| LSTM (+LM, L) | 0.961 | 0.155 | 0.943 | 0.952 | 0.876 | 0.759 $\pm$ 0.12 | 0.897 |
| LSTM (+NS, S) | 0.992 | 0.046 | 0.987 | 0.980 | 0.652 | 0.779 $\pm$ 0.12 | 0.919 |
| LSTM (+NS, L) | 0.961 | 0.165 | 0.942 | 0.966 | 0.890 | 0.784 $\pm$ 0.11 | 0.915 |
| LSTM (+LM+NS, S) | 0.997 | 0.031 | 0.994 | 0.986 | 0.639 | 0.638 $\pm$ 0.07 | 0.756 |
| LSTM (+LM+NS, L) | 0.971 | 0.123 | 0.953 | 0.966 | 0.771 | 0.688 $\pm$ 0.10 | 0.915 |

**Table 20: Full results on the Compute Sqrt language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.956 | 0.130 | 0.954 | 0.948 | 0.718 | 0.673 $\pm$ 0.10 | 0.828 |
| Tf (L) | 0.937 | 0.254 | 0.898 | 0.926 | 0.629 | 0.705 $\pm$ 0.10 | 0.860 |
| Tf (+LM, S) | 0.971 | 0.100 | 0.964 | 0.960 | 0.629 | 0.623 $\pm$ 0.10 | 0.885 |
| Tf (+LM, L) | 0.911 | 0.264 | 0.887 | 0.906 | 0.629 | 0.648 $\pm$ 0.09 | 0.782 |
| Tf (+NS, S) | 0.973 | 0.101 | 0.967 | 0.967 | 0.578 | 0.631 $\pm$ 0.11 | 0.852 |
| Tf (+NS, L) | 0.953 | 0.205 | 0.919 | 0.947 | 0.645 | 0.639 $\pm$ 0.06 | 0.739 |
| Tf (+LM+NS, S) | 0.970 | 0.094 | 0.968 | 0.963 | 0.592 | 0.648 $\pm$ 0.11 | 0.856 |
| Tf (+LM+NS, L) | 0.960 | 0.177 | 0.932 | 0.952 | 0.811 | 0.695 $\pm$ 0.11 | 0.846 |
| RNN (S) | 0.892 | 0.280 | 0.897 | 0.884 | 0.887 | 0.784 $\pm$ 0.12 | 0.887 |
| RNN (L) | 0.892 | 0.306 | 0.878 | 0.884 | 0.773 | 0.699 $\pm$ 0.13 | 0.887 |
| RNN (+LM, S) | 0.976 | 0.110 | 0.965 | 0.975 | 0.647 | 0.681 $\pm$ 0.15 | 0.882 |
| RNN (+LM, L) | 0.911 | 0.281 | 0.893 | 0.898 | 0.806 | 0.776 $\pm$ 0.09 | 0.878 |
| RNN (+NS, S) | 0.982 | 0.099 | 0.976 | 0.982 | 0.636 | 0.720 $\pm$ 0.15 | 0.887 |
| RNN (+NS, L) | 0.894 | 0.301 | 0.874 | 0.884 | 0.709 | 0.767 $\pm$ 0.08 | 0.887 |
| RNN (+LM+NS, S) | 0.987 | 0.080 | 0.979 | 0.983 | 0.644 | 0.638 $\pm$ 0.10 | 0.887 |
| RNN (+LM+NS, L) | 0.917 | 0.283 | 0.888 | 0.910 | 0.816 | 0.715 $\pm$ 0.14 | 0.887 |
| LSTM (S) | 0.892 | 0.278 | 0.897 | 0.884 | 0.853 | 0.836 $\pm$ 0.07 | 0.887 |
| LSTM (L) | 0.892 | 0.307 | 0.878 | 0.883 | 0.887 | 0.799 $\pm$ 0.07 | 0.887 |
| LSTM (+LM, S) | 0.995 | 0.043 | 0.989 | 0.989 | 0.658 | 0.653 $\pm$ 0.15 | 0.887 |
| LSTM (+LM, L) | 0.985 | 0.123 | 0.959 | 0.982 | 0.610 | 0.697 $\pm$ 0.13 | 0.887 |
| LSTM (+NS, S) | 0.986 | 0.076 | 0.976 | 0.978 | 0.576 | 0.795 $\pm$ 0.10 | 0.887 |
| LSTM (+NS, L) | 0.915 | 0.293 | 0.869 | 0.914 | 0.729 | 0.830 $\pm$ 0.07 | 0.887 |
| LSTM (+LM+NS, S) | 0.995 | 0.036 | 0.991 | 0.994 | 0.659 | 0.614 $\pm$ 0.08 | 0.831 |
| LSTM (+LM+NS, L) | 0.984 | 0.140 | 0.944 | 0.981 | 0.613 | 0.679 $\pm$ 0.11 | 0.887 |

**Table 21: Full results on the Bucket Sort language.**
| Model | Train | Val. CE $\downarrow$ | Val. | S. Test | L. Test | L. Test (Mean) | L. Test (Max) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Tf (S) | 0.974 | 0.107 | 0.973 | 0.963 | 0.569 | 0.629 $\pm$ 0.08 | 0.764 |
| Tf (L) | 0.821 | 0.417 | 0.806 | 0.824 | 0.670 | 0.727 $\pm$ 0.03 | 0.756 |
| Tf (+LM, S) | 0.986 | 0.029 | 0.989 | 0.977 | 0.556 | 0.590 $\pm$ 0.10 | 0.858 |
| Tf (+LM, L) | 0.988 | 0.094 | 0.973 | 0.975 | 0.837 | 0.706 $\pm$ 0.11 | 0.880 |
| Tf (+NS, S) | 0.976 | 0.077 | 0.978 | 0.977 | 0.891 | 0.616 $\pm$ 0.12 | 0.891 |
| Tf (+NS, L) | 0.945 | 0.200 | 0.920 | 0.936 | 0.878 | 0.709 $\pm$ 0.13 | 0.884 |
| Tf (+LM+NS, S) | 0.997 | 0.008 | 0.999 | 0.992 | 0.553 | 0.603 $\pm$ 0.10 | 0.874 |
| Tf (+LM+NS, L) | 0.960 | 0.168 | 0.947 | 0.948 | 0.579 | 0.572 $\pm$ 0.02 | 0.629 |
| RNN (S) | 0.967 | 0.132 | 0.966 | 0.953 | 0.911 | 0.766 $\pm$ 0.09 | 0.911 |
| RNN (L) | 0.945 | 0.181 | 0.942 | 0.929 | 0.757 | 0.769 $\pm$ 0.14 | 0.897 |
| RNN (+LM, S) | 0.990 | 0.063 | 0.984 | 0.977 | 0.575 | 0.647 $\pm$ 0.12 | 0.880 |
| RNN (+LM, L) | 0.960 | 0.128 | 0.965 | 0.953 | 0.630 | 0.706 $\pm$ 0.10 | 0.908 |
| RNN (+NS, S) | 0.965 | 0.138 | 0.964 | 0.957 | 0.924 | 0.778 $\pm$ 0.13 | 0.924 |
| RNN (+NS, L) | 0.962 | 0.126 | 0.966 | 0.954 | 0.957 | 0.771 $\pm$ 0.15 | 0.957 |
| RNN (+LM+NS, S) | 0.962 | 0.142 | 0.962 | 0.950 | 0.930 | 0.836 $\pm$ 0.09 | 0.951 |
| RNN (+LM+NS, L) | 0.960 | 0.129 | 0.965 | 0.953 | 0.613 | 0.690 $\pm$ 0.09 | 0.869 |
| LSTM (S) | 0.969 | 0.095 | 0.966 | 0.966 | 0.546 | 0.688 $\pm$ 0.13 | 0.967 |
| LSTM (L) | 0.971 | 0.109 | 0.970 | 0.956 | 0.813 | 0.700 $\pm$ 0.09 | 0.813 |
| LSTM (+LM, S) | 0.998 | 0.013 | 0.997 | 0.991 | 0.592 | 0.645 $\pm$ 0.10 | 0.774 |
| LSTM (+LM, L) | 0.999 | 0.003 | 1.000 | 0.998 | 0.605 | 0.621 $\pm$ 0.10 | 0.769 |
| LSTM (+NS, S) | 0.996 | 0.015 | 0.998 | 0.992 | 0.576 | 0.572 $\pm$ 0.04 | 0.664 |
| LSTM (+NS, L) | 0.979 | 0.087 | 0.980 | 0.968 | 0.592 | 0.588 $\pm$ 0.04 | 0.671 |
| LSTM (+LM+NS, S) | 0.992 | 0.039 | 0.991 | 0.984 | 0.569 | 0.554 $\pm$ 0.03 | 0.597 |
| LSTM (+LM+NS, L) | 0.989 | 0.075 | 0.982 | 0.981 | 0.594 | 0.640 $\pm$ 0.09 | 0.835 |

## Appendix G Edit distance from languages

In this section, we give a formal definition of string–language edit distance and provide an algorithm for computing it for regular languages.

###### Definition 9 .

For any string ${w}$ and language ${L}$, the edit distance ${\mathcal{D}}({w},{L})$ is defined as

$$ ${\mathcal{D}}({w},{L})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}} \min_{{u}\in{L}}{\mathcal{D}}({w},{u}),$ (20) $$

where ${\mathcal{D}}({w},{u})$ is the Levenshtein distance between ${w}$ and ${u}$, or the minimal number of single-symbol edits (insertions, deletions, and replacements) required to transform ${w}$ into ${u}$.

Suppose ${L}$ is a regular language over alphabet ${\Sigma}$ recognized by DFA ${\mathcal{A}}$. Then for any ${w}\in{{\Sigma}^{\ast}}$, ${\mathcal{D}}({w},{L})$ can be computed as follows:

- 1.
Construct a nondeterministic weighted finite automaton (WFA) ${{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}}$ over the tropical semiring $({{{\mathbb{R}}_{\geq 0}}}\cup\{\infty\},\min,+,\infty,0)$ that assigns weight ${\mathcal{D}}({w},{u})$ to every string ${u}$ (Figure 2);
- 2.
Lift ${\mathcal{A}}$ to the tropical semiring by assigning weight 0 to all transitions and accept states, resulting in a WDFA ${{{\mathcal{A}}}_{\cdot\in{L}}}$;
- 3.
Intersect ${{{\mathcal{A}}}_{\cdot\in{L}}}$ and ${{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}}$ using the standard WFA intersection algorithm (Mohri, ), resulting in an automaton ${{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}}$ that encodes ${\mathcal{D}}({w},{u})$ for every ${u}\in{L}$; and
- 4.
Compute the shortest path in ${{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}}$ using the Floyd–Warshall algorithm (Floyd, ; Warshall, ).

The rest of this section describes these steps in more detail and argues their correctness.

###### Definition 9 .

### G.1 Weighted finite automata

We start by defining WFAs, which are used in multiple steps. This is a more general, nondeterministic version of Def. 4.

###### Definition 10 .

A weighted finite automaton (WFA) over semiring $({{\mathbb{K}}},\oplus,\otimes,{\bm{0}},{\bm{1}})$ is a tuple ${{\mathcal{A}}}=({Q},{\Sigma},{\delta},{{q_{0}}},{\rho})$ such that
(i) ${Q}$is a finite set of states;
(ii) ${\Sigma}$is an alphabet;
(iii) ${\delta}\colon{Q}\times({\Sigma}\cup\{{\varepsilon}\})\times{Q}\rightarrow{{
\mathbb{K}}}$is the transition function; and
(iv) ${{q_{0}}}\in{Q}$is the start state(^5^55Some definitions use an initial weight function $\lambda\colon{Q}\rightarrow{{\mathbb{K}}}$ to indicate start states. For simplicity, we assume one start state with a weight of ${\bm{1}}$.); and
(v) ${\rho}\colon{Q}\rightarrow{{\mathbb{K}}}$is the accept weight function.
If ${\delta}({{q}},{a},{r})={w}$, we say that ${{\mathcal{A}}}$ has a transition from ${{q}}$ to ${r}$ that scans ${a}$ with weight ${w}$, and we write ${{q}}\xrightarrow{{a}/{w}}{r}\in{\delta}$.

This definition is nondeterministic in the sense that it permits multiple outgoing transitions on the same symbol from the same state. We define paths and path weights in a similar way to § 2.2.

###### Definition 11 .

A path ${\pi}$ in WFA ${{\mathcal{A}}}$ is a sequence of states and transitions

$$ ${\pi}={r}_{0}\xrightarrow{{a}_{1}/{w}_{1}}{r}_{1}\cdots{r}_{{m}-1}\xrightarrow {{a}_{{m}}/{w}_{{m}}}{r}_{{m}}$ (21) $$

such that

- 1.
${r}_{0}={{q_{0}}}$, and
- 2.
for all $i=0,\ldots,{m}-1$, ${r}_{i}\xrightarrow{{a}_{i+1}/{w}_{i+1}}{r}_{i+1}\in{\delta}$.

We say that ${\pi}$ scans the string ${a}_{1}\cdots{a}_{{m}}$, and that the path weight of ${\pi}$ is

$$ ${\mathbf{w}}({\pi})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}} \left(\bigotimes_{i=1}^{{m}}{w}_{i}\right)\otimes{\rho}({r}_{{m}}).$ (22) $$

Note that in a nondeterministic WFA, multiple paths may scan the same string. We denote the set of all paths of ${{\mathcal{A}}}$ as ${\Pi}({{\mathcal{A}}})$ and the set of paths that scan ${w}$ as ${\Pi}({{\mathcal{A}}},{w})$.

The weight that a WFA assigns to a string is the sum of the weights of all paths that scan that string.

###### Definition 12 .

The stringsum of string ${w}\in{{\Sigma}^{\ast}}$ under WFA ${{\mathcal{A}}}$ is

$$ ${{\mathcal{A}}}({w})\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}} \bigoplus_{{\pi}\in{\Pi}({{\mathcal{A}}},{w})}{\mathbf{w}}({\pi}).$ (23) $$

We also make use of the sum of the weights of all paths in a WFA.

###### Definition 13 .

The allsum of WFA ${{\mathcal{A}}}$ is

$$ $\displaystyle{Z}({{\mathcal{A}}})$ $\displaystyle\mathrel{\stackrel{{\scriptstyle\textnormal{def}}}{{=}}}\bigoplus _{{\pi}\in{\Pi}({{\mathcal{A}}})}{\mathbf{w}}({\pi})$ (24a) $\displaystyle=\bigoplus_{{w}\in{{\Sigma}^{\ast}}}{{\mathcal{A}}}({w}).$ (24b) $$

###### Definition 10 .

###### Definition 11 .

###### Definition 12 .

###### Definition 13 .

### G.2 Algorithm details

First, we encode the input string ${w}={{w}_{1}}{{w}_{2}}\cdots{{w}_{{n}}}$ into a chain-like WFA ${{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}}$ in the tropical semiring, as shown in Figure 2.

Figure: Figure 2: Diagram of ${{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}}$. The double-circled state has accept weight 0; the others have accept weight $\infty$.

Given an input string ${u}\in{{\Sigma}^{\ast}}$, every path in ${{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}}$ that scans ${u}$ encodes a way of transforming ${w}$ into ${u}$. Every time a transition deviates from scanning ${w}$ by inserting, replacing, or deleting a symbol, it incurs a cost of 1. Taking the minimum weight of any path that scans ${u}$ gives ${\mathcal{D}}({w},{u})$.

###### Lemma 1 .

For all ${u}\in{{\Sigma}^{\ast}}$, ${{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}}({u})={\mathcal{D}}({w},{u})$.

###### Proof.

For every ${{w}_{i}}$ in ${w}$, ${{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}}$ either matches a symbol in ${u}$ with ${{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}}$ with cost 0, simulates the deletion of ${{w}_{i}}$ with cost 1 so that it can continue scanning ${u}$ some other way, or simulates the replacement of ${{w}_{i}}$ with a symbol in ${u}$ with cost 1. Before and after symbols in ${w}$, ${{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}}$ can also simulate the insertion of any number of symbols, each with cost 1. So, a path is in ${\Pi}({{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}},{u})$ iff it corresponds to a way of changing ${w}$ into ${u}$, and its weight is the number of edits it performs to turn ${w}$ into ${u}$. The stringsum gives the minimum number of edits.

$$ $\displaystyle{{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}}({u})$ $\displaystyle=\bigoplus_{{\pi}\in{\Pi}({{{\mathcal{A}}}_{{\mathcal{D}}({w}, \cdot)}},{u})}{\mathbf{w}}({\pi})$ (25a) $\displaystyle=\min_{{\pi}\in{\Pi}({{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}} ,{u})}{\mathbf{w}}({\pi})$ (25b) $\displaystyle={\mathcal{D}}({w},{u})$ (25c) $$

∎

Next, we lift the weights of ${\mathcal{A}}$ into the tropical semiring, resulting in a WDFA ${{{\mathcal{A}}}_{\cdot\in{L}}}$. The weights of all transitions and the accept weights of all accept states in ${\mathcal{A}}$ are set to 0 in ${{{\mathcal{A}}}_{\cdot\in{L}}}$. All other weights are set to $\infty$. So, ${{{\mathcal{A}}}_{\cdot\in{L}}}$ assigns weight 0 to all strings in ${L}$, and weight $\infty$ to all others.

###### Lemma 2 .

For all ${u}\in{{\Sigma}^{\ast}}$,

$$ ${{{\mathcal{A}}}_{\cdot\in{L}}}({u})=\begin{cases}0&\text{if }{u}\in{L}\\ \infty&\text{otherwise.}\end{cases}$ (26) $$

###### Proof.

By definition, ${\mathcal{A}}$ has a path that scans ${u}$ iff ${u}\in{L}$. By construction, ${{{\mathcal{A}}}_{\cdot\in{L}}}$ has a path that scans ${u}$ with weight 0 iff ${\mathcal{A}}$ has a path that scans ${u}$. Therefore, if ${u}\in{L}$, the stringsum ${{{\mathcal{A}}}_{\cdot\in{L}}}({u})$ is the minimum of one or more path weights of 0, so it is 0. Otherwise, the stringsum is a summation over an empty set of path weights, which is defined to be $\infty$ in the tropical semiring.
∎

Next, we intersect ${{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot)}}$ and ${{{\mathcal{A}}}_{\cdot\in{L}}}$ using the standard intersection algorithm for WFAs, resulting in a WFA ${{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}}$ that assigns weight ${\mathcal{D}}({w},{u})$ to ${u}$ if ${u}\in{L}$ and $\infty$ otherwise.

###### Lemma 3 .

For all ${u}\in{{\Sigma}^{\ast}}$,

$$ ${{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}}({u})=\begin{cases}{\mathcal{D}}({ w},{u})&\text{if }{u}\in{L}\\ \infty&\text{otherwise.}\end{cases}$ (27) $$

###### Proof.

By definition of intersection, the stringsum of the intersected automaton is

$$ ${{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}}({u})\mathrel{\stackrel{{ \scriptstyle\textnormal{def}}}{{=}}}{{{\mathcal{A}}}_{{\mathcal{D}}({w},\cdot) }}({u})\otimes{{{\mathcal{A}}}_{\cdot\in{L}}}({u}).$ (28) $$

Using Lemmas 1, 2 and 28, we have

$$ $\displaystyle{{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}}({u})$ $\displaystyle=\begin{cases}{\mathcal{D}}({w},{u})+0&\text{if }{u}\in{L}\\ {\mathcal{D}}({w},{u})+\infty&\text{otherwise}\end{cases}$ (29a) $\displaystyle=\begin{cases}{\mathcal{D}}({w},{u})&\text{if }{u}\in{L}\\ \infty&\text{otherwise.}\end{cases}$ (29b) $$

∎

Finally, we compute the allsum of ${{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}}$, which gives us the minimum edit distance from ${w}$ to any string ${u}\in{L}$. Let ${{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}}=({Q},{\Sigma},{\delta},{{q_{0}}},
{\rho})$. To compute the allsum, we first use the Floyd–Warshall all-pairs shortest path algorithm(^6^66This is a special case of Lehmann’s algorithm (Algorithm 4). The only difference is that we do not need to compute the star operation in Algorithm 4, line 7, which is always 0 in the tropical semiring.) to compute the shortest path weight from ${{q_{0}}}$ to ${r}$, denoted ${A}[{{q_{0}}},{r}]$, for every ${r}\in{Q}$. We then compute the allsum as

$$ $\displaystyle{Z}({{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}})$ $\displaystyle=\bigoplus_{{r}\in{Q}}{A}[{{q_{0}}},{r}]\otimes{\rho}({r})$ (30a) $\displaystyle=\min_{{r}\in{Q}}{A}[{{q_{0}}},{r}]+{\rho}({r}).$ (30b) $$

This gives us the edit distance ${\mathcal{D}}({w},{L})$.

###### Theorem 1 .

${Z}({{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}})={\mathcal{D}}({w},{L})$.

###### Proof.

By definition, the allsum is

$$ ${Z}({{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}})\mathrel{\stackrel{{ \scriptstyle\textnormal{def}}}{{=}}}\bigoplus_{{u}\in{{\Sigma}^{\ast}}}{{{ \mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}}({u}).$ (31) $$

Using Lemmas 3 and 9, we have

$$ $\displaystyle{Z}({{{\mathcal{A}}}_{{\mathcal{D}}(\cdot,{L})}})$ $\displaystyle=\min_{{u}\in{{\Sigma}^{\ast}}}{{{\mathcal{A}}}_{{\mathcal{D}}( \cdot,{L})}}({u})$ (32a) $\displaystyle=\min_{{u}\in{L}}{\mathcal{D}}({w},{u})$ (32b) $\displaystyle={\mathcal{D}}({w},{L}).$ (32c) $$

∎

###### Lemma 1 .

###### Proof.

###### Lemma 2 .

###### Proof.

###### Lemma 3 .

###### Proof.

###### Theorem 1 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Please check my questions in the above section.
soundness: 3
strengths: The strength of the paper lies in its motivation to quantify gaps between different architectures by formal language recognition tasks. The authors start with a discussion on the basis of formal language theory, and how existing works differ from this basis in their experimental settings. Then, they propose a novel data generation algorithm that can sample positive and hard negative samples from each formal language. The algorithm has been discussed in great detail, and the running time has been contrasted with naive data generation algorithms.

The authors then conduct extensive comparisons of RNNs, LSTMs, and transformers across a wide suite of formal languages. Interestingly, RNNs and LSTMs generally perform better. Other interesting observations include (a) transformers can't learn Dyck-(2,3), as opposed to the results of Yao et al. (2021), and (b) the order of ranking between the different architectures is different from Deletang et al. (2023). The work emphasizes the need for empirical validations that align with theoretical results for a clearer understanding of neural network capabilities.
summary: The paper explores formal language recognition tasks with different architectures. The authors argue that the primary motivation underlying formal language theory is language recognition and not next token prediction as used by existing literature. As such, they propose a novel data generation algorithm that can generate positive and hard negative examples from a diverse set of formal languages. Finally, through extensive experiments, they show that RNNs and LSTMs generally outperform transformer architectures.
weaknesses: As such, the work doesn't have many weaknesses. I have a couple of questions regarding the setup.

a) **Behavior with input length**
- The authors report aggregated scores over strings of all lengths. It would be interesting to include a discussion on input length v/s performance for different models. Are there tasks where the transformer's performance shows a more exponential/drastic drop with input length? 

b) **Tasks where additional loss terms hurt:** 
- Are there tasks where the additional language model loss and the next symbol loss hurt performance? For example, for parity, language model loss can intuitively hurt performance as the token at each step could be randomly selected for each string. 
- Furthermore, how do the optimal $\lambda$ hyper-parameters behave for different tasks for different models? Are there cases, where the additional losses help one architecture more than others?

c) **How is 64k parameters and 5 layers decided for the experiments?** What happens for smaller and wider models?

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
questions: 1. Can you clarify the contribution of this work in light of previous work on language recognition with neural networks? For instance, the authors of [2] have evaluated with larger datasets and have trained many more models. How does your contribution differ in terms of language classes tested and insights derived therefrom? Are there other aspects of your work that can be highlighted?
2. Have you considered investigating the scaling properties of the neural networks on the language recognition task? [1] demonstrated that none of the networks in your study are able to perform transduction on recursively enumerable languages without the support of an external memory module (e.g. Stack-RNN or Tape-RNN), but -- with respect to scaling -- only showed that increasing the amount of training data when the network is large enough to memorize the training data did not help generalization for some neural network types. Related: do you have any reason to believe that results you report here that differ in order from e.g. [1] -- such as recognition on cycle navigation -- are not due to the capacity of the network? Would larger networks recognize cycle navigation better?
soundness: 4
strengths: This is a well-performed study of the ability of neural networks to recognize formal languages. The writing is of good quality, the methodology is clearly communicated, and it introduces an efficient algorithm for sampling strings from regular languages. Models are trained with validation sets of length [0, 40] (short) or [0, 80] (long) and tested on a set with strings of length [0, 500]. The authors of this study introduce several additional languages -- Dyck-(2, 3), binary strings that start with 1, and a distinction between marked and unmarked reversed strings -- that do not appear in [1]. The appendix contains copious information about the models trained.
summary: This paper takes a formal language theory approach to string classification and asks how well various types of neural networks recognize languages. The authors evaluate the network types on eighteen formal languages from three of the four languages classes of the Chomsky hierarchy (excluding recursively enumerable languages). Length generalization is tested systematically by using a short and a long validation set, and a test set that comprises much longer strings than in either validation set. They find that recurrent types of networks tend to be more accurate than transformers. The paper contains some analysis of certain languages on which one or more network types exhibits poor performance. The authors additionally describe an algorithm for efficiently sampling strings from a regular language that they describe as concurrent work.

--------

I will refer to the following papers in this review. [1] is relevant because the paper being reviewed here appears to be, at least in part, a response to [1]. [2] is relevant as an example of prior work with substantial overlap in experimental setting and possibly different results. [3] provides theoretical insights into the results reported in Section 4 of the paper reviewed here.

* [1] Neural networks and the chomsky hierarchy, Del{\'e}tang et al, 2023
* [2] MLRegTest: A Benchmark for the Machine Learning of Regular Languages, van der Poel et al, 2024
* [3] Why are Sensitive Functions Hard for Transformers?, Hahn & Rofin, 2024
weaknesses: * The general method for training neural networks as language recognizers is straightforward and is difficult to see as a substantial contribution (see similarities with e.g. [2]).
* The algorithm for efficiently sampling from a regular language is described, and the authors state that they use it for sampling training and evaluation instances from the regular languages (class `R` in Table 1). Since the algorithm is only used to generate data for 25% of the types of languages in this study, the amount of page real estate devoted to it seems disproportionate, particularly since algorithms for sampling from a formal language are not typically showcased in this venue.
* The insights about which languages are best-suited to which network types could be much deeper. With the literature on language recognition having advanced somewhat, reports that explain *the why* (e.g. [3]) are more compelling than those that describe *the what*. The results reported here are similar to [1] on the modular arithmetic language and marked string reversal and differ from [1] on cycle navigation. Some analysis is done here to characterize the kinds of errors transformers make on the task of recognizing strings from the cycle navigation language. The authors describe how with cycle navigation the recognition error of the instances with the highest cross entropy loss is always due to the model recognizing an instance with an incorrect final character (the position in the cycle). Since [1] reports 100% transduction accuracy for cycle navigation for RNN and LSTM, and 62% for a transformer, what explains the ceiling on recognition accuracy for all networks here? The analysis of Dyck-(2, 3) and Repeat 01 seems to primarily indicate that, with transformers,  some negative instances are near the decision boundary to positive instances. More insights about *why* this occurs with transformers and not the other networks would improve the paper.

Nit
* The standard deviation of recognition is a figure of merit for distinguishing neural network types, particularly in cases when no network achieves perfect recognition accuracy. This is included in the appendix. It would be helpful to report in Table 2 mean and stdev of recognition accuracy across multiple runs using the model from the appropriate table in the appendix.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Please refer to the weaknesses part.
soundness: 3
strengths: 1. It is an important direction to study neural networks' computational ability through formal language theory.
2. This paper introduces an efficient algorithm for length-controlled sampling from finite automata, which may have practical value for future research in formal language processing.
3. Experiments are conducted on a variety of formal languages with 3 neural models with different architectures (RNN, LSTM, transformer). The methodology appears to be well-documented and reproducible.
summary: This paper argue that there exists a methodological disconnect between the complexity theory of the formal language and the empirical evaluation of neural networks' computational capabilities. The existing work related the capabilities of neural networks with Chomsky hierarchy, which is framed in terms of language recognition (classifying whether strings belong to a language). However their empirical studies evaluate models on string-to-string transformation tasks instead. This paper propose an experimental setup for training neural networks as recognizers, and a more efficient algorithm for length-controlled sampling from finite automata. The empirical results show that RNNs and LSTMs often perform better than transformers on the formal language recognition task.
weaknesses: 1. The paper overlooks significant existing work on training neural networks for formal language recognition tasks (e.g. [1, 2, 3]). This oversight diminishes the claimed novelty of the proposed experimental setup. The authors should acknowledge and position their work in relation to previous studies.
2. The claimed technical improvement in sampling from finite automata appears to be the main novel contribution, but its significance needs better contextualization.

References       
[1] Bhattamishra, Satwik, Kabir Ahuja, and Navin Goyal. "On the ability and limitations of transformers to recognize formal languages." EMNLP 2020.          
[2] William Merrill. 2019. Sequential Neural Networks as Automata.           
[3] Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. 2020. On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languages.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: Can the length constrained algorithm for DFAs be modified for other automata? I suspect not due to the combinatorial way the paths compose for these other automata, and the infinite nature of the stack, etc.
soundness: 4
strengths: The paper references important work on the theoretical expressibility of Transformers, and other neural architectures, and, along with Deletang et. al. 2023, is useful information for understanding the learnability of these architectures in an empirical way.

It follows a similar set of experiments as the Deletang et. al. 2023 paper, while focusing on the recognition aspect of formal languages, rather than mixing recognition and transduction tasks. This of course comes with some drawbacks (e.g. uninformative training signal), but the authors spend some time addressing that issue with other reasonable auxiliary losses.

The length-constrained sampling from DFAs is an interesting aspect, even if it takes a bit of a detour from the original point of the paper

Understanding the limitations of the neural architectures we use is important, and can only be explored and understood in smaller scale experiments lik
summary: This paper builds on Deletang et. al. 2023, and rigorously tests standard sequence neural architectures for their ability to _recognise_ formal languages that span the Chomsky Hierarchy. It also proposes a way to sample sequences from automata with a length constraint in order to generate training data for the experiment.
weaknesses: I have only minor comments here as I find the paper well-executed:
- Table 2: decide on a threshold and make results above it visually dissimilar, this will give a better idea of where a model sits on these benchmarks and the hierarchy they’re measured to be in
- Missing a more conclusive figure regarding placement of models wrt to their level in the chomsky hierarchy. I know this is a tough ask, since the mapping of these models don’t fit as neatly into the Chomsky hierarchy as Deletang, et. al. 2023 suggest. Perhaps a better visual representation could be figured out.

Meta-review: This submission addresses a fundamental concern in the literature on neural network expressivity: the discrepancy between theoretical claims of what neural architectures can recognize and how these capabilities are tested empirically. The authors propose training neural networks directly as recognizers of formal languages (i.e., binary classification tasks) rather than relying on proxy tasks like language modeling or sequence-to-sequence transduction. They introduce a general and flexible approach for generating both positive and negative samples that can be applied to a wide range of formal languages across different levels of the Chomsky hierarchy. A core technical contribution is an efficient algorithm for length-controlled sampling from regular languages represented as DFAs, which can be extended to more complex automata.

The experiments compare three common architectures—RNNs, LSTMs, and transformers—on a broad set of 18 languages. The authors report that recurrent architectures often achieve better performance than transformers, contradicting some earlier claims that transformers can learn certain complex formal languages with ease. The paper also systematically varies training objectives, comparing purely recognizable (R) losses to mixed objectives that include language modeling (LM) and next-symbol prediction (NS). While no single objective is best across all scenarios, the authors find that simpler binary classification objectives can be quite effective. The authors also carefully distinguish between testing inductive bias vs. testing expressivity.

Strengths:
	•	The authors highlight a significant methodological gap between theoretical claims and empirical evaluations in the literature.
	•	They propose a unified methodology for testing neural networks on actual recognition tasks that are aligned with formal language definitions.
	•	An efficient length-constrained sampling algorithm for DFAs is introduced and analyzed, improving upon existing methods.
	•	Empirical results are provided for a variety of languages (regular to context-sensitive), showing unexpected performance differences, such as RNNs/LSTMs often outperforming transformers.
	•	Extensive responses to reviewers address issues related to novelty, placement relative to prior work (MLRegTest and others), and provide additional results (including performance vs. input length and model scaling).

Decision: Accept (Poster)