Automata Learning and Identification of the Support of Language Models
Authors: Satwik Bhattamishra
Michael Hahn
Varun Kanade
Venue: ICLR 2026 Poster (2026)
Keywords: automata learning
regular languages
learning theory
DFA extraction
language models
Primary area: learning theory

Abstract: We study the learnability of languages in the *Next Symbol Prediction* (NSP) setting, where a learner receives only positive examples from a language together with, for every prefix, (i) whether the prefix itself is in the language and (ii) which next symbols can lead to an accepting string. This setting has been used in prior work to empirically analyze neural sequence models, and additionally, we observe that efficient algorithms for the NSP setting can be used to learn the (truncated) support of language models. We first show that the class of DFAs with at most $n$ states is identifiable from positive examples augmented with these NSP labels. Nevertheless, even with this richer supervision, we show that PAC-learning DFAs remains computationally hard, and exact identification using only membership queries cannot be achieved in polynomial time. We then present $\mathrm{L_{nsp}^{\star}}$, an extension of Angluin’s $\mathrm{L}^{\star}$ algorithm, and show that DFAs can be PAC-learned efficiently using a language-model–based teacher that answers membership queries and generates valid strings conditioned on prefix prompts. Finally, we conduct a comprehensive experimental evaluation on 11 regular languages of varying complexity. Using $\mathrm{L}^{\star}_{\text{nsp}}$, we extract DFAs from Transformer-based language models trained on regular languages to evaluate the algorithm’s effectiveness and identify erroneous examples.

Published as a conference paper at ICLR 2026
AUTOMATA LEARNING AND IDENTIFICATION OF THE SUPPORT OF LANGUAGE MODELS
Satwik Bhattamishra Michael Hahn
Varun Kanade
University Oxford Saarland University
ABSTRACT
We study the learnability of languages in the Next Symbol Prediction (NSP) set- ting, where a learner receives only positive examples from a language together with, for every prefix, (i) whether the prefix itself is in the language and (ii) which next symbols can lead to an accepting string. This setting has been used in prior work empirically analyze neural sequence models, and additionally, that efficient algorithms for the NSP setting can be used to learn the (truncated) support of language models. We first show that the class of DFAs with most n states is identifiable from positive examples augmented with these NSP labels. Nevertheless, even with this richer supervision, we show that PAC-learning DFAs remains computationally hard, and exact identification using only membership queries cannot be achieved in polynomial time. We then present T T. an exten- sion of Angluin's L algorithm, and show that DFAs can be PAC-learned effi- ciently using a linguage-model-based teacher that answers membership queries and generates valid strings conditioned on prefix prompts. Finally, conduct a comprehensive experimental evaluation on 11 regular languages of varying com- plexity. Using Lag. we extract DFAs from Transformer- -basededr---eddddddd language models trained on regular languages to evaluate the algorithm's effectiveness and identify erroneous examples.
observe
INTRODUCTION
Language models (LMs) are now deployed across text, vision, and bioinformatics; yet their internal computation and potential outputs they generate remain difficult to interpret. This motivates basic question: given black-box access to a model, can we extract a compact, interpretable formal object, such as a deterministic finite automaton (DFA), that accepts (approximately) the same strings as those that lie in the model's 's generative support? We develop a formal framework for this problem and study its lcarnability in a setting that closely mirrors how LMs are typically used in practice.
We formalize and study the problem of learnability of languages in the Next Symbol Prediction (NSP) setting. Here learner receives only positive strings from target language, together with rich supervision for every prefix: a membership bit indicating whether the prefix itself in the language and vector of "continuation" bits indicating which next symbols admit some accepting continuation. A prediction is correct only if the hypothesis matches all membership and continuation labels at every prefix of the example.
This setup has a natural interpretation in the context of generative models: when decoding with top- p (Holtzman al., 2019), top-k, min-p (Minh al. 22255) sampling, the per-prefix continuation set is precisely the set of admissible next tokens, and termination corresponds to allowing the end- of-sequence token. In particular, positive-only NSP supervision natural obtain from black-box models and avoids inventing an artificial distribution over negative strings; at the same time, the requirement for correct predictions at every prefix makes the task challenging. Fig. [ illustraate NSP labels on Dyck example and how admissille-next-tkenn sets can be read from an LMM
Additionally, while NSP has been widely used to evaluate sequence models on formal- benchmarks (see e.g. Gers & Schmidhuber (2001); Suzgun et al. (2019; Ebrahimi al. 2020
"Corresponding author. Contact: satw k. bmi amiishrrccs ac..uuuk

---

Published as a conference paper at ICLR 2026
Bhattamishra al. 2020a) and references therein). the learnability of languages under NSP and its relationship to conventional binary classification has not been established.
Our contributions. We investigate the question of learnability in the NSP setting within the com- putational learning theory framework by studying computational complexity and oracle require- ments. We also conduct systematic empirical evaluation with several regular languages, using Transformer- based language models as teachers.
ii Identifiability and hardness. We give PAC-style formulation of learning using NSP labels and show that positive examples augmented with NSP labels are informatiion-thorrtiiaa sufficient to identify minimal DFAs. Concretely, distinct minimal DFAs always disagree on the NSP labeling of some positive string, yielding finite teaching sets and well-defined equivalence oracle in the NSP model. At the same time, we prove that NSP supervision does not remove the key computational barriers for learning regular languages. The key technical argument is construction that renders all but one continuation label uninformative, allowing a reduction to well-known hardness results (Kearns & Valiant 1994). Thus, even with the richer labels, efficient (improper) learning remains computationally intractable (under standard cryptographic assumptions). We further show that iden- tification with membership queries alone cannot be achieved in polynomial time for certain natural DFA families, even when each query returns all NSP labels. Together, these results suggest that while NSP labels offer some benefit, they do not, in general, circumvent computational hardness.
(ii) Learning with a language-model teacher. Motivated by the hardness results, we study a more powerful, though still practically motivated, learning framework based on prefix-conditional gen- eration queries. These can easily be simulated using black-box access to an LM. In addition to membership queries, the learner can issue generative queries that return positively labeled NSP strings conditioned on a prefix prompt. We extend Angluin's 's L.* algorithm (Angluin 1987) to de- sign new algorithm we denote Lap that uses membership and generative queries to construct a DFA consistent with the observed NSP labels. The guarantee is distribution-specifi::: Lisp PAC- learns with respect to the distribution induced by the teacher language model. This perspective is aligned with our goal of identifying the model's (truncated) support and is particularly appealing in the context of generative models, where the target distribution over negative strings is either unde- fined or arbitrary. Conditional generation is both natural capability of modern LMs and turns out to be a powerful query primitive for efficient learning in the NSP framework.
(iii) Empirical evaluation and analysis. We apply the map algorithm to extract DFAs from Trans- former teachers trained on eleven regular languages of varying complexity, including the Tomita grammars, Parity, and bounded Dyck languages. We study how NSP accuracy, the number of ex- tracted states, and runtime scale with the number of positive training strings. Across tasks, a modest amount of positive data with NSP labels typically suffices recover the target automata or their teacher-suppon counterparts. When the teacher is imperfect (e.g.. for Parity, Tomita-5), the ex- tracted DFA reveals systematic errors by identifying strings in the symmetric difference between the target and the teacher's support. Ablations further indicate that the continuation labels are heavily used on languages with transitions to dead states (e.g.. bounded Dyck), leading to improved sample complexity over binary labels alone. These experiments underscore a practical point: while NSP la- bels cannot break worst-case computational barriers, they are easy to obtain from modern sequence models and can be leveraged effectively in practice.
1.1 RELATED WORK
Learnability of DFAs. Classical results show that inferring DFAS from labeled examples is compu- lationally hard- finding the minimum consistent DFA is NP-hard (Gold 1978 Angluin 1978 Pitt
& Warmuth| 1993), and even (improper) PAC learning is intractable under eryptographic assump- tions (Kearns & Valiant 1994). With queries and counterexamples, Angluin (987)) showed that
regular languages are learnable in polynomial time. Under structural assumptions, several works have studied PAC learnability for probabilistic DFAs (Clark & Thollard 2004 Palmer & Goldberg 2007]. The area remains active with recent theory on counterexample handling and lower bounds in the MAT framework (Vaandrager al. 2022 Kruger et al.) (023). We build on this line of re- search by characterizing the Icarnability of DFAs in a new setting relevant to learning the support of language models, and by situating prior empirical analyses of neural nets in the appropriate context.
2

---

Published as a conference paper at ICLR 2026
00O0 2B
0
1, 1. 0,
1,,00,
0,,1,
min-p 2 .15
[0.25 0.25 0.35 0.05 0.1]
[1, 1,100,0,01
1,,00
Language Model
Label order
1,
ia allowed next symbol
Preftx is the langagg
BKS
Left: An example of string with NSP labels from the Dyck-2 language. The language consists of well-balanced parentheses with two types of brackets. Right: An illustration of how NSP labels can be obtained from language model. See Section 2 for details.
Figure 1:
Automata extraction from neural models was introduced by Giles et al. (1992); Omlin Giles
(1996) and has been active field (Wang et al. 201 8 Muškardin et al. 2022). Notably, Weiss et al.
2018 developed a method for white-box extraction based on L.", and several subsequent works
have focused on weighted automata/PDFAs (Weiss et al. 2019 Wei et al. 2024 Eyraud & Ayache,
2024). Recent work (Zhang et al. 2024) has also explored L like methods for Transformer-bas
classifiers. Mayr al. (2023) learn PDFA abstraction of an LM via a distributional congruence. Our focus is on support identification, where we characterize learnailityy and conduct empirical
analysis based
provable extension of the L algorithm.
PROBLEM DEFINITION
Notation. A deterministic finite automaton (DFA) is tuple A = (Q, E, 6, go, FA) with finite state
set Q, alphabet Σ, transition function ó x - Q. start state Qo- and subset of accepting states FA C Q. The language of A is LA D;; write A(x) La(x) E {0, 13. Fix order 2 ( For x = W1 WN, . let the length-n prefix be F.n := w1 .. w, for 0 S n S N. We use Grtend for a dead state with 8 ((gaead; o)) = Qdead for all E Σ (unique, if present, in a minimal DFA). We use DFA, to denote DFAs with at most states.
2.1 NEXT SYMBOL PREDICTION (NSP) SETTING
For language C 5>* and any x E Σ", E E, define the continuation bit
(1( = I[ E s.L. O.
If L is regular with minimal DFA A, then with q 8(ga, x) have & (2, Of and only 5(g, .) = Idead- The continuation vector at is defined as (g(()) = (1),
miine E {0, 1) الار For strings E D*, write (z)) == * x)) and (I) = ()(g..)),,
positive Nab-labeled example is string x = w1 ... WN E together with, for every prefix &.n (0 N), its membership L(x:n) and all continuation bits (p((z.. o))... We collect these
fL(x) = ((p(2 (1)())n))))) [1) I(xr.)) == E (1
We will use the term NSP labels to refer to such labels (See Fig. I left for an illustration). We in- stantiate predictors via automata. For a DFA define (a() = ((v(s,,,, o,)) [a( ) Let fA- denote the target NSP labeling function. The per-example loss is the 0/1 sup-norm mismatch err(fa (x), /A- (x)) : (z)) fA- (x:)))) i.c., it equals 1 iff any membership/- continuation label for any prefix is wrong; the NSP loss on D (supported on strings in L is LNSP (fa: fA- D) Ez-D [err(f(()), fA- (x))). Because all (EΣ) 1)((x) 1) labels must be simultaneously correct, NSP is stringent in the sense that a naive random guesser has near-zero chance of zero emoor typical example (contrast with 550 in binary classification).

---

Published as a conference paper at ICLR 2026
2.2 LEARNING THE TRUNCATED SUPPORT OF LANGUAGE MODELS
Let Σ VU {[EOS}} and let a language model LM define next-token probabilities PLM( y) on E for each prefix y E Σ". A sampling/tuncation rule T (c.g., top-p, top-k, per-step min-p) maps to the admissible next-symbol set (Tl)) S Σ. with [EOS] E CT (y) exactly when y may terminate (see Fig. [] right for an illustration). The T-truncated support of LM is the set of all strings that can be generated by running LM under T. Formally,
L.LM == f
UN : 0A S < N, Wo+1 E CT(w w..w,) and [EOS] E (1))
The NSP labelling oracle induced by the language model LM and truncation strategy is then,
(l = I[[EOS] E CT()),
x (v, = lla e CT(w) E)
and we set (x) ((v" (I:., (.). Li (z:n)) |.] n=o If generation under T terminates almost surely, then for any admissible step there exists a finite accepting continuation, so oT coincides with the global NSP semanties above.
From NSP learning to learning support. Let DLM be the distribution of strings generated by LM under T. Any PAC learner that, from NSP-labeled positive examples (x, (x)), outputs f with CNSP ff: DD) S immediately yields, by instantiating f fi.M and D = Di. procedure that learns the --truncated support of LM with NSP error at most c.
Oracle simulation. With black-box access to LM and rule T, one can simulate the typical example oracle EX(F D[M) by sampling x ~ DIM and returning (z, (x)). Membership queries can be computed by checking if string takes admissible path based the truncation strategy 'T and [EOS] is permissible at the last step.
3 IDENTIFIABILITY AND EQUIVALENCE IN THE NSP SETTING
Before studying efficient learnabllity, it is first necessary to establish whether NSP labels are nec- essary and sufficient, in an iooommtiion-thorreee sense, to identify a target language from positive examples alone. By unique identification from positive NSP data for a target DFA A with L # 0, we mean that there exists finite set S C LA such that
AA E DFAn,
Ya E S, [a(o)= [a-(
A= A
Any such S will be called (positive) NSP teaching set for A*.
Note that positive strings alone without additional labels are sufficient for such identifiability: over Σ = {0. 1}, let LA E" and LA- = 1 Every positive example x E 1 is accepted by both, so no positive counterexample exists. The same obstruction persists even if, in addition, the oracle reveals the membership of each prefix: for any x 1" and any prefix y of we have labels still cannot distinguish
(a(w)= = L (y) = 1, so positive examples with A from A The key property of the NSP labels is that the continuation bits convey information about strings not in the language: syy, or) = 0 certifies that no extension of yo is accepted. This additional information suffices to separate distinct minimal DFAS using positive examples only.
Proposition 3.1. Let A + A be minimal DFAs with LA + G. Then there exists LA such that fa( # (z). Equivalently, the oracle EQ(A; A*) is well-defined it either returns "equivalent" or a positive counterexample (x, J (x)).
The proof is in Appendix
Consequences. Proposition 3.1 has two immediate consequences. First, finite teaching sets exist: for each E DFA, \ {A* choose a witness FA E LA- with fA(AA) + fA-(IA) guaranteed by the proposition, and set S : {IA A E DFA, {A*)} C LA.. Then S is positive NSP teaching set for A in the sense of (I). Second, since it also implies that equivalence query oracle (cf. App. F is well-defined in the NSP setting, which is crucial for exact learning to be feasible.
4

---

Published as a conference paper at ICLR 2026
4 HARDNESS OF LEARNING
We study efficient PAC learnability in the NSP setting. An algorithm A an efficient PAC learner for a class F if for every f E F and every distribution D supported on positive examples, A runs in polynomial time NSP-labeled inputs and outputs î such that, with probability least 1 6. ENsp(f:f.o D) E.
Note that the continuation labels can be highly informative for certain classes. Consider Conjunc- tions: Boolean monomials f {0, + [0, e.g., f()) = z2 A Σ4. In the conventional clas- sification model, learning Conjunctions is known to require ((V) labeled examples. In the NSP model. one positive example
ff'(()1)))) suffices. For each prefix T:A. the label ((z- 0) equals if and only if the literal + appears in the target; likewise, ( 1) 0 if and only if the literal Ek+1 appears. Thus, by reading the continuation labels across the N prefixes, the learner recovers exactly which literals are present and hence identifies the target monomial from a single positive NSP example. While the NSP labels may provide a statistical advantage for some classes, we show that in the general case, they are not enough to remove the computational barriers for learning DFAs.
Main hardness result. Let ADFA N P(N) denote the class of Boolean Acyclic DFAs (ADFAs) which contains DFAs with at most p(N) states, whose language is contained in {0, 17.% Kearns & Valiant (1994) show that, for suitable polynomial p. weak PAC learning of ADFA,() in the conventional bmary-classification model as hard as inverting basic cryptographic primitives. We prove that an efficient NSP learner for ADFA P(N) would immediately yield an efficient learner in the standard model and thus the problem remains hard under the same cryptographic assumptions.
Theorem 4.1. Fix N and polynomial p(.). If ADFA M.Ny is efficiently PAC-learnable in the NSP setting from positive examples, then ADFA p(N) is efficiently PAC-learnable in the conventional classification (binary-label) setting.
The main technical idea is a construction for ADFAs along with reduction to the result of Kearns & Valiant (1994). We show that for any Boolean Acyelic DFA in ADFA P(N). there exists another ADFA with at most N + 1 additional states such that all but one continuation bit becomes uninformative. Accurately predicting the only informative continuation bit is as hard as learning ADFAs in the conventional classification setting.
The proof is in Appendix D
Discussion. The theorem shows that richer supervision via NSP does not circumvent the computa- tional barrier for learning regular languages: under standard assumptions, there is no polynomial- time weak learner for ADFApt) and hence for DFAs even in the NSP setting. This remains true when the learner receives both positive and negative examples with NSP labels, showing that such additional supervision does not mitigate these barriers. The hardness is improper: rules out ef- ficient learning even when the hypothesis need not be DFA, and thus applies neural models trained to match NSP labels.
Learning with Membership Queries. In addition to passive examples, also study active access in the NSP model. A conventional membership-quer
oracle MQ : Σ' + {0, 1} takes an input string and returns whether it belongs the target language. In the NSP setting, the oracle MQ (x) returns the full vector of (|Σ) + (1xr + 1) labels for any x E Σx We show that certain simple classes known to be not identifiable polynomial time with conventional queries become efficiently identifiable with MQusp with the help of additional labels. However, more generally, we show that some classes of DFAs and Boolean functions remain non-identifiable in polynomial time even with NSP labels from MQnsp- See App. for details.
5 LEARNING WITH A LANGUAGE MODEL TEACHER
Given the hardness of learning with random examples or membership queries alone, we now study the learnability of DFAs in relatively more powerful model based the information can conveniently obtain via blackbox access to language models.
Problem and Assumptions. Let LM be language model which induces distribution over strings DLM (correspondingly DIM for a sampling strategy T). Assume that the support of the distribution DLM is regular language and let A be the DFA that recognizes the support LAt. Given blackbox
5

---

Published as a conference paper at ICLR 2026
access to such language model, we would like to find À such that EE fa fa))-
e with high probability. In this setting, a learner has access to two types of queries: (i) Membership queries MQ(=) {0, 1} which returns (z)), and (ii) Generative queries GenDLa (-) which takes
an input string or prompt & and generates a string along with NSP labels based on the distribution
DLM conditioned on the prompt x. Note that both these queries can be simulated with blackbox access to the language model (cf. App. G.3).
Approach. Broadly, we first sample a set X of size m NSP labeled examples from the distribution DLM using Generative queries GenD (A). We will then use an extension of the L* algorithm to make use of the membership queries and generative queries to obtain hypothesis DFA Å in polynomial time such that |A| < |A*| and Á is consistent with the NSP labels of all m examples. A standard Occam-style generalization bound then yields a PAC-guarantes for the learning problem.
Preliminaries from L We briefly recall the notions from L* (Angluin 1987) based on modern treatments (Kearn&& & Vazirani 1994) that we use in Lamp (cf. App. G. for a more detailed de- scription). The algorithm maintains finite sets Q E* of access words and T C E* of test words, both containing the empty string X. Intuitively, Q represents states and T represents distinguishing strings. With respect to a target language A and any ordering &,, ; ETr T, we can define row vector of T-labels for any string x: row(x) = [LA- (x tq),. LA (a +pri]] E {0, 131T!. The pair (Q, is defined to be separable with respect to language LA- if every row vector is unique: row(g) F row()') for q.9' E Q. The pair (Q.T) is closed if for every E Q and o E E, there exists o' E Q such that row(g o) = row(g'). When (Q, is closed and separable, one can con- struct DFA hypothesis with state set Q and transitions based on T-labels (see App. G.1 for the construction). A crucial fact about this L* framework is that (Lemma G.I) when (Q, T) is closed and separable with respect to language LA-, then [Q] < |A* for the minimal DFA A*.
Given a set of labeled examples, L* starts from Q = T = {A} and iteratively adds states and distinguishing strings based on label disagreements, maintaining key invariant that (Q, T) remains separable. The procedure has two steps: (i) Closure (Lemma G.2): if T) is not closed, use membership queries to update (Q,T) to achieve closure in polynomial time. (ii) Counterexample processing (Lemma G.3:: once closed, construct hypothesis DFA Å and find a counterexample r in the training set with A(x) + (x). Then, using at most [x| membership queries, one can identify o' & Q and l' & ' so that ('') TU(()) is separable. This step is the backbone of Lt: membership disagreements can be used to obtain new access and test words to refine (Q,T).
In the NSP setting, counterexamples may arise from continuation-lahed rather than membership disagreements, so Lemma G.3 does not apply as is. This is where Liup departs from Lt: we use a different method to process counterexamples x E LA- using continuation-label disagreements. The next lemma formalizes this update rule for Lissp.
Lemma 5.1. Let () be closed and separable, and let À be the minimal DFA induced by (Q, T). fA)( Then one can find g' & Q and t' & T such that (QU(d)) TU(t') is separable, using membership queries and at most one generative query in polynomial time. If a generative query is used, let denote its output; otherwise set = X. The total number of membership queries is at most |x] + [y), and the running time is polynomial in |z]| + 1vl IQ).
Suppose there exists string with (x) #
The proof for this Lemma is relatively straightforward. The idea is to convert any NSP-label mismatch into an ordinary membership mismatch, and then use the same approach as the classical Lt update (Lemma G.3 Take x with (a) + fA- and let 2.,. be the first prefix where labels disagree. If the mismatch is the membership label, we simply use x' I.n, on which Á and A disagree so the first case trivial. If the mismatch is a continuation label at some symbol a, then there are two complementary situations. Case (i) The target says can never lead to acceptance from T.n. but the hypothesis says it can ( o) = 1. In this case, we can find a suffix s from T to accepting state in the hypothesis automaton and the strings x' Zin is an ordinary membership mismatch. Case (ii) The target says a is permissible, but is forbidden according to the hypothesis yo *A(I.., (I..,, o) = 0. In this case, we can use single generative query conditioned on Z.no returns a valid continuation y, then x' = I.n is accepted by the target and rejected by Å. Thus, in both cases, we have a string x' such that A(x') + Aa')') and we can use Lemma G.3 to find desired of & Q and L & T. A more detailed version of the proof is in App. G.2
Proof.

---

Published as a conference paper at ICLR 2026
Bounded Dyck Family: Key metrics vs Sample
accuracy
100
Dyck-66,33
Target states
NSP accuracy (86)
80
Dyck
300
Dyck((2.2)
Dyck-12.4)
states
Dyck-14,3)
200
40
Dyck-13,3)
Dyck-12,4)
100
20-
20
12ck-12,2)
10
10a
10"
10
107
10
10"
10
10a
10:
10'
10
Sample size
Sample size
Sample size
Parity, Tomita Key metrics Sample
States
1.00
rget
MSP accuracy 196)
Temita 5
30
Tomita-7
Time (c)
spatres
1amita- 5
Tom
10"
10'
10
10'
10
10'
10'
10
10'
Sample size
Sa mplll size
Sample size
Figure 2: Key metrics for Lisp across training-set sizes using Transforrmrr-LM teacher. Each point shows the mean over 10 trials; shaded regions denote standard deviation (see Sec. 6).
Algorithm. Given a set of m NSP-labeled example, the Lisp algorithm works as follows. It starts with T = (Λ} and iteratively updates the pair (Q, 7') such that they are always separable. For hypothesis Á associated with (Q, T), it finds the first disagreement in the NSP labels with the examples in the training set X. Using membership queries and generative queries based on Lemma 5.1 it updates the pair (Q,T) T)) and adds at least one state whenever there is disagreement with the training examples. The closure step remains the same as in the original L algorithm. The algorithm terminates when Á induced by (Q,T) is consistent with all the training examples. Since [Q] is guaranteed to be at most |A*), the algorithm must terminate after most |AA| disagreements with the training examples. pseudocode of the 1sp is given in Algorithm
Let A E DFA, be any minimal DFA with at most n states, and let DLM be a distribution over strings whose support LA There exists an algorithm with access to the mem- bership query oracle MQ and generative query oracle GenDI producing NSP labeled examples in Las, that runs in time polynomial in n, 1/e,1/e and the length of the largest string produced by the generative query oracle, and with probability least 6, outputs a DFA Å such that,
Theorem 5.2.
E DO-DLM
- (A
Discussion. A key benefit of this model of learning is that the guarantee we get is with respect to a desired distribution. For example, one uses the L algorithm to learn DFAs using positive and negative examples, the target distribution (on negative examples) is often unclear and can be artificial. In practice, for generative models, we often do not have access to the target distribution on negative examples. For the purpose of identifying the support of language models, arguably the most relevant distribution is the one induced by the model itself, e.g. if one intends to predict whether the language model will generate erroneous strings.
EMPIRICAL ANALYSIS
We evaluate the Lisp algorithm as a tool for extracting DFAS from Transformer language models trained on regular languages. Given NSP-labeled strings from the model, we study how the NSP error LNSP, the number of identified states, and the running time vary with the size of the training set. When the extracted automaton is not equivalent to the target DFA, also find strings in the symmetric difference to identify erroneous examples. Further, we conduct ablations to analyze the effectiveness and usage of the continuation labels in the NSP setting.
7

---

Published as a conference paper at ICLR 2026
Tasks, We consider 11 regular languages spanning 2-86 states: the 6 Tomita grammars Tomita
1982), Parity, and 4 bounded Dyck languages. Tomita grammars comprise small DFAs (2 states)
and is commonly used as benchmark for automata extraction (Wang et al. 2018 Weiss et al. 2018
Zhang et al. 2024). Parity is the two-state language over Σ = {0, 1 which contains all strings with an odd number of 1s. Bounded Dyck languages contain well-balanced parentheses up to fixed depth and are regular. We denote by DYCK-(n, k) the Dyck language with n bracket types and depth at most k. The depth of a Dyck string is the maximum number of unclosed brackets in any prefix of the string. These languages have relatively larger number of states: E n² + 1. We use four Dyck instances: DYCK-(2, 2), DYCK-(2, 4), DYCK-(33 3), and DYCK- (4, 3). Further details of the tasks are in App.
Setup. For each target language we convert its canonical DFA to PDFA to generate training strings. At non-final states, probability mass is split uniformly among transitions that avoid the dead state; at final states, generation terminates with probability (otherwise, the next symbol is sampled as above). For each language, we choose / so that the empirical expected length is below 40.
Model training. We train Transformers as next-token predictors on sequences of the form [BOS] 81 [EOS] $2 [EOS] ... with context window 250. Models use 8 layers and width 512, opti- mized with AdamW for up 40k steps with early stopping. Our evaluation focuses on the support of the first string produced after [BOS]; the concatenated format matches standard training and provides additional learning signal.
DFA extraction. We use the trained Transformers to generate training sets of various sizes to evaluate the Lisp algorithm. We create training sets with strings of length up to 80 that are generated and labeled using min-p sampling with threshold p = 0.05 as described in Sec.2.2 The Transformer model serves as both membership and generative query oracle for hsp-- We evaluate sample sizes (1,5, 10, 100, 1000}; for each size we run 10 independent trials and report means and standard deviations. For very small targets (e.g., Tomita), even a single positive example can be informative.
Results. Figure 2 summarizes NSP accuracy, running time, and the number of extracted states for representative tasks. On Tomita, when teacher models are well trained, hss recovers the target DFA quickly (often within a second; bottom row). For models that are not perfectly trained, such as for Parity, the algorithm extracts a much larger DFA and takes longer, depending the number of target states. Note that since Lisp adds a state only after finding a distinguishing string, the number of extracted states is always most the number of states in the target DFA that recognizes the language model's support. Thus, even when we recover more states than the target DFA, the result is faithful to the language teacher's 'ss support.
Bounded Dyck languages have relatively much larger number of states (8-86 states). As shown in the top row of Figure 2 Dyck tasks naturally require more samples than Tomita, yet Tsp converges to the target DFA and achieves near-perfect NSP accuracy within 100 examples. Our ablation experiments in App. H.djiidiccte that the continuation labels are heavily used and play crucial role in identifying the states of the target (see Table 3)
Identifying erroneous examples. When the learned DFA Á is not equivalent to the target DFA A", we construct the product DFA B which recognizes the strings in the symmetric difference of the two languages L(B)= = L(Á)
We use BFS- like approach identify several erroneous examples for the language model. Table 2 Illustrates some erroneous examples for Bounded Dycks, Parity, and 5 language. Fig. 6 and 7 depicc the extracted automaton for Parity and Tomita- 5; the ones for DycK-(2,2) 2) and DYCK- (3,3) 3) are too large to be visually informative. Note that these models were not intentionally trained to fail, and all the examples generated by the language models were in their respective target languages. The DFAs extracted by Lisp were based on a few disagreements in the NSP labels of the generated strings. Training the language models for longer avoids such errors for synthetic languages of this scale. Note that the Transformer models used for Tomita-5 and Dyck languages in Figure 2 (well-trained) and Table 2 (imperfect) are different. See App. for further details.
NSP Label vs Binary Label Ablations. To assess the value of NSP labels, we compare binary labels (classical L*) with NSP labels (Liup extension) on six languages. We sample strings from the model's 's untruncated distribution (actual next-token probabilities) and label each as positive if it lies in the min-p truncated support DTM used elsewhere, negative otherwise. Naturally, most (=: 99.5%)
8

---

Published as a conference paper at ICLR 2026
(2c) L-star va L-star-N5P
12,k-12,4); L-star va Listar-NP
(433-14433) Later L-star-
L-P
L-beN55
L-tter
1-ttr
1-tte
Target Caras
Berge care
Trrget Care
127
12"
30
202
221
20
20
202
307
Sample dize
Sample dan
Sample dan
Parity:: Lester us Lettar-NS
Tomita-2: Letter vn L-tar-NSP
Tomita S: Letter L-star-NSP
30
20:
15:
Sample
Sample
Sample
Figure 3: Comparison between binary labels (L*) and NSP labels (Lisg) by including negative examples by sampling from the untruncated distribution of the LM. Each point in the plots is the mean value over 10 trials; shaded regions show standard deviation. See Sec. offor details.
of the samples are positive; nevertheless, even positive strings serve as counterexamples for L* and using any natural variant of the DLM variant will have few negative examples.
Results. Figure plots the number of extracted states versus sample size (means over 10 runs). On bounded Dyck languages, Lisp reaches the target DFA with = 10 examples for DYCK- and ~ 100 for DYCK-(2, 4) and DYCK-(4, 3). whereas L* fails recover the target even with 10 samples. For small Tomita DFAs, single counterexample suffices, so both approaches perform similarly. For Parity, although the target DFA has 2 states, the teacher's support DFA is larger, with NSP labels, Lisp identifies this larger support (enabling the discovery of erroneous strings), while binary labels yield no disagreements and thus additional states. Because almost all samples are positive, classification accuracy is uninformative; predicting leads to near perfect accuracy and thus the extracted state count is the meaningful signal. Note that the claim here isn't tt that T. L. is superior (it is direct extension of L* itself). The primary goal is to assess whether the additional labels are informative and the results indicate that leveraging NSP labels can be sample efficient for problems where the natural distribution primarily has positive examples.
FUTURE WORK AND LIMITATIONS
A natural question that remains open is the efficient learnability of DFAs with membership (MQ) and equivalence queries (BQ) in the NSP setting. We show that with membership queries and types of cquivalence queries, DFAS are exactly learnable and discuss barriers behind obtaining a standard MQ+EQ algorithm in App. G.4 Prop. 3. shows that NSP labels are sufficient and a teaching (or characteristic) set exists. However, the size of such a set obtained from Prop. 3.1 is likely to be quite loose and could possibly be improved.
Limitations. Even though the Lisp algorithm is polynomial-timg time, since it is built upon the L* framework, some of the same limitations apply, which make it difficult to scale the approach to practical language models. In particular, when the target DFA (language model support) has large number of states, the algorithm is quite slow. We observe that when models are poorly trained, the underlying DFA typically has thousands of states. The Lisp algorithm identifies about 1k states and the closure step is slow due to the [Q[[T||S| time complexity (discussed in more detail in App. H.3 Further, the factor of [ may not play a significant role for synthetic languages but has immediate consequences for language models trained on text which have a large vocabulary. An interesting future work would be to develop more efficient system-leve level improvements to speed up the algorithm to make it applicable relatively more practical language models.

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENTS
We would like to thank Dana Angluin, Alex Clark, Charles London, and anonymous reviewers for their valuable feedback and constructive suggestions this work.
REFERENCES
Dana Angluin. On the complexity of minimum inference of regular sets. Information and control, 39(3):337-350, 1978.
Dana Angluin. Learning regular sets from queries and counterexamples. Information and computa- tion, 75(2):87-106, 1987.
Dana Angluin. Queries and concept learning. Machine learning, 2(4):319-3422 1988.
Leonor Boneche, Adrian Horia Dediu, and Cristina Türnāucā. Learning dfa from correction and equivalence queries. In International Colloquium on Grammatical Inference, pp. 281-292. Springer, 2006.
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the Ability and Limitations of Trans- formers to Recognize Formal Languages. In Proceedings of the 2020 Conference Empir- ical Methods Natural Language Processing (EMNLP). pp. 7096-71 16, Online, November 2020a. Association for Computational Linguistics. doi: 10.18653/w1/20000
2000:///020000mmmmmmmmm577777771 URL
https://aclanthcclogy wwtp:/hhoooo....///2e2eo2/// ottp htt.://oww....//222..mmmmmmaaaaa emnlp-main 576
Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the practical ability of recurrent neural networks recognize hierarchical languages. In Proceedings of the 28th International Confer- ence on Computational Linguistics, pp. 1481-1494, Barcelona, Spain (Online), December 2020b. International Committee Computational Linguistics. doi: 10. 10.116633/1/2002.cooii org/ wtgg//20000000..00ooo000/ooo///0
129.
URL httt::::/aacaaathooe
mainn 129
Alexander Clark and Franck Thollard. Pac-lcarnability of probabilistic deterministic finite state automata. Journal of Machine Learning Research, 5(May):473 497, 2004.
Thomas Colcombet, Daniela Petrişan, and Riccardo Stabile. Learning Automata and Trans- ducers: A Categorical Approach. In Christel Baier and Jean Goubault-Larrecq (eds.). 29th EACSL Annual Conference on Computer Science Logic (CSL 2021), volume 183 of Leibniz International Proceedings in Informatics (LIPles), pp. 15:1-15:17, Dagstuhl, Germany, 2021. Schloss Dagstuhl- weiinii-Zentruu für Informatik. ISBN 978-3-959777-75577 doi: 10.4230/ URL httts:://drop:: wtw.ddrossssssstuu...dddddd..e www.t de http:/aatttaaaaaaeaaaaaaaaeeeeea
CIPlcs.CSL.2002
10. 11.44230/IPPIC CSL.
Colin De la Higuera. Grammatical inference: learning automata and grammars. Cambridge Uni- versity Press, 2010.
Javid Ebrahimi, Dhruv Gelda, and Wei Zhang. How can self-attention networks recognize dyck-n languages? arXiv preprint arXiv:2010.04303. 2020.
Rémi Eyraud and Stéphane Ayache. Distillation of weighted automata from recurrent neural net- works using a spectral approach. Machine Learning, 113(5):3233-3266, 2024.
Felix A Gers and E Schmidhuber. Lstm recurrent networks learn simple context- free and context- sensitive languages. IEEE Transactions on Neural Networks, 126))1333)13400 2001.
C. Lee Giles, Clifford B Miller, Dong Chen, Hsing Hen Chen, Guo-Zheng Sun, and Yee-Chun Lee. Learning and extracting finite state automata with second-order recurrent neural networks. Neural Computation, 4(3):393-405, 1992.
E Mark Gold. Complexity of automaton identification from given data. Information and control, 37 (3):302-320, 1978.
Michael Hahn. Theoretical limitations of self-attention neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020.
10

---

Published as a conference paper at ICLR 2026
Michael Hahn and Mark Rofin. Why sensitive functions hard for transformers? arXiv preprint arXiv:2402.09963 2024.
John Hewitt, Michael Hahn, Surya Ganguli, Percy Liang, and Christopher D Manning. Rnns can generate bounded hierarchical languages with optimal memory. arXiv preprint arXiv:2010.07515, 2020.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. arXiv preprint
2019.
Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM), 41(1):67-95, 1994.
Michael Kearns and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994.
Loes Kruger, Bharat Garhewal, and Frits Vaandrager. Lower bounds for active automata learning. In François Coste, Faissal Ouardi, and Guillaume Rabusseau (eds.), Proceedings of 16th edition of the International Conference on Grammatical Inference, volume 217 of Proceedings of Machine Learning Research, pp. 157-180. PMLR, 10-13 Jul 2023. URL https: http:s////pcccedings..
mlr wwr.prer.sseee wtt.pppsss/////.useeeeeee
html
Franz Mayr. Sergio Yovine, Matías Carrasco, Federico Pan, and Federico Vilensky. congruence- based approach active automata learning from neural language models. In François Coste, Faissal Ouardi, and Guillaume Rabusseau (eds.), Proceedings of 16th edition of the International Conference on Grammatical Inference, volume 217 of Proceedings of Machine Learning Re- search, pp. 250-264. PMLR, 10-13 Jul 2023. httpht/sss/ppcccddggg..... .mw.rediiinnsm......mmm press/ v217 2217/mayr23a.22
Nguyen Nhat Minh, Andrew Baker, Clement Neo, Allen G Roush, Andreas Kirsch, and Ravid Shwartz-Ziv. Turning up the heat: Min-p sampling for creative and coherent LLM outputs. In The Thirteenth International Conference on Learning Representations, 2025. URL https:
//openzeview.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Edi Muškardin, Bernhard K Aichernig. Ingo Pill, and Martin Tappler. Learning finite state models from recurrent neural networks. International Conference on Integrated Formal Methods, pp. 229-248. Springer, 2022.
Christian W Omlin and Lee Giles. Extraction of rules from discrete-time recurrent neural net- works. Neural networks, 91):41--5, 1996.
Artidoro Pagnoni, Ramakanth Pasunuru, Pedro Rodriguez, John Nguyen, Benjamin Muller, Mar- garet Li, Chunting Zhou, Lili Yu, Jason Weston, Luke Zettlemoyer, et al. Byte latent trans- former: Patches scale better than tokens. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 9238-9258 9258, 2025.
Nick Palmer and Paul W Goldberg. Pac-learabilitty of probabilistic deterministic finite state au- tomata terms of variation distance. Theoretical Computer Science, 387(():18-3) 2007.
Leonard Pitt and Manfred K Warmuth. The minimum consistent dfa problem cannot be approxi- mated within any polynomial. Journal the ACM (JACM), 40(1):95-142, 1993.
Mirac Suzgun, Yonatan Belinkov, Stuart Shieber, and Sebastian Gehrmann. LSTM networks can perform dynamic counting. In Proceedings of the Workshop on Deep Learning and Formal Lan- guages: Building Bridges, pp. 44-54, Florence, August 2019. Association for Computational Lin- guistics. doi: 00.16653/1/119939900 URL https://///...........t www. c www. orw.antholl/to/oooooooooo o
W1 W19-3905]
Masaru Tomita. Learning of construction finite automata from examples using hill-climbing. IT: Regular recognizer. Technical report, 1982.
11

---

Published as a conference paper at ICLR 2026
Frits Vaandrager, Bharat Garhewal, Jurriaan Rot, and Thorsten Wißmann. A new approach for active automata learning based on apartness. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 223-243. Springer, 2022.
Qinglong Wang, Kaixuan Zhang, Alexander G Ororbia II, Xinyu Xing, Xue Liu, and C Lee Giles. A comparative study of rule extraction for recurrent neural networks. arXiv preprint arX1vv1801.05420, 2018.
Zeming Wei, Xiyue Zhang, Yihao Zhang, and Meng Sun. Weighted automata extraction and expla- nation of recurrent neural networks for natural language tasks. Journal of Logical and Algebraic Methods in Programming, 136:100907, 2024.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Extracting automata from recurrent neural networks using queries and counterexamples. In International Conference Machine Learning, pp. 5247- 5256. PMLR, 2018.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Learning deterministic weighted automata with queries and counterexamples. Advances Neural Information Processing Systems, 32, 2019.
Yihao Zhang, Zeming Wei, and Meng Sun, Automata extraction from transformers. arXiv preprint 0455542406.05564, 2024.
12

---

Contents
1
Introduction
1.1
Related Work
2
Problem Definition
2.1
Next Symbol Prediction (NSP) Setting
2.2
Learning the Truncated Support of Language Models
3
Identifiability and Equivalence in the NSP setting
Hardness of Learning
Learning with a Language Model Teacher
Empirical Analysis
Future Work and L Limitations
Usage of Large Language Models
13
FAQs
13
Preliminaries
14
D Hardness of NSP Learning
15
D.I Boolean Acyclic DFAs
15
D.2 Boolean formulas
18
Hardness of Learning with Membership Queries Only
18
Equivalence Queries and Identifiability
19
Learning with Membership and Generative Queries
20
G.1
--ttar Preliminaries]
21
G.2
Processing Counterexamples in the NSP setting
22
G.3
Simulating Membership and Generative Queries
23
G.4
On Exact Learning with Membership and Equivalence Queries
23
Further Experiments and Details
25
H.1
Additional Details of the Setup
25
H.2
Identifying Erroneous Examples
26
H.3
Practical Notes on the algorithm
28
H.4
Ablation: Usage of Continuation Labels
28
I
Experiments with LLMs
30
Setup
30
Results
A USAGE OF LARGE LANGUAGE MODELS
We used publicly available AI tools (LLMs) to improve the flow and clarity the text various places. LLMs were used to rephrase certain text to polish it and/or make it more concise, Al tools have also aided in writing the code for the experiments in the paper.
B FAQS
(1) If Lisp is an efficient polynomial time algorithm, why shouldn' we directly apply it to large language models (LLMs) to obtain DFA that captures their support?
13

---

Published as a conference paper at ICLR 2026
There are few nontrivial obstacles in applying the algorithm to LLMs. Firstly, the target language for an LLM could have a huge number of states, and currently, it is difficult to use the algorithm for targets beyond the order of a few thousand states. Secondly, while the complexity of the algorithm is polynomial, it still scales linearly with the size of the vocabulary, and LLMs have vocabularies that are in the order of tens of thousands. Lastly, the support of LLMs may not be regular, which could violate the main assumption, and the guarantees need not apply. We believe this work makes progress towards the larger goal of capturing the support of language models, but is practically limited, similar to other existing methods for automata extraction.
(2) To identify erroneous examples, can we not sample from language model several times and then check if any of them are incorrect?
In theory, one can sample repeatedly to identify erroneous strings in the support. We argue that better algorithms for this problem can make the identification of erroneous strings much more efficient. For instance, for the parity language, sampling Ik strings from a seemingly well-trained model does not seem to produce any erroneous examples. However, the DFA extracted by leveraging NSP labels provides us with numerous erroneous examples. We found that Lisp could extract DFA within 10 seconds using 1k generations from the language model, which could then be used to produce about Ik erroneous strings within 16 seconds (see App HH. for details). While the current approach isn't t scalable beyond such synthetic problems, further improvements could help make progress in more efficient identification of DFAs and, consequently, identification of erroneous examples.
(3) On what kind of problems is it more beneficial use s as opposed to directly using L*?
Lasp is a direct extension of L* that exploits NSP labels when available. It can be more sample- efficient in positive-only or highly imbalanced settings typical of generative models. Empirically, bounded Dyck languages, Lis recovered the target DFA with 110-100 examples, whereas without NSP labels, L. did not with 10 samples (Fig. 3); ablations also show the algorithm heavily uses continuation labels on Dyck tasks (see Table and Sec. H.4))
(4) Does the hardness result imply that learning with random examples alone will likely fail?
One should take note that the hardness results are generally for the worst-case setting. It is helpful to gain a formal understanding of the strengths and weaknesses of a problem but they do not imme- diately imply that learning will fail most of the times. The result indicates that efficient distribution- independent PAC-learning algorithms are not feasible under standard cryptographic assumptions. However, in practice, using scalable heuristic-based methods is often effective. Our goal was to characterize the learnability in the NSP setting to understand the power of the additional supervi- sion available in the NSP setting and it implies that they are not powerful enough to mitigate certain computational barriers.
C PRELIMINARIES
We define Probabilistic DFAs (PDFAs) formally here. Our result on learning with membership and generative queries (Theorem 5.2 has direct implications on learning the support of PDFAs. We also use PDFAs to generate strings for training Transformer language models.
Probabilistic DFAS (PDFAs). probabilistic DEA is DFA equipped with stochastic emission rule. Formally, a PDFA is a tuple
P= (Q, go, F,T),
where E, go. F) is a DFA and, for each & E Q, T(- | g) is a probability distribution on E U { [E At state q, the generator samples w E u [[OOS] according to 5(- q): if w E Σ the next state is ō(g, w). and if w [EOS] the sequence terminates. We say a string W1 w.... wN E E" the support of Pif
<(w1 qo) (w22 6(9o. w1)) TwNN 8(90, x.N- [ECS] 8(go, x)) > 0.
The DFA that accepts exactly this support is the support DFA of P.
NSP labels from PDFAs. In PDFA P, the NSP labels coincide with positivity of the local emis- sion probabilities:
()), = T(r((a 6(go. v)) 0),
T(y) T( [[FOS] 56(go y)) > 0).
14

---

Published as a conference paper at ICLR 2026
Thus, the NSP labelling oracle exposes exactly the admissible next symbols and termination each prefix; for a PDFA this recovers the (untruncated) support of P.
The following is an elementary but fundamental fact about minimal DFAs due to the Myhill-Nerode Theorem that is at the heart of many of our proofs and constructions.
Lemma C.1 (DFA basic fact). Let A be minimal DFA recognizing LA. For any two distinct strings z, E E", if there exists a suffix s E " such that LA(Z s) & LA(y s) then the strings a and y lead to two distinct states in the DFA A, L.e,, ( # dx(go. v). If no such suffix exists, then they lead to the same state A x) = 54(40.3) y)-
In a minimal DFA, distinct states are pairwise distinguishable by some continuation; conversely, strings with indistinguishable residual languages must reach the same state. This is the My- Nill-Nerode characterization of minimality.
Lemma C.2. Let the dead state qdead be a state such that qdead & F and ó öggdead σ) = 9dead for all E. Then, minimal DFA has at most one dead state.
Assume there are two dead states. Since every suffix from dead state is rejected, there cannot be a suffix that is accepted by one state and rejected by another. Further, by definition, both of them non-final. Hence, they are Myhill-Nerode equivalent and must be merged in a minimal DFA.
Lemma C.3. Let DFA, be the class of DFAs over fixed alphabet E with most states. Then log [DFA,/ = On l)..).
This is well-known result (De la Higuera 2010 and can be proved in the following way. The proof follows from the fact that for a DFA with at most states, there are n [ and each state can either be an accept or reject state adds factor of 2", and one of the states can be an initial state. Hence, the total number of possible DFAs is 2" n/ 1= Thus, log |DFAn = On n).
D HARDNESS OF NSP LEARNING
We relate learnability in the NSP setting to standard PAC learning for acyclic DFAs that accept only strings of a fixed length. Throughout this section, we work over the binary alphabet Σ = {0. 1}.
Notation for classes. For N E N and polynomial p(-), define
ADFA N P(N) { [A: A is DFA with most p(N) states and T. (0,1)
and write ADFA (() = UN UN ADFA p(Ny. As in the context, DFA,, denotes all DFAs with at most
n states.
Background. Kearns & Valiant 1994) show that, for a suitable polynomial p, weak PAC learning of ADFAp(.) p(-) in the conventional classification (binary-label) model is as hard as inverting certain cryptographic functions.
Theorem D.1 (Kearns & Valiant 1994)). There exists a polynomial p(-) such that the problems of inverting RSA, factoring Blum integers, elc., are probabilistic polynomial-time reducible weakly learning ADFAp(.) in the standard PAC setting.
We prove that efficient PAC algorithm for ADFA ((N) in the NSP setting would yield effi- cient PAC algorithm for ADFA P(N) in the conventional classification setting. Together with Theo- rem D.I this implies cryptographic hardness for NSP learning of these Boolean Acyelic DFAs and consequently the general class of DFAs.
D.1 BOOLEAN ACYCLIC DFAS
Fix N 2 1 and a target DFA A = (Q, 0, go. F) with LA S 10,1 We first record a basic structural property of minimal DFAs for fixed-length languages.
Lemma D.2 (Unique depth in minimal ADFA If A is minimal and LA C {0, 1N then every state Q {9dead} is reachable by strings of exactly one length l(g) E (0.1..... N). Consequently, every transition increases depth by one: if 6 o) = d' and q # Gdeads then Elg') =
((g) + 1. Acceptance occurs only at depth N.
15

---

Published as a conference paper at ICLR 2026
al
0,1
F2
R3
Q1
(a) DFA for 21 233, a E 10.
(b) Transformed DFA (z) A z3) V 2s. x E {0, 1]
Figure 4: Transformation from Section D.1 In (b), green states from the original DFA; blue
states ......y 4a ensure every prefix of length < N has NSP labels [1. 1,,, and gi routes to accept on input (to the dead state 0).
Proof. Let 9 E Q {gdead) be reachable both by a string of length l and by a string of length e' with & f'. The residual language q is R(q) {s Σ" 5(g, s) F. If is reached after e symbols, then every E R(g) must have length exactly N if if is reached after symbols, then every R(q) must have length exactly N
are disjoint; hence R(g) must be empty, contradicting * Qdead in minimal DFA. Thus, each non-dead state has unique depth (g)) Any transition consumes one symbol, {(q') E(q) + 1; equality must hold by uniqueness of depth. Finally, if E F had E(g) * N, then LA would contain strings of length other than N, contrary to the assumption.
Since N - j N f', these
By Lemma D.2, may index non-dead states by their unique depth {(g) (O....,, NN (the dead state has no depth).
Padding by bit. We construct from A DFA A over length- --1 inputs whose NSP labels are uninformative before depth N, while at depth the continuation bit for symbol recovers A's label.
+1
Lemma D.3 (Padded Construction). From a Boolean Acyclic DFA A we can construct, in time polynomial in |A| + N, DFA A with A C [0, 11 and
u. E LAw
(A(u) 1) (b (b= 1), u (0,011 be (0.1}.
(2)
Moreover, for every prefix with lul < N,
(p(y, 0), ply, 1), LA (ao (1,1,0),
for every (0,1)%
(ę(u, 0), p(u, 1), (uo(u)) = (A(u), 1, 0).
The construction adds at most - states.
Proof. Introduce new states ......,
.......,e dy and a new accepting state Oin- For S < N set
0o (g/, 0) 4441
8 (g's 1) d
and at N set
0 (g'v. 1) 9in:
A (d'x, 0) = Idead.
From AEn send both symbols Idend (so acceptance occurs only at length N+1).
Now modify A to create A as follows. For each non-dead state q with E(g) < N and each (0, 1}:
If dA(g, = Idead in A, set )λ=(g,o) = l6g41 (redirect the dead transition into the chain).
Otherwise set λa (g. o)(
For each state g at depth N set
م (g,0) 0) = Pan. E FA.
A (g. 1) = piins
Idead,
E FA.
16

---

Published as a conference paper at ICLR 2026
See Figure simple example construction for Boolean Acyelic DFA computing conjunction.
All transitions out of Qdead point to gdead. i.c., 6 (Adead: 0) = qdead for both symbols. (If A recognizes the empty language. then Q {4dead]; h: in this case we additionally introduce fresh start state do of depth with 5 (Āo, 0) = A (9o. 1) = of and take do as the start state; the conclusions below still hold.)
By construction, acceptance can oceur only at qin after exactly N+1 symbols, so L S {0, 1) The rule at depth N gives (2) For any prefix y with lyl < N, either origi- nal transition still has an accepting continuation, or a dead transition is redirected to the chain d' > qin (taking the last symbol 1). Hence spy, 0) s 1) and
7 L (v) = 0 for any with lvl < N. At depth N, for every E {0, 1) our construction en- forces
= 9inz
óΛ(q0: u) E FA,
8 o ( u), 1) = Qtin and 8ΛY( 1r (40, u).
Idead:
6a(g0: u) $ FA.
80 ((,, 1) = 1, s(u, 0) A(u), and a (u) O, which exactly (v(u, 0), p(u, 1), La=(u)) = (A(u), 1, 0).
Reduction from standard learning to NSP learning. Let D be any distribution on {0, 13... Define the padded distribution Do on {0, 1) N+1 by sampling
D and returning xr 1. By (
E L for every u, so D is supported on positive examples as required by the NSP setting. Moreover, given a labeled standard example (u. y) with y = A(u), the full NSP label vector f (z)
for x = u 1 is computable from yu,
for 0 < (p(2,, 0), (1. 1), L(x.))) = (1,1,0),
for l = N: (F(E,,, p(ENN, 1), ((EN)) (v. 1)0, for l = N+1: (p(a:N+1, 0), (0 (x.N++1) (0,
Here I.s denotes the length-E prefix of the padded string x. Theorem 4.1. Fix N and polynomial p(-). If ADDFA is efficiently PAC-learnable in the NSP
setting from positive examples, then ADFA N classification (binary-label) setting.
P(N) is efficiently PAC-learnable in the conventional
Proof. Let ANsT be an efficient NSP learner for ADFA N M(N)- From i.i.d. labeled samples (u(), ()) with ( A(u(O), form positive NSP examples (zo(9) S^ (z)) where x(()) ( 1 using the rule above, and feed them to ANSP. Let f be the returned predictor so that, with probability at least 1 5,
LNSP (f: fAo, D E [[]((u- fAo 1)1co] S e.
u>D
Define standard classifier h {0, 13.h + {0, 10 by
h(w)= = the bit predicted by f for p< 0) u-
Whenever [[f(x) SAe (2)]l = 0, Lemma D.3 gives h(u) A(u). Therefore
Pr h(uu) # A(u) < Pr k>D
[l 1) fae (u- 1) =1] s
w
yielding efficient PAC learner in the standard setting. The state complexity of A is at most P(N) + N + 1, preserving polynomial time complexity.
Corollary D.3.1 (Cryptographic hardness for NSP learning of fixed-length acyclic DFAs). Under the assumptions of Theorem D.1 there is no polynomial-time weak learner for ADFA,t) in the NSP setting. Otherwise, Theorem 4.1 would yield a polynomial-tin time weak learner in the standard setting, contradicting Theorem D.1
17

---

Published as a conference paper at ICLR 2026
D.2 BOOLEAN FORMULAS
Exactly the same padding idea applies to Boolean formulas. Let F be any class of formulas f (0. 13 - {0,1] 1} and define
((411)..,2411) = f(21..... 2L) V 2N+1-
Given a labeled standard example (u,y) y) with y [(u), set == u. 1. The NSP labels for the positive string x under I' are then computable from (u, y):
for l <<N> N (1,
for N: (,, for N+1 (0,0,
with the same ordering (continuations first, then membership) in $2 Thus efficient NSP learner for F := { E F) yields, by reading the depth-N continuation bit for symbol 0, an efficient PAC learner for F in the standard setting. In particular, cryptographic hardness results for learning formulas (e.g., via NC²) carry to the NSP setting by this reduction.
E HARDNESS OF LEARNING WITH MEMBERSHIP QUERIES ONLY
Definition. A conventional membership query oracle MQ E' + f0. 1] takes input string and returns whether it belongs to the target language or not. In the NSP setting, the membership query oracle MQusp E - {0, 1 (10)+)))()+++ returns all the NSP labels for an input string x. Since it contains that membership label of the input in its label, it is strictly more powerful than the conventional MQ oracle.
To understand how additional labels could provide more information, consider the following. If for any pair of prefixes or strings æ, the |Σ| continuation labels (((z))p())))))))) differ, then it implies that they lead two distinct states in the target DFA. This is because disagreement in the continuation label implies that there exists suffix 8 such that L(x 8) # L(y 8) and by Lemma C.1 they must lead to two different states.
There are some classes of functions that can be efficiently identified by MQnsp but not by conven- tional MQ. For instance, consider the class of singleton Boolean functions Fi over {0, 1 which contains 2-V functions that accept exactly 'one' Boolean input of length N. Such functions cannot be identified by conventional membership queries in polynomial time (see Aeeeung (1888) for gen- eral characterization). The main idea that no matter which input in 13 a learner queries, an adversary can decide to always return O as the label until the learner queries 2 inputs.
Learning Singletons with MQusp- The membership query oracle in the NSP setting more pow- erful in the sense that such singleton Boolean functions can be identified easily in polynomial time. To see how, consider the following procedure: Let xx E (0. N be the only string accepted by the target f" {0. 1 + {0, A learner first queries MQnsp (r) any E {0. 1 and checks the Σ continuation labels for the first index corresponding to empty prefix A. That indicates the first bit in the string accepted by the target function. Let 2 be the first bit of the target string, the learner then queries any string starting with x and obtains the second bits. Similarly, can iteratively query MQusp and obtain the string x² with at most N MQnsp queries.
While the membership query oracle in the NSP setting MQnsp is strictly more powerful than the one in the conventional classification setting, we show that there DFAs in the class DFA,, that cannot be efficiently identified with membership queries only in the NSP setting. Similar to the case of hardness of learning with DFAs, we will construction functions where the NSP labels uninformative and the problem becomes as hard as learning with the conventional membership query oracle.
Suftix Language f'amily. Consider the following family of languages. Let ) = {0, 1} (the argument applies to any Σ with |Σ] 2 2). Let S = {0, 1 N/2 be the set of Boolean strings of length exactly N/2. The suffix language family Ls contains N/2 languages, where for each s E {0, N3/2, the language L. Ls only accepts strings which end with the suffix s.
Each of the language L. E Ls can be represented by a DFA of size at most N/2+1. 1. For any suffix or string s, create a state corresponding to each prefix of s So ... SN/2 including the empty prefix 80 À which serves the start state. Define transitions 5(8.,, 8k+1) 8 For every
18

---

Published as a conference paper at ICLR 2026
other transition, if the symbol is $1, then they go to the state 8:1 else they go to so. From the first state, the shortest string that leads to the accept state is of length N/2. For every other state qi in
Q1.....QN7 the shortest accepting suffix is of length N 2 -
Proposition E.1. The class of Suffix languages Lis cannot be identified in polynomial time with membership queries MQnsp in the NSP setting.
Proof. A key characteristic any of suffix language L. is that, an accepting string exists for any prefix x. For any string v, the string 8 is in the language Ls. Thus, the continuation label for any prefix of any string will always be (v0(1; 0), p(x, 1)) = (1, 1). Hence, the continuation labels are not informative. The only informative signals are the membership labels.
In the NSP setting. the oracle MQnsp will provide the membership labels of every prefix. Suppose a learner makes Qusp queries where the maximum length of the queried input strings is k. Then each query eliminates most (k + 1) 3 k suffixes out of 2 possible suffixes if all the membership labels are O. Thus, in the worst case, the learner can eliminate at most ((mk) suffixes or functions from the class. If both the number of queries m and input length are polynomial in N, then they cannot identify the target Hence, either the number of queries must be exponential or the learner must use exponential computational steps.
Since the suffix language with suffixes of size n/2 be represented with DFAs with at most states, Prop. E.1 immediately implies that the class DFA, cannot be identified in polynomial time with membership queries alone in the NSP setting even with the richer set of labels.
Boolean functions and Acyelic DFAs. A similar argument applies to the class of Boolean functions as well. Consider the class of functions F2N_1 over f0, 1 which accept all bit strings of length N except one. It is straightforward to see that every function in that class can also be represented by Boolean Acyelic DFAs with exactly N 2 states.
For such a class, the continuation labels will be unhelpful for all but one prefix of length N - 1. The same line of argument as earlier shows that each membership query can eliminate most 1 function from the class. An adversary can decide to return membership labels 0 for every input query and choose the function based the inputs queried by the learner, and hence in the worst case, the learner must make N - 1 queries before it can identify the target functions.
This implies that certain classes of Boolean functions as well as the class ADFA, cannot be identi- fied with polynomial number of MQnsp queries in the NSP setting.
F EQUIVALENCE QUERIES AND IDENTIFIABILITY
Let Å and A be hypothesis and target DFA, respectively. In the NSP setting, a valid Equivalence Query oracle EQ (A; A+) with respect to target A should take a hypothesis Á as input and output 'equivalent" if L = LA- or else it should return a counterexample x E L such that fx(x) # (z). In other words, the counterexample is a string that is accepted by the target DFA A but disagrees with Å on at least one of the NSP labels.
Since the Equivalence query oracle can only produce strings accepted by A", it is not immediately clear whether a counterexample will always exist when LA * TA We show that positive examples
with NSP labels sufficient in the sense that for any pair of DFAs Á, A such that L * 0, there is always a counterexample if L # LA. The following result is crucial for exact learning of DFAS with membership and equivalence queries be feasible.
Proposition 3.1. Let A + A' be minimal DFAs with LA * (.. Then there exists E LA such that (x) + (x). Equivalently, the oracle EQ(A; A*) well-defined: it either returns "equivalent" " or a positive counterexample (x, J (x)).
Proof. Since A + A', there exists a string 2 E Σ" with A(z) + A'(x). take z; the NSP vectors then disagree in the membership coordinate for the full prefix 2, so fa(x) + (x) and we are done. Thus assume
If A' = 1, we may
A(=) and A'(z) =0,
19

---

Published as a conference paper at ICLR 2026
and let q' (qu, 2) be the state that the DFA A' reaches after traversing the string distinguish two possibilities for q'
We
Case (i): q' * 4dead- Because A' is minimal, any non-accepting state distinct from the dead state has an accepting continuation (otherwise would be equivalent to qdead and hence identified with by minimality). Hence there exists suffix E" such that 8))
Let x == 2 s. In the NSP label sequence for x, the membership coordinate at the prefix & is
LA(2) = and (2) 0,
so fA(Ø) # (x)). The oracle may therefore return this positive example together with (a)
Case (ii): q' Gdead- Write w1 ... WN with w; E and set 2; == w.... ... w; for 0 S $ N
(with 2:0 = X). There exists index E {0. .o. N - 13 such that
(go z3)) # qdead and
6 2.111) = Qdead-
Az) 0 and the DFA A' ends at qdead after traversing z, select the first position which qdead is entered. By minimality (as in Case (i)), the non-dead state (g0, 2;1) admits an accepting continuation; hence there exists suffix s E" with A' A'zz; s)
For the continuation bit at the prefix 2; and the next symbol w1+1, implies
A Wi+1) = O.
On the other hand, since A(=) and Z, Wi+11 (wa+2 ... WN), there exists suffix (namely W4+2 .. WNN witnessing that
pA wi+1)
Now set x := s. This is accepted by A', and the two NSP labelings disagree at the continuation coordinate (2:g, w;+1):
fa(x) (x) =. Thus is valid counterexample for the oracle.
In either case, there exists a positive example x (accepted by A') with fa(a) + fx(( and if no such counterexample exists, then A A'.
G LEARNING WITH MEMBERSHIP AND GENERATIVE QUERIES
In this section, we will show that the class of DFAs is PAC-learnable in the NSP setting with mem- bership queries and generative queries which provide NSP labelled positive examples conditioned on input strings. The setting is inspired by the information one obtain via blackbox access the next token probabilities of any language model. When the language model a formal device such as Probabilistic DFA (See App. C) then we will (approximately) learn the support of the language model. For practical neural language models, our algorithm will learn the truncated support of the language model as defined in Section 2.2
We will restate certain definitions and preliminaries in more detail here for clarity.
Problem and Assumptions. Let LM be language model which induces distribution over strings DLM- The support of the distribution PLM is a regular language LA" which is recognized by the DFA A'. We will assume that the expected length of strings generated by the language model finite. Given blackbox access to such a language model, we would like to find Á such that Ex-DEM [x))xxx)= - JA- (x)]l. < with high probability.
Recall that, in this setting, learner has access to two types of queries: (i) Membership queries
MQ(z) E {0, 1) which returns (*)),, and (ii) Generative queries Gen (-) which takes input string or prompt x and generates a string s along with NSP labels based on the distribution DLM conditioned on the prompt We describe how these queries can be simulated by practical language models in Section G.3
The next statement is the main result, which formalizes that with extension of L", obtain an algorithm that, with high probability, outputs an automaton A using membership and generative queries such that Lxsr(J (J JA, DLM) S
20

---

Published as a conference paper at ICLR 2026
Theorem 5.2. Let A E D be any minimal DFA with at states, and let DLM be distribution over strings whose support is LA-- There exists an algorithm with access to the mem- bership query oracle MQ and generative query oracle GenDi producing NSP labeled examples in LAs, that runs in time polynomial in n, //e,1/ and the length of the largest string produced by the generative query oracle, and with probability at least -ô, outputs DFA A such that,
EE DOMDLM
fa
To prove Theorem 5.2. we will show that there exists a consistent learner which takes m NSP labelled examples from PLM and, by using the generative and membership query oracle, always returns hypothesis Å that is consistent with all the m examples in terms of NSP labels. Our learning algorithm will be based on Angluin's s L* algorithm (Angluin 1987). We will first discuss the preliminaries of the framework based on modern and minimal treatments (Mohri al. 2018 Kearns & Vazirani
1994 Colcombet et al. 2021)
G.1 L-STAR PRELIMINARIES
Let Å be hypothesis DFA constructed by learner and let A" be the target DFA. We will refer to string such that A(x) * (z) as counterexample (typically provided by an Equivalence query oracle).
Access and Test words. In this setup, we will have a pair of sets (Q,T) where Q C Σ" is set of access words, and T S Σ" is a set of test words. Both Q and T are always nonempty. Intuitively, the set Q will play the role of states, where it will have a string corresponding to every state of our DFA. The test words T act as distinguishing strings for the access words Q. Both the sets Q, T contain the empty string We will now define the notion of T eqquivalleeee.
Definition G.1 (T-Equivalennee. For a non-empty set T C Σ' and a language L, two strings u, are 7 --equivalent: =T v, if for every string E T, the string
L if and only if v E L.
Closed and Separable. A pair (Q,7) is closed if for every access word q E Q and every symbol E Σ, there exists an access word q' E Q such that q a = q'. pair (Q.T) is defined to be separable if every two distinct access words q. q' Q are not T-equivalent: q #r g'-
Constructing a DFA. Given a closed and separable pair (Q, T') and access to membership queries MQ, one construct DFA follows.
Set the qo x E Q.
For every g Q, add them the of final states F' if MQ(q) -
For any access word q and symbol a E Σ, let g' be the word such that a =T d' Then set the transition ō(g, o) = q'. Since (Q, T) is closed, such state or access word of must exist, and separability implies uniqueness of such a word.
To prove the correctness of our algorithm, we use the following technical lemmas from I.* without proof.
Lemma G.1 (L* Fact (Angluin, 1987)). Let (Q,T) be closed and separable pair of sets which consistent with some language Let A be the minimal automaton that decides L. Then,
[Q1 < |A*)
The above Lemma follows directly from Lemma C.I and the fact that we have distinguishing string in T for each pair of strings in Q.
Lemma G.2 (I. Fact (Angluin 1987). Let () be a pair that is separable but not closed. Then, using most identify q' & Q such that (Q (QU()
membership queries, and in time polynomial in (IQ), El), we can (d',.T) T) is separable.
The following lemma is the crux of the original L* algorithm in terms of how it updates the pair (Q, () based disagreement between the hypothesis DFA and labelled example.
21

---

Published as a conference paper at ICLR 2026
Lemma G.3 (L* Fact (Angluin 1987), ). Let (Q,T) be a closed and separable pair. and À be the associated DFA. Suppose E E" be string such that A(x) + (x)). Then using at most |at membership queries and in time polynomial in [x), we can identify q' $ Q and t' & T such that (QU is separable.
G.2 PROCESSING COUNTEREXAMPLE, IN THE NSP SETTING
Similar to L", our La algorithm will maintain a pair (Q. and iteratively expand the sets by finding new states and distinguishing strings based on disagreements with the training examples. However, in the NSP setting, the disagreements in labels need not always be based on the differences in the memberships of strings, but can be based on the continuation labels. Hence, Lemma G.3 does not directly yield us our desired algorithm. The key difference between L* and Lusp is in how they obtain and process disagreements between predicted labels and true NSP labels.
Let Å be the hypothesis DFA constructed by a learner based on closed and separable (Q, T) and A be the target DFA. In the following lemma, we will show that when presented with an NSP labelled such that f (a) * fa- (1) (either from training set or an Equivalence query oracle), the learner can find at least one new pair of access word o' & Q and test word t' & 'T' using membership and generative queries.
Lemma 5.1. Let (Q, T) be closed and separable, and let Å be the minimal DFA induced by (Q, T). Suppose there exists a string x with fz( * fz)(2). Then one can find g' & Q and t' & T such that (QU (d); TU ((')) is separable, using membership queries and most one generative query in polynomial time. If a generative query is used, let denote its output; otherwise set y = X. The total number of membership queries is at most [z| + lg), and the running time is polynomial in |x|| + 1y1 + +Q)-
Proof. By definition, we have a string such that (x))) = 1 and fa(x) * fa)( Thus, there is prefix z.n of which the NSP labels disagree; the disagreement either (a) in the membership label for I.n. or (b) in one of the continuation labels for some symbol a E Σ. We treat these two cases separately. For all cases, our goal will be to construct a string x' such that we can invoke Lemma G.3 to obtain q' and t'.
Case A: Membership-label disagreement. There exists a prefix I.n of x such that (I:)) * Á(x:)). . In this case we may simply take x' = Ven and apply Lemma G.3 That lemma produces an access word o' & Q and test word E' & T in time polynomial in (and using most [x'] membership queries), and it guarantees that (Q (g'), (t(tt)) is separable.
Case B: Continuation-label disagreement. There exists prefix I.n of a and a symbol o e such that
@ (A 0) # Ap (Non; r).
We distinguish two subcases according to the value of the target continuation label.
Subcase Bl: &a (Z:n: d) 0 and y (I:n. σ) 1. By the semantics of the continuation labels for the target, A (Zon, o)) = 0 means that for every suffix E Σ' we have (' a s) = On the other hand, 4 (Z o)) = 1 means that the state q == ò (4o, x.n σ) that À reaches after traversing I.n is not the dead state.
Therefore, we can search within À from q to see whether there is some accepting continuation. Run a breadth-first search in À starting at q if the search reaches a final state q E F let s' be a shortest suffix labeling such a path. Then by construction, the length |s'| < |Q] and
A ( s')
and Á(z.. σ o') =1
so x' == J.n. s' is standard membership counterexample. Applying Lemma G.3 to x' yields of & Q and t' & T in polynomial time.
Subcase B2: PA (Z:n, o) = 1 and & (I:n: σ) 0. The target label yA pA (Tm, 0) asserts that there exists a suffix s' E D with (I o s') = 1. In contrast, & (X = 0 means that 5 DA(4 (6 (90, x.n), o)
gdead; hence A(x.. a 8) 0 for every suffix
22

---

Published as a conference paper at ICLR 2026
As consequence of Prop. E.1 also have that such suffix cannot be found in polynomial time using membership queries only. Thus, to find an accepting suffix, we call the generative query oracle with input 2:n." Since (p (I:n, σ) = 1, such a suffix is guaranteed to exist. Let s' GenDLM (Iim a) and we have x' 2.n a. -s' which is rejected by A (since it reaches a dead state after reading I.n σ). Thus, invoking Lemma G.3 on x' produces the desired q' and t' in polynomial time.
In all cases we obtain g' & Q and t' & ' such that (QU(g') (t')') is separable. This completes the proof.
Theorem G.4. Let A be the minimal DFA that recognizes the support language LA- C E* of the distribution DLM- Given m NSP labelled examples X = (xx6) fA. (x(0)) with access to mem- bership query oracle MQ and generative query oracle GenDuS with respect to DLM, Algorithm outputs DFA À such that J (1x(00) J (xx5) for all i = 1,....,,m The running time is polyno-
mial 1 max; (x(0),, and the length of the longest string returned by the generative query oracle.
Proof. If the target language is LA = then the initial hypothesis DFA Å at Line 6 will also be such that Á(x) = O for all x E Σr. Whenever disagreement with any training example is found, by Lemma 5.1 the algorithm will add at least string to Q and effectively identify least one new state from A By Lemma G.I we have that |Q] S [A*| and thus after at most |.A*| iterations of the main loop (Line 7 equivalently, at most | calls to Lemma G.3 we have that !Q) |A* Each state in Q is uniquely identified with a set of distinguishing strings that are consistent with A Since (Q, T) is closed and the transitions are defined using membership queries check T T'eqquivaennce, the final DFA isomorphic to the target DFA A" Hence, in such case Å = A and the hypothesis must be consistent with all training examples. Thus, it will terminate. The algorithm can of course terminate with |Q] < [A*] if the hypothesis DFA is consistent with all the training examples.
As a consequence of the above theorem and the fact that log DFA,/ O(n logn) (Lemma C.3 Theorem follows from standard Occam's 's razor arguments.
G.3 SIMULATING MEMBERSHIP AND GENERATIVE QUERIES
We describe how membership and generative queries be conveniently simulated by blackbox access to the target language model LM. For a neural language model, the empty string corresponds to [BOS] token.
(i) Membership Queries. Given a query string x = W1 wy E Σr compute the NSP continuation labels for every prefix of using the language model including the empty string A. For neural lan- guage model, this is simply done by obtain the next token probabilities for each prefix and applying the truncation rule T (cf. Sec. 2.2). If for any prefix the continuation label (2 Wn+1) = 0 then Wa41 is not valid continuation so the oracle can return O. If the path traversed by wt, wi is valid, then we can check whether (EOS)) 1 or O and thus MQ(x) (( [EOS]).
(ii) Generative Queries. For any string or prefix x, the Generative Query Oracle Gen (I) pro- vides (s, 3) where is a string from the distribution D' conditioned x. If no such continuation exists and x is at a dead state, then it returns 'None'. To simulate the example oracle or equivalently, to obtain examples from the target distribution DIM one can simply query the oracle with empty string Ge (A). To obtain a continuation for particular prefix 2, one can provide it as an input prompt to the language model and first check whether x traverses a valid path based on the NSP labels as described above. If it does not then return 'None'. If it does then, then iteratively sample the next tokens using the truncation rule until the [EOS] is permissible ş(# s, [EOS]) = 1.
G.4 ON EXACT LEARNING WITH MEMBERSHIP AND EQUIVALENCE QUERIES
We show that the class of DFAS can be learned exactly with membership queries and two types of equivalence queries. (i) F. (A; A+) which returns positive NSP-labelled counterexample with
23

---

Published as a conference paper at ICLR 2026
Algorithm nep algorithm
1: Q - (A), T {Y}
2: x= (oli), fAA (z())))
b call GenD (A) m times
3: while (Q.T) not closed do
4: Use Lemma G.2 to obtain d' QU
5: end while
6: Construct hypothesis automaton from (Q,T)
7: while Á not consistent with X do
8: Choose I E X with fx(x) + (x)
9: while fx * fa- do
Use Lemma 5.1
10:
Let Z;n. be the prefix with first NSP mismatch
11:
let denote the symbol if it is continuation mismatch if membership mismatch at C:n. then
12:
>. Case A
13:
w/ Tiz
14:
else if' continuation mismatch with A forbids and admits then s' find A-accepting suffix from Z.n"
> Case B
16:
w' t +Zn a. s
else
Case B2
18:
w' <- Ien GenDiM (Een σ)
19:
end
20:
Use Lemma G.3 on w' to obtain of and L'
21:
Q c QUiQQu/u + [t)
22:
while (Q,7) not closed do
23:
Use Lemma G.2 to obtain d:: Q - QU(( end while
24:
25:
Reconstruct À from (Q.T) end while
26:
27:
end while
at least one disagreement in NSP labels else it returns equivalence: (ii) EQ (A; A²) which just returns a string with no additional labels, such that the string is accepted by but rejected by A there exists such string, otherwise it returns none. The problem of learning with just memhership and NSP equivalence queries remains open.
For the setting where learner has access two types of equivalence queries, the algorithm is almost the same as the one described earlier (Alg. I with a couple of differences. Similar to the previous algorithm with membership and generative queries, the learner will maintain pair (Q,7) and iteratively update them, but with counterexamples from EQusp instead of a set of labelled examples. There are only two changes to address, which we describe below.
(i) The first thing to note is that by Proposition 3.1 the equivalence query oracle EQ+ Esp is well- defined and always guaranteed to return a counterexample. If the target DFA A" is such that LA- W. then the initial hypothesis DFA in Line 6 of Alg. will be the same as A and thus, we do not need any counterexample.
(ii) Secondly, we do not have access to generative query oracle anymore, so we cannot use it to find an accepting continuation when the target NSP label says that suffix exists, but for our hypothesis DFA, no such suffix exists. The difficulty is that EQ against our hypothesis need not return counterexample beginning with the particular prefix I'n a. To force such a witness, we will use EQpas (A, A+). Consider the DFA Axmo whose language is
LA == E ...")
i... Az..o accepts exactly the strings that do not begin with the prefix I.n Submit the equivalence query EQuas! (Ar,,,; A*). Because A (I:., or) = 1, there exists an accepted string with prefix Jen o; therefore, the oracle must return a positive counterexample of the form
d'
I:n s' with A A*(x') 1.
But x' is rejected by (the run reaches the dead state after reading I:n G), so is again a standard membership counterexample.
24

---

Published as a conference paper at ICLR 2026
2, & Key vs Sample
0.30
Tamit-2
NSP accuracy (%)
Tomila-3
Tomita4 4
0.25
Tomie-3 Tomit
0.20
states
0.15
0.05
Target states
0.00
101
Sample
Sample size
Sample
Figure 5: Key metries for Lasp other Tomita grammars. See Sec. 6 for details.
Correction Queries. In the above approach and Sec. 5 generative queries and the positive equivalence query oracle to find an accepting suffix. learning model where the learner has access something called correction queries (CQ). For string & E E", using the query CQ(x) will return the shortest accepting suffix (i) if x is not in the target language and (ii) if such accepting suffix exists. If the x: is in the target language, then the oracle can return an empty string, and if no accepting suffix exists, then CQ returns a special symbol not in the alphabet >. Thus, CQ provides the information provided by MQ along with an accepting suffix when it exists. Boccrre-Bonache et al. (2006) analyze learnability with correction and equivalence query oracle the conventional classification setting. CQ and generative queries are closely related in the sense that generative queries can be seen as a diittibutiion-deeedden version of CQ along with additional NSP labels. In the NSP setting, using the approaches discussed ahove, it is straightforward to that the class of DFAs is exactly learnable from positive examples only with a correction query CQ and equivalence query oracle E'uuep'
et al. (2006) proposed a
It is unclear whether exact learning with just membership and the NSP equivalence queries is fea- sible and left as an open problem. When the learner gets a counterexample such that the only disagreement is of the form that (P (Z:ns r)) 1 and 4 ( o) O, then one might wonder if a continuation can be recovered using the NSP membership query oracle MQusp which provides additional label. But consequence of Prop. E.1 such accepting continuation cannot be found in polynomial time using MQnsp-
Table 1: Tomita grammars and descriptions.
Tomita grammar
Description
Tomita
Strings of only Is (including the empty string), 1*. Repeated "10" pattern, (10)*.
Tomita 2
Tomita 3
Any block with an odd number of consecutive Is is always followed by block with an even number of consecutive Os.
Tomita 4 Tomita
Strings that do not contain 000 as substring.
Strings with an even number of Os and an even number of 1s.
Tomita
Strings where the difference between the number of Os and the number of Is is multiple of 3. 0*1"0"1* (zero or more Os, then 1s, then Os, then Is).
Tomita 7
H FURTHER EXPERIMENTS AND DETAILS
We discuss additional details of the experimental setup as well as additional results for DFA extrac- tion from language models.
H.1 ADDITIONAL DETAILS OF THE SETUP
Tasks. We provide additional details about the tasks considered in experiments.
Tomita grammars. Table [ooled[rooviee the description of the 7 Tomita grammars (Tomita 1982) in the benchmark. We use all of them except the first one since is trivial (1"), and the results are uninfor-
25

---

Published as a conference paper at ICLR 2026
Figure 6: DFA with 26 states extracted by Liep from Transformer trained on Parity. See App. H.2 for more details.
mative. All the regular languages in the Tomita benchmark have 2-5 states. These benchmarks have primarily been used to extract DFAs from RNN or Transformer-basee classifiers (Wang et al. 2018 Weiss et al. 2018 Zhang et al. 2024).
Parity. The Parity language is simple two-state DFA recognizing whether the number of 1s in string is odd or even. This task has been widely in the context of Transformers and previous works have shown empirical (Bhattamishra et al. 2020a) and theoretical (Hahn & Rofin 2024 Hahn 2020) evidence to indicate that such functions are difficult for Transformers to model.
Bounded Dycks. DYCK-(n, (n, k) represents the language with well-balanced parentheses with types of brackets and depth at most k. These languages have also been widely used in analysis of sequence models (Hewitt et al. 2020 Bhhttamishha al.. 2020b) since they capture hierarchical dependencies prevalent natural languages. These DFAs have a relatively larger number of states than Tomita grammars and Parity, and hence provide testbed to evaluate learning algorithms languages with increasing state complexity. We use the following languages in our experiments: D2CK-(2,2): 8 states, DYCK-(2, 4): 32 states, DYCK-(3, 3): 41 states, and DYCK-(4, 3): 86 states.
The experiments in the paper are not compute heavy. All our experiments were conducted using 8 NVIDIA Tesla V100 GPUs each with 16GB memory for training language models. Each run for up to 40k steps could take 1-6 hours, depending on the task. Some runs are much shorter if the model achieves high accuracy quite early. The execution of T.gap primarily on CPU, and uses the GPU to answer Generative and Membership queries with the Transformer language model. The time taken for each run Lisp is provided in the main plots (Fig. and 5
Compute.
H.2 IDENTIFYING ERRONEOUS EXAMPLES
When the Transformer models trained regular languages not perfect, the extracted DFA is not isomorphic to the target DEA used to generate training data for Transformers.
There two key things note about this event. (i) When the extracted DFA has the target DFA (such as for Parity in Fig. 2). then it implies that the support language for Transformer has at least many states as the extracted DFA. This is because states are always created after identifying distinguishing strings (Lemma C using the teacher model. (ii) The cases where models are not perfectly trained and our extracted DFA identifies erroncous strings, the models are still well- trained in the sense that all 1K strings generated using the language model are in the target language. Thus, the difference comes from disagreement in some NSP label which the T algorithm then leverages to extract a bigger DFA, which is then used to identify erroneous strings.
states than
Method. When the learned DFA Å is not isomorphic to the target DFA A", we construct the product automaton B Á x A where each state of B is pair (p.g) with Q(A) and Q(A"); on input symbol a. B transitions óg (p, q), a) = (6 ( (p, a), 6 (q. a)). The state (p, q) is accepting and only if exactly of p q accepting (XOR). The product DFA accepts the strings in the symmetric difference of the hypothesis and target DFA L(B) L(Â)AAT(A)). We then enumerate
26

---

Published as a conference paper at ICLR 2026
Figure DFA with 28 states extracted by ssp from Transformer trained on Tomita-5. See App. H.2 for more details.
erroneous strings by doing a BFS-like search within B to find accepting strings in nondecreasing length order.
Table 2: Examples of erroncous strings found via extracted DFAs. The A column within states denotes the number of states in the target DFA used to train the language model. The column indicates the number of states in the extracted DFA. Ground truth labels are denoted by Ves and Teacher LM labels by yr- Note: The models used as Teacher LM for Tomita-5, DYCK-(2, and DYCK- (3, 3) for these results were imperfect and not the same models used for the experiments in Figure See Sections 6 and H.2 for more details.
Language
States
Labels
Erroneous string J:
|A"|
|
y+
yr
1
Parity
2
26
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
1
C
1
Dyck-(2,2)
8
189
0
(
0
)
0
Dyck-(3,3)
41
87
0
[
]
[
0
[
0
0
0
1
0
0
0
0
0
Tomita-5
4
28
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
Results. We observed erroneous strings for languages like Parity, Tomita-5, DYCK-(2, 2), and
DYCK-(3, 3). Examples of some erroneous strings identified by the hypothesis DFA is provided the DFAs extracted for Parity and Tomita-5, respectively. The DFAs for DYCK-(2, 2) and DYCK-(3.3) 3) are too large to be visually interpretable. Constructing the prod- uct DFA is efficient and identifying several erroneous examples takes only few seconds. There is no natural distribution over the symmetric difference language and further it can even be finite in some cases which makes difficult to systematically compute the accuracy of predicting erroncous examples using the extracted DFA. The closest signal we have is the NSP accuracy for the extracted DFAs which near perfect.
in Table 2
Fortunately, identifying strings the symmetric difference language of Á and A quite efficient which can allow one to find numerous erroneous examples (if they exist). For instance, with Ik strings generated from Transformer trained on Parity, the Lisp algorithm extracted DFA with 26 states within 10 seconds, and using the extracted DFA, we identified 1k strings in the symmetric difference language L(A) in 16 seconds. Out of the 1000 strings identified by Á, 987 of them were erroncous: (*) * MQ(x) where MQ(x) denotes whether the string was in the support of the teacher language model and Ax indicates whether the string in the target regular language. Thus, such an approach can sometimes be far more efficient than finding erroneous strings by repeatedly sampling from language model and testing whether they correct not.
For all languages except Parity, the language model became more robust when we retrained them for longer steps. The curves for Tomita-5, and the two Dyck languages in Fig. 2 are with retrained
27

---

Published as a conference paper at ICLR 2026
and more accurate Transformer models. We suspect that for the lengths considered in this paper, retraining a larger Transformer on Parity for longer might make more robust, but we keep the imperfect model to illustrate the differences in Fig.
H.3 PRACTICAL NOTES ON THE ALGORITHM
As mentioned in Sec. 7 if the DFA representing the support of the language model has a large number of states, then the extraction algorithm can be extremely slow. The key bottleneck for Tusp the same as L', which is the closure step (Line 22 in Alg. Tb. Even though it is polynomial, the time complexity O (([Q[T][E) blows up when both Q and [T] are in the order of thousands, since the process is sequential. We observe that when the models are partially or poorly trained, then the number of states blows up, and the algorithm slows down significantly, failing to terminate even after a day.
The other step where the Lasp algorithm might fail is if the assumptions about the learning problem are violated which case the use of generative queries to find accepting suffixes (Line [8 Alg. D may not terminate. If the support language is not regular, then even though continuation is per- missible according to min-p/top-p sampling, the language model may still not terminate. However, we did not observe any instance of this problem in all our experiments. We suspect that since the
language models are typically trained to predict [EOS] after certain steps, they always terminate (EOS token becomes permissible) after certain number of inference steps.
Tokenization.
Another practical consideration concerns the effect of tokenizers. The algorithm can be applied to character-level language models and to word-level models with distinct word vocabu- laries in a natural way, since in both cases the alphabet aligns closely with the underlying notion of a string. For subword or BPE tokenizers, while the algorithm can be applied as is, one needs to be more careful about the semantics of the extracted DFA. The algorithm treats the language model as a black-box sequence model over an alphabet of discrete symbols, so in all cases the learned DFA captures the model's behavior over sequences of elements of Σ, and our guarantees apply at this level. However, with subword tokemizers there is typically no one-to-one correspondence between token sequences and character strings, since single surface string may have multiple tokenizations that the model treats differently. As a consequence, the DFA learned over tokens should be inter- preted as describing the token-level support induced by the fixed tokenizer and decoding rule, and cannot, in general, be read directly as an automaton for a specified character-level regular language.
Efficiency improvements. While the algorithm is polynomial-time it could still be challenging to run it at scale as described above. To mitigate those, there are few natural ways to avoid redundant computation and improve efficiency in practice. (i) LRU Cache for MQ. In our implementation, we use an LRU cache with the membership query (MQ) oracle. The key computational bottleneck in the algorithm is that requires many MQ calls in the closure steps where each MQ call is essentially a forward pass through the teacher language model. To avoid querying the label of the same string multiple times, we have an LRU cache which stores the last 10 recently used strings which when queried directly return the label instead of making a pass through the teacher LM. (ii) Parallelization. Another concrete direction to improve efficiency is to parallelize the calls in the closure steps. The key observation is that the MQ calls in the closure step need not be in any particular order. Hence, one could query the labels of multiple strings by processing them as a batch through the teacher LM. To do so along with the LRU cache, one could take the following approach: suppose the closure steps requires K MQ calls and let batch size be B. One could sequentially go through the strings to be queried and add them to a queue if they are not in the LRU cache and if string is in the cache, then directly return its label. If the size of the queue reaches B or there are no more strings to be queried, then algorithm can pass the items in the queue as a batch through the teacher LM. This could lead to tangible gains with GPUs which can fit large batches.
H.4 ABLATION: USAGE OF CONTINUATION LABELS
When we apply the Lisp algorithm on positive examples, information about refinements new states is provided by two types of labels: (i) prefix membership labels, and (ii) continuation labels. Within continuation labels, there are two cases described in Lemma Whenever the algorithm finds one of the three types of disagreements in the NSP labels between the hypothesis DFA and the examples in its set, it refines the DFA and adds one more state its hypothesis.
28

---

Published as a conference paper at ICLR 2026
Table Usage of different types of NSP labels by the Lasp algorithm on various tasks, Refinement indicates the number of times states were added through disagreements (number of times loop in Line 9 is executed or equivalently Lemma [5.1 is invoked. Mem fraction denotes the percentage of times prefix membership labels were used. B and B2 fractions denote how many continuation labels were used. See Sec. H.4 for more details.
Language
States
Prefix Memberships (%)
Cont. (%)
Cont. (%)
Refinements
Sample size:
10
Dyck22
3.0
0.0 0.0
16.7 = 0.0
83.3 + 0.0
6.00 = 0.00
Dyck24
21.0
0.0 0.0
5.9
94.1 = 2.6
19.00 5.35
Dyck33
32.5 = 7.0
0.0 0.0
3.5 1.2
96.5 = 1.2
30.50 = 7.01
Dyck43
37.4 14.1
0.0
3.8 3.2
96.2 - 3.2
35.40 = 14.14
Parity
0.0
0.0 1.0
0.0 0.0
0.0 + 0.0
0.00 = 0.00
Tomita 2
0.0
0.0
0.0 0.0
100.0 0.0
1.00 0.00
5 5
4.0
100.0 0.0
0.0 0.0
0.0
2.00 = 0.00
Tomita 7
5.0
0.0
100.0 + 0.0
0.0 0.0
3.00 + 0.00
Sample size:
100
Dyck22
8.0 0.0
0.0 0.0
16.7 0.0
83.3 + 0.0
6.00 + 0.00
Dyck24
32.0 0.0
0.0 0.0
3.3 0.0
9.0
30.00 0.00
Dyck33
41.0
0.0
26 0.0
97.4
38.90 0.32
Dyck43
85.6
0.0
1.2
98.8 0.0
83.60 = 1.26
Parity
0.0
0.0
0.0
0.0
0.00 = 0.00
Tomita 2
0.0
0.0
0.0
100.0 0.0
1.00 0.00
Tomita 5
0.0
100.0
0.0
0.0
2.00 0.00
Tomita 7
5.0
0.0
100.0 + 0.0
0.0 0.0
3.00 0.00
Sample size:
1000
Dyck22
0.0
0.0
1.0
83.3 + 0.0
6.00 0.00
Dyck24
32.0 0.0
0.0
3.3
96.7 0.0
30.00 0.00
Dyck33
1.0
0.0
2. 0.0
9.0
39.00 0.00
Dyck43
86.0 = 0.0
0.0
0.0
1 0.0
98.8 0.0
84.00 = 0.00
Parity
18.3 15.7
70.0 48.3
48.3
0.0 0.0
0.0
11.80 + 11.72
Tomita 2
0.0
0.0
0.0 0.0
100.0 0.0
1.00 + 0.00
Tomita 5
4.0
100.0 0.0
0.0
0.0 0.0
2.00 + 0.00
Tomita 7
0.0
0.0
1.0
0.0
3.00 + 0.00
Results. We run the Lisp algorithm on representative languages and track the usage of the type of disagreement used update its hypothesis. Table 3 depicts the usage of different types of dis- agreements on three different sample sizes averaged across 10 runs. The prefix membership column indicates the percentage of times the prefix membership labels were used. The Cont. B1 column represents the cases where the hypothesis predicted that a certain continuation is permitted, but the continuation label indicated that such continuation is not allowed in the target DFA. The Cont. B2 column represents the cases where the hypothesis predicts that continuation is forbidden, but the true labels indicate otherwise. This is the case where the generative query oracle is invoked generate accepting suffixes.
The results indicate that continuation labels are heavily used for all Dyck languages. Such languages also contain several transitions with dead states, and the results indicate that the algorithm is able to leverage continuation labels to identify new states. On parity and Tomita-5, the algorithm relies only the prefix membership labels. This is natural since the DFAs for those languages do not have any dead states, and hence the continuation labels are uninformative. From positive examples, the algorithm obtain negative information from the prefix membership labels for such languages. Both Tomita-2 and Tomita-5 have a transition to dead state. Since these are small DFAs, the algorithm converges the target DFA with only few refinements.
29

---

Published as a conference paper at ICLR 2026
Tomita-2 (10)*
You are language generator. You will be given a regular language and you will generate one string that is in the language and end with \n (newline) character. Language Description: The language consists of binary strings of the form (10)", i.e., repeating "10" zero or more times.
Multiple examples of strings in the language (each string ends with newline \n):
generate:
generate:101010),
generate:10),n
10nera
gcnerate:1000101110|p
generate:101010|p
generate:
Parity (odd number of 1 symbols)
You are a language generator. You will be given a regular language and you will generate one string that is in the language and end with \n (newline) character.
Language Description: The language consists of all binary strings (alphabet = {0, 1 with odd number of "1" symbols. The number of zeros does matter and the number of "1"s should be odd.
Multiple examples of strings in the language (each string ends with newline \n):
generate: \nn
generate: 101 m
generate:010
generate:010101.
generate:111)p
generate:110011
generate:11llI\p
generate:
Figure 8: Example prompts provided to the LLM for regular-languae generation experiments. Each prompt consists of natural language instruction describing the target regular language and multiple exemplars illustrating valid strings from that language, terminated by \n newline character. See Sec. for more details.
I EXPERIMENTS WITH LLMS
In this section, we explore application of the Lisp algorithm extract DFAs from open-source LLMs. To mitigate the computational challenges associated with large vocabularies we restrict the vocabulary size during generation and to simplify tokenization, we use byte-level LLMs, which naturally fit in our setup. For experiments, adopt Meta's 's Byte-Level Transformer (Pagnoni ct al. 2025), which operates over Unicode characters and similar to a character-level language model.
1.1 SETUP
Tasks and Models. For our experiments, we use two LLMs (IB and 7B BLT (Pagnoni et al., 2025)) and 5 regular languages. The 5 tasks include (i) Tomita-2 (10)*, which contains zero more repeated blocks of '10', (ii) Tomita-4, which contains strings that not have '000' as a substring, (ii) Tomita-7, which contains strings from 0*'"0"1*, (iv) the Parity language, which contains an odd number of 1s, and (v) DYCK-(1, 4), which contains balanced parenthesis with type of bracket and depth at most 4.
30

---

Published as a conference paper at ICLR 2026
Table Results on extracting DFAs from IB and 7B BLT models using Lisp on regular languages. The NSP-Acc. column denotes the accuracy of the extracted DFA. The # States column denotes the number of states in the extracted DFA. The 'Baseline' column denotes the accuracy of predicting the NSP labels of the LLM using the DFA of the target language. The 'Erron. Acc,' column denotes accuracy of the erroneous strings identified using the extracted DFA. See Sec. for more details.
IB BLT
7B BLT
Language
NSP-Acc.
# States
Baseline
Arron.Ace.
NSP-Acc.
States
Baseline
Frron.Ace.
Tomita-2
100.0
10
0,0
100.0
100.0
3
100.0
NA
Tomita-4
99.5
7
0.0
99.8
99.6
35
0.0
99.2
Tomita-7
99.8
61
72.1
94.2
96.4
128
76.6
96.6
Parity
99.2
91.4
98.1
39
2.7
97.2
DYCK-(1,4)
94.0
53
22.9
83.2
97.8
99
73.3
85.0
These languages were chosen for the following reasons: Tomita-2 is one of the simplest languages and is useful to include as sanity test; yet even 1B model does not perfectly capture this lan- guage, as we will see later. Tomita-4 is relevant to the general use case for verification, where we would not want the model to generate something (e.g.. '000', passwords, or forbidden words) and would like the algorithm to detect that. Tomita-7 checks whether the model can generate a certain alternating pattern. Parity checks modular counting behaviour and is representative of some other Tomita grammars, which also involve similar modular counting. The language DYCK-(1, (1,4) 4) checks bracket-matching ability with one type of bracket. As discussed later, we also tried DYCK-(2, 4), but the LLMs were much poorer at generating well-balanced strings with 2 types of brackets than with 1.
Experimental Setup. For each task and model, we prompt the LLM to generate strings from the language. During generation, we restrict the vocabulary to the symbols of interest, which contain '(' and ')' for Dyck and 'I' and '0' for the others. Apart from that, the model is asked to end each string with the newline character "\n"", which serves as the [EOS] counterpart in this setup. The approach is quite simple and minimal. We provide prompt with three parts: (i) first, general instruction which tells the LLM that it supposed to generate a string from the language ending with newline, (ii) description of the language, and (iii) in-context examples. The prompt ends with the string generate: :, after which the model is supposed to generate a string from the language. A couple of example prompts are provided in Figure 8 To extract DFAs, sample 100 lab-llbelled strings from an LLM with top-p sampling with p = 0.9 as a training set and evaluate the extracted DFAs 1k freshly sampled NaP-labelled strings.
1.2 RESULTS
Accuracy of extracted DFAs. The first question that investigate is whether the DFAs extracted using the Ti algorithm are accurate with respect to the NSP accuracy or error defined in Sec. 2 Note that the NSP accuracy on any example 0 even one the predicted membership or continu- ation labels is incorrect. The NSP accuracy indicates how faithful the extracted DFA is in capturing the LLM's (truncated) support. Obtaining DFA with good accuracy is essential before conducting further analysis with the extracted DFA.
Table 4 summarizes the overall results and reports the NSP-accuracy for each task for the 1B and 7B LLMs. As can be seen from the table, for all tasks, the NSP-accuracies of the extracted DFAs are quite high (94%-100%). Note that the accuracy zero, and as baseline, we use the DFA from the target language (e.g., Tomita-2, Parity, etc.). The NSP-accuracy of the target baseline DFA denotes the accuracy that one would obtain if they used the target language DFA to predict the NSP labels of the LLMs. To avoid confusion, we emphasize that the goal of the extraction algorithm is to obtain a DFA that is faithful to the NSP labels induced by the LLM and not to the labels induced by the target DFA. As be seen from the table, the baseline accuracy using the target language DFA is quite low for most languages, more so for the 1B L.M.
random labelling function will be near
31

---

Published as a conference paper at ICLR 2026
Table 5: Examples of mismatch strings found via extracted DFAs. The columns An and An indicate whether the string was in the support of 1B and 7B LLM, respectively. The column A* indicates whether the string is in the target language. See Sec. for more details.
Language
Labels Am
Mismatch strings
A"
0
0
Tomita-7
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1 1
1 1
0
Parity
0
0
0
0
1
0 0
0
0
1
1
0
( (
( ( 3
Dyck-(1, 4)
()
0
(
(
C
We also explored DYCK-(2, 4). but the generation accuracies of the LLMs were quite poor compared to DYCK-(1, 4). While over 90% of the strings that the 7B LLM generates are in DYCK-(1, 4), for DYCK-(2, 4) this fraction was less than 30%. We ran the Lipp algorithm for DYCK-(2, 4), and the number of states blew up: the algorithm
not able to find a consistent DFA even after extracting over Ik states. We tested an extracted DFA with about 384 states, which was partially consistent with the training set, and its NSP-aceuracy on the test set was about 64%. This scenario falls into the regime discussed in Sec. [nd Sec. H.3 where the model is far from perfect and the number of underlying states is too large for our current implementation to handle.
Identifying Erroneous Examples. We also evaluate the effectiveness of the extracted DFAs in identifying erroneous examples. For each task, we use the extracted DFA to find strings in the symmetric difference between the hypothesis Á and the target language A", as described in Sec. H.2 order and report the correctness of the identified
We find the first 500 strings in examples, which indicates the percentage of times that a string identified using the product DFA is actually erroneous.
Table 4 depicts the accuracy of the erroneous examples identified by the extracted DFA, For Parity and the Tomita languages, the erroneous strings identified by the extracted DFA are quite accurate. For DYCK-(1, 4). the accuracies are still quite high but seemingly lower than for the other languages. Upon further analysis, we believe that the difference is due to the following reason: most of the strings in the training set for Lusp are quite short (length 20). When we identify erroncous strings order, the number of erroneous strings of length less than 20 is quite low (unlike Parity and the other languages), and the DFA identifies many strings that are of greater length than those seen during training. The accuracy of these strings is not as high, since they could be considered aut-of-distribution as well. If we look the first 100 erroneous strings identified by the product DFA, then over 90 of them are correctly predicted as erroneous by the extracted DFA. Additionally, we emphasize that finding strings from the product DFA is quite cheap, and even with an accuracy of 50%, it is much faster to generate erroneous strings from the product DFA and verify them using the LLM, compared to sequentially generating many strings from an LLM and checking whether they are erroneous.
in
Among the languages we tested, Tomita-2 is the only language where the 7B LLM seems to per- fectly capture the support. The support of the 1B LLM is also quite close to the target, since the symmetric difference between the extracted DFA and the target contained only two strings. In all other languages in Table the "SP-accuracies of the target DFA relatively far from the support, and various erroneous examples could be found. We also tested the sensitivity to the top-p parameter p E {0.8, 0.9, 0.95). We found that the 1B LLM was relatively more sensitive to this parameter than the 7B LLM. For instance, with p = 0.95, the DFA extracted from the 1B BLT model for Tomita-2 had over 500 erroneous strings, as opposed to just 2 for p 0.9.
Model Comparison. We investigate whether DFAs extracted from the IB and 7B models can be used to identify differences in the behaviour of the two L.MMs. In this analysis, we consider Tomita-
32

---

Published as a conference paper at ICLR 2026
7, Parity, and (1,.- For each language, we proceed follows. We take the two extracted DFAs, dΙ and ATg, and construct the product DFA ÅB ÅTg, which represents the symmetric difference language as described in Sec. H.2 We then generate 50 strings in length-lexicooraphic
order from the product DFA for which (I * (z) We inspect these mismatch strings to find systematic patterns and then check whether any identified pattern holds more generally using the extracted DFAs. While this approach is not the most efficient, we adopt it because the extracted DFAs, as well as the product DFAs, have many states and are largely uninterpretable visually.
Observations. Table 5 shows representative examples from the symmetric difference between the IB and 7B LLMs for each language. Based on the extracted DFAs and the mismatch strings, we make the following observations. The IB model is generally overly permissive, whereas the 7B model is overly conservative, the sense that the 1B model includes strings in its support that are not in the target language. Unsurprisingly, the 7B model is more accurate than the 1B model, but the cases where the 7B model incorrect are those where it excludes strings that should be in the support. Beyond this, we find systematic differences for 7omita-7 and DYCK-(1, 4), but are unable to identify any clear pattern for Parity.
Tomita-7. For Tomita-7 (0*1"0"1"), the language requires the string alternate between 0 and 1, starting with O, with at most alternations. The IB model contains many strings with more alternations (see the first two examples in Table 5]. The IB model also has strings of the form 100 in its support. Upon seeing such mismatch strings. we checked the extracted DFA A and observed that such strings lead to an accepting state in ÅΙB. The 7B model correctly excludes such strings from its support. Out of the 50 strings, the IB model is incorrect in a 60% of the cases. The strings where the 7B model incorrect are typically those that have or fewer than alternations, c.g., 00000, which belongs to the language 0" 1"0" 1 but is excluded by the 7B model.
Dyck-(1.4). For DYCK-(L, 4), the 7B model substantially more accurate than the IB model. All first 50 mismatch strings correspond cases where the 1B model makes a mistake. Looking at the next 50 mismatch strings, the IB model is incorrect on 49/50 them. We find two patterns in the mistakes made by the IB model. First, it includes strings in its support with unclosed brackets, i.e., prefixes of DYCK-(1, 4) that are missing one or two closing brackets (see the first two examples in the DYCK-(1, 4) row in Table 5 The model does not seem make mistakes of the form ( where the number of closing brackets exceeds the number of opening brackets. Second, the IB LLM sometimes fails to enforce the depth constraint and includes strings with depth >> in its support (see the last example in Table 5) while the 7B LLM correctly excludes them.
33


Reviews:
[{"review_id": "4iY3khCxTn", "reviewer": "Reviewer_3o3h", "summary": "The paper is a theoretical and empirical contribution to understanding language models learnability of formal languages by means of extracting automata from them. The data is regular languages with NSP labels (given a prefix, its acceptance as a prefix and the possible next symbols are labeled). The work gives a formal proof that for a given sized DFA the machine is identifiable with strings annotated with the NSP labels. The work also gives a L* variant (classic algorithm for identifying automata) algorithm for identifying the automaton by making use of a learned membership query and a simulated next symbol prediction, both using a trained language model (as in the original L* but with an oracle). A PAC guarantee is given that is connected to the error of the language model. This allows for extraction of DFAs from trained models, and can serve as a way to understand what “automaton” the trained model is simulating given the training data. Such an empirical study is conducted using 11 regular languages. There is also a hardness result showing how membership alone does not suffice to learn.", "questions": "Did you try at all to extract automata from public LLMs for simple languages to see how they implement something like parity? E.g. to benchmark them on whether they find minimal solutions or something of that sort. I see you point out this might be overly complex machines in the appendix, but I’m curious. \n\nDo you see a path forward to extending the work to WFSAs?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The work is thorough and shows us how we can cleverly extract automata from language models trained on synthetic data. This is backed up by theoretical results. The problem is well framed, the L* algorithm is nice and the guarantee accompanying it. Evaluation is done on 11 varied languages and the bridge between formal languages and neural languages is welcome.", "weaknesses": "The work is quite dense, and comes with a thorough appendix. I feel like it could almost have been more than a single paper. \n\nIt would have been nice to see more variations in the trained language models (architectures, hyperparams) , as an empirical study of learnability, but again that could be another paper. And same for some public LLMs.\n\nComparison to other ways to identify the machines could maybe have been done. I am not sure what methods would make most sense but i imagine there are some.\n\nTiny nitpicks: it wasn't immediately clear to me from e.g. figure 2 on its own what was being plotted until after reading the work. Maybe say (time to run L*), (number of states in found machine). Also in figure 1, the labels for the symbols make sense but they could be somehow marked as such.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QistOyScx1", "reviewer": "Reviewer_VJGS", "summary": "This paper introduces a new model for automata learning where the queries the learner can ask are the ones that are more naturally provided by a language model that exposes token logits at each step. That is, in normal automata learning, one can only ask membership queries (is this string in the language) and equivalence queries (did I find the right automaton, if not give me a counterex). Whereas the authors propose a setting where one can, given a sequence a1...an ask for every token b, whether a1..aib is in the language. This is a very powerful oracle that can provide many positive and negative examples at once. The paper shows that even with this powerful new model identification in the limit remains hard. They therefore move to a setting where the learner can ask the LM itself to generate positive sequences (together with their possible continuations). This approach yields a PAC guarantee (as long as equivalence is checked on the same distribution of the LM). The empirical analysis shows small DFAs can be relearned from a transformer (that were trained to recognize them).", "questions": "Can the authors do the experiment I discuss in weakness for some interesting regular expressions and small open LLM? Ideally with some practical regexes than Dick languages (maybe pick 10 from regexlib or automatark)\n\nHow does the algorithm change when moving from characters to tokens?\n\nWhy are there EOS tokesn between characters in 393? IS this a way to force a certain tokenization scheme?\n\nMINOR COMMENTS:\n- line 145: missing _L in phi\n- what does well-defined mean on l 210?\n- Spell out PDFA in line 388 and point to a reference\n- is the reference to Sec 2.2 in line 400 incorrect?\n- maybe relevant paper to cite https://arxiv.org/abs/2501.02825", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The formalization of NSP queries is a clean one.\n- The paper studies a question worth studying and though the hardness result is somewhat unsurprising (and also the generative one since very similar results hold for learning DFAs when strings are sampled from a distribution to mimic an equivalence oracle), it is nonetheless an interesting result that NSP queries help learning faster empirically as shown (i.e., if one has the examples handy, might as well use them).\n- The paper is formal and self-contained", "weaknesses": "- My main criticism of the paper is that open source LLMs provide the perfect setting for evaluating interesting questions and this paper instead has gone for training small transformers on toy languages. Before reading the eval description in the introduction, I was expecting this paper to do the following\n1. Prompt the LLM (any open one) with the query \"Generate strings that are accepted by the regular expression R\"\n2. Use L*NSP to learn what the LLM generate\n3. Compare automaton to R\nThen the evaluation would tell us whether 2B parameter models learn worse than 8B parameter models, for example, and what type of mistakes they make. I would love to see such an evaluation. One really interesting aspect would be to see when using (Real-world regexes) what characters LM \"prefer\" within character classes and how they fail to cover them\n- Related to the above problem is that the paper does not seem to discuss the fact that LLMs produce tokens and not characters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FrMBHehsPa", "reviewer": "Reviewer_xFFN", "summary": "The paper formalizes support identification for language models in an NSP supervision setting that mirrors LM decoding, establishes identifiability of minimal DFAs from positive NSP data, proves worst‑case hardness results that survive NSP labels, and proposes $L^\\*_{nsp}$, an extension of Angluin’s $L^\\*$ that uses LM‑simulable queries (membership and prefix‑conditional generation). Experiments with Transformer teachers on 11 regular languages demonstrate that modest positive NSP data suffice to recover the target or teacher‑support DFAs and to detect erroneous strings when teachers deviate.", "questions": "1. How sensitive is the learned support DFA to the choice and hyperparameters of truncation (top‑k vs. top‑p vs. min‑p)? Could the same teacher yield meaningfully different supports across rules?\n2. If the true support is not regular but “close,” does $L^\\*_{nsp}$ converge to a minimal DFA that best approximates NSP labels in expectation (e.g., a smallest consistent DFA on observed NSP data)?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. NSP exactly captures what a practitioner can extract from an LM under top‑k/top‑p/min‑p decoding. The focus on support (rather than probabilities) is natural and practically important.\n2. $L^\\*_{nsp}$’s Lemma 5.1 is a neat reduction from continuation mismatches to standard counterexamples using at most one generative query. This method does not require a perfect equivalence oracle which is often infeasible in practical.\n3. The evaluations are careful and complete. The method recovers large Dyck DFAs with tens–hundreds of positives and surfaces nontrivial errors. The ablations support the claim that continuation labels are particularly beneficial on languages with dead‑state transitions.", "weaknesses": "1. The regular-language focus is reasonable for support identification, but large vocabularies are the key obstacle for LM-scale studies. While the paper is honest about this, many NLP applications involve **huge vocabularies**. The closure step’s $(O(|Q||T||\\Sigma|))$ cost is problematic for realistic LMs, and the paper does not yet provide system‑level accelerations. If the authors can solve this concern I am glad to raise my score.\n2. The PAC guarantee is **with respect to the teacher LM’s own distribution**. This is appropriate for support identification but complicates cross‑teacher comparisons and may hide rare but catastrophic support errors (if the teacher rarely visits those prefixes). (Section 5.) \n3. $L^\\*_{nsp}$ sometimes needs one **generative** query to produce an accepting suffix. If the teacher’s support is not regular or exhibits long nonterminating paths under a truncation rule, the procedure may stall (H.3).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "esRREaxTp2", "reviewer": "Reviewer_4bT5", "summary": "The paper proposes a next-symbol-prediction-based formal language learning framework with applications in extracting formal descriptions of neural language models. This framework augments Gold’s seminal language learning framework with information about the allowed string continuations. This allows much larger classes of languages to be learnable from positive examples alone. Nevertheless, the authors show that the added information still does not enable efficient PAC learning of finite-state automata (FSAs), but in some cases allows for more efficient L*-style learning based on membership and equivalence queries. \nThe L* learning framework is compatible with using a language model as an oracle, which enables the authors to use the introduced algorithms to extract FSAs from trained language models. They find the algorithm to be very sample-efficient. Moreover, the extracted FSAs often agree with the ground-truth (whenever the neural model is well-trained), unless the language is hard to learn (like parity), as expected.", "questions": "- How does one (gracefully) handle learning states that are technically learned by the language model but not in the truncated support? \n- How does one choose the truncation threshold for the support of a language model?\n- Any intuition of what happens when the language is not actually regular? The number of states just keeps increasing?\n- Are there any convenient descriptions of languages where NSP information provably makes learning more efficient (even though it, in general, does not hold)?\n- I believe that, technically, it can hold that a symbol can be in the set of permissible continuations in a neural LM but never lead to a string in the support if the generation never halts (so-called improper or non-tight language models). Is that intuition correct? If so, should this condition be enforced? I suppose this is equivalent to enforcing a finite expected length, which you do?\n- Two nit-picks:\n\t- Is the framing of “positive examples only” completely justified? As mentioned, each (positive) example also brings with it possibly many negative examples (prefixes). This is purely a naming thing.\n\t- If the language model is regular (as assumed), the distribution over negative examples should also be regular (and thus defined and available)", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is very well structured and clearly written. The contributions are clear and in my opinion important.\n\t- Most significantly, the paper takes a well-studied and known learning setting and updates it to a well-motivated and relevant setting useful in modern language models\n- The results are theoretically thoroughly backed and explained with well-composed proofs.\n- Although the main contributions are theoretical, the paper provides extensive and well-justified empirical validation of the results with languages well-studied in the theoretical literature on neural networks and formal languages.\n\t- These experiments show the practical improvements of the proposed algorithm, which is also theoretically shown to be much more efficient in some cases\n- I found the FAQ section to be useful. \n- It is useful that the algorithm is completely specified and described understandably in pseudocode.", "weaknesses": "- The work is very well written and presented. I found no major weaknesses.\n- I just had one thought: I imagine looking at automata learned from some actual large-ish-sized language models would be interesting—maybe specifically domain-specific or domain-prompted large LMs. I imagine this is not possible with the current algorithmic complexities?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)