The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory

Romain Peyrichou

cs.CLMar 10, 2026

The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory

Authors: Romain Peyrichou

Organizations: Independent Researcher

Abstract

Every formal grammar defines a language and can in principle be used in three ways: to generate strings (production), to recognize them (parsing), or -- given only examples -- to infer the grammar itself (grammar induction). Generation and recognition are extensionally equivalent -- they characterize the same set -- but operationally asymmetric in multiple independent ways. Inference is a qualitatively harder problem: it does not have access to a known grammar. Despite the centrality of this triad to compiler design, natural language processing, and formal language theory, no survey has treated it as a unified, multidimensional phenomenon. We identify six dimensions along which generation and recognition diverge: computational complexity, ambiguity, directionality, information availability, grammar inference, and temporality. We show that the common characterization "generation is easy, parsing is hard" is misleading: unconstrained generation is trivial, but generation under constraints can be NP-hard. The real asymmetry is that parsing is always constrained (the input is given) while generation need not be. Two of these dimensions -- directionality and temporality -- have not previously been identified as dimensions of the generation-recognition asymmetry. We connect the temporal dimension to the surprisal framework of Hale (2001) and Levy (2008), arguing that surprisal formalizes the temporal asymmetry between a generator (surprisal = 0) and a parser that predicts under uncertainty (surprisal > 0). We review bidirectional systems in NLP and observe that bidirectionality has been available for fifty years yet has not transferred to most domain-specific applications. We conclude with a discussion of large language models, which architecturally unify generation and recognition while operationally preserving the asymmetry.

Figures & tables

Operation	Given	Sought	Analogy
Generation	$G$	$s$	The speaker knows the rules and produces speech
Recognition	$G+s$	Structure	The listener knows the rules and parses speech
Inference	$\{s_{1},\ldots,s_{k}\}$	$G$	The child has no rules and must learn the language

Table 1

Panel of Figure 1 — Figure 1: Shannon’s communication model and the generation-recognition analogy. The encoder (generator) knows the source with certainty; the decoder (recognizer) must infer it under equivocation $H(X|Y)>0$ .

Type	Class	Automaton
3	Regular	Finite automaton
2	Context-free	Pushdown automaton
2+	Mildly context-sensitive (TAG, CCG, MCFG)	Embedded pushdown
1	Context-sensitive	Linear-bounded automaton
0	Recursively enumerable	Turing machine

Table 3

Panel of Figure 2 — Figure 2: Commutative diagram: the round-trip test. Generation followed by recognition should recover the original structure — the failure of this commutativity measures the asymmetry.

System	Domain	Generation	Recognition	Inference	Bidirectional
LL/LR parsers	Compilers	—	$\checkmark$	—	—
Earley/CYK	FL*	—	$\checkmark$	—	—
NLG pipeline (Reiter & Dale)	NLP	$\checkmark$	—	—	—
Template-based NLG	NLP	$\checkmark$	—	—	—
LLMs (GPT, etc.)	NLP	$\checkmark$	(implicit)	—	—
DCG (Prolog)	NLP	$\checkmark$	$\checkmark$	—	$\checkmark$ *

Table 5

Class	Best algorithmic bound	Intrinsic characterization
$k=3$ Regular	$\Theta(n)$ by DFA (Hopcroft et al. 2006)	tight bound $\Theta(n)$
$k=2$ CFG	$O(n^{3})$ by CYK (Younger 1967); $O(n^{\omega})$ with $\omega\leq 2.37$ (Valiant 1975; Williams et al. 2024)	in $\mathsf{P}$ , conditionally equivalent to BMM (Lee 2002)
$k=2^{+}$ TAG/MCFG	$O(n^{6})$ (Joshi & Schabes 1997)	in $\mathsf{P}$ , conditionally tight, BMM reduction (Satta 1994)
$k=1$ CSG	$O(2^{n^{2}})$ in time, $O(n^{2})$ in space (Savitch 1970)	PSPACE-complete (Kuroda 1964; Savitch 1970; Stockmeyer & Meyer 1973)
$k=0$ RE	not applicable	undecidable (Turing 1936)

Table 3: Membership-decision bounds by class of the Chomsky hierarchy.

Panel of Figure 3 — Figure 3: Semi-logarithmic scale of the best known algorithmic bound for the membership decision, class by class of the Chomsky hierarchy. The polynomial bounds for $k=3$ ( $\Theta(n)$ , green), $k=2$ ( $O(n^{2.37})$ , yellow) and $k=2^{+}$ ( $O(n^{6})$ , orange) appear as straight lines of increasing slope; the slope is 1, 2.37 and 6 respectively on the semi-log scale. The exponential bound $O(2^{n^{2}})$ for $k=1$ CSG (magenta) diverges from $n\approx 6$ beyond the represented scale. For $k=0$ RE, undecidability is not representable on the $n$ axis (complexity is not a function of input length); see the $k=0$ paragraph for the detailed discussion.

Class	Explicit enumeration	Compact representation	Characterization
$k=3$ Regular	$O(n)$	$O(n)$ (single tree)	tight, no structural ambiguity
$k=2$ CFG	$O(4^{n})$ (Catalan)	$O(n^{3})$ shared forest (Billot & Lang 1989)	tight (asymptotic Catalan)
$k=2^{+}$ TAG/MCFG	$O(4^{n})$ or worse	$O(n^{6})$ shared forest (Billot–Lang generalization)	conditional BMM + combinatorial explosion
$k=1$ CSG	$O(2^{n^{2}})$	n/a (same bound)	identical to the decision (PSPACE)
$k=0$ RE	undecidable / infinite	n/a	undecidable + potentially infinite number of trees

Table 4: Bounds for enumerating all trees, by class.

Panel of Figure 4 — Figure 4: Semi-logarithmic scale of the complexity of the explicit enumeration of all derivation trees, class by class. To be compared with Figure 3 (membership decision): for $k=3$ the curve is identical ( $O(n)$ , one tree per string), but from $k=2$ onward the bound $O(4^{n})$ (Catalan numbers, a line of slope $\log_{10}(4)\approx 0.602$ on the semi-log scale) diverges far faster than the $O(n^{2.37})$ bound of the decision — a concrete illustration of the “second dimension of difficulty” introduced by the combinatorial explosion of the set of trees to produce. For $k=1$ and $k=0$ , the bounds coincide with those of the membership decision (enumeration inherits, respectively, the exploration of the configuration space and the undecidability). The $O(4^{n})$ curve overtakes the CFG-decision curve ( $O(n^{2.37})$ ) as early as $n\approx 5$ , and reaches $10^{11}$ steps at $n=18$ already.

Class	Total cost	Characterization
$k=3$ Regular	$\Theta(n)$	tight, identical to the membership decision
$k=2$ CFG	$O(n)$ to $O(n^{2})$	in $\mathsf{P}$ , not tight
$k=2^{+}$ TAG/MCFG	$O(n^{2})$ to $O(n^{3})$	in $\mathsf{P}$ , not tight
$k=1$ CSG	$O(n^{3})$	in $\mathsf{P}$ , sharp contrast with PSPACE-completeness of the decision
$k=0$ RE	unbounded (semi-decidable)	undecidable in the strict sense

Table 5: Bounds for terminating example-generation, by class.

Panel of Figure 5 — Figure 5: Semi-logarithmic scale of the complexity of terminating example-generation, class by class. The bounds remain polynomial for all monotonic classes ( $k=3$ to $k=1$ ), with moderate growth — slope 1 for regular, slope 2 for CFGs, slope 3 for TAG/MCFG and CSG. To be compared with Figure 3 (membership decision): generation is strictly faster than the decision for $k=2^{+}$ and $k=1$ , and the gap becomes qualitative for $k=1$ (polynomial vs PSPACE-complete). For $k=0$ , the derivation may fail to terminate; this case is not representable on the $n$ axis (see legend).

Class	Bound	Pivot source
$k=3$ Regular	$\Theta(n+\|Q_{G}\|\cdot\|Q_{C}\|)$	Mohri 1997
$k=2$ pure CFG (compositional semantics)	polynomial	folklore
$k=2$ CFG + features/unification	exponential ( $2^{k}$ modifiers)	Kay 1996, §4
$k=2$ CFG + multi-set input	NP-complete (proven)	Brew 1992, §2.1.3
$k=2^{+}$ TAG/MCFG + features	exponential (Kay + Brew inheritance)	Kay 1996, Brew 1992
$k=1$ CSG + features	NP-hard to PSPACE-hard	Barton 1987, Ch. 3

Table 6: Bounds for generation under semantic constraint, by class.

Panel of Figure 6 — Figure 6: Semi-logarithmic scale of the complexity of generation under semantic constraint, class by class and sub-case by sub-case. Polynomial bounds persist for regular and pure CFGs, but the introduction of feature structures or non-local constraints tips the complexity into exponential as early as $k=2$ ( $O(2^{n})$ NP-complete, proven by Brew 1992) or into NP-hard to PSPACE-hard at $k=1$ . To be compared with Figure 3 (membership decision): here generation exceeds the decision in complexity from $k=2$ onward with features, whereas in Figure 3 the decision remained polynomial up to $k=2^{+}$ . This is the visual manifestation of the sign reversal of the asymmetry under semantic constraint.

Class	Membership decision	Example-generation	Gap between the two
$k=3$	$\Theta(n)$	$O(n)$	none
$k=2$	$O(n^{3})$ to $O(n^{2.37})$	$O(n)$ to $O(n^{2})$	polynomial, from $n$ to $n^{0.37}$
$k=2^{+}$	$O(n^{6})$	$O(n^{2})$ to $O(n^{3})$	polynomial, from $n^{3}$ to $n^{4}$
$k=1$	$O(2^{n^{2}})$ (PSPACE-complete)	$O(n^{3})$	class separation ( $\mathsf{P}$ vs $\mathsf{PSPACE}$ )
$k=0$	undecidable	unbounded	decidability separation

Table 7: Comparison between the membership decision (recognition side) and terminating example-generation (generation side), by class.

Panel of Figure 7 — Figure 7: Complexity heatmaps for generation (top) and recognition (bottom). The rows represent the three sub-problems per side; the columns represent the five classes of the Chomsky hierarchy. The palette encodes the order of magnitude: green for linear bounds, yellow for cubic, orange for $O(n^{6})$ , red for exponential, dashed dark red for $O(4^{n})$ (Catalan numbers), magenta for $O(2^{n^{2}})$ , gray for undecidable or unbounded. The differential coupling is visually apparent: the generation matrix (top) varies mainly along the rows (sensitivity to the sub-problem: free $\to$ terminating $\to$ constrained), whereas the recognition matrix (bottom) varies mainly along the columns (sensitivity to the class), with the exception of the “all trees” row, which also becomes class-sensitive through combinatorial explosion from $k=2$ onward.

Strategy	Direction	Mechanism
LL (recursive descent)	Top-down	Predict nonterminal, match terminal
LR (shift-reduce)	Bottom-up	Shift terminals, reduce to nonterminals
Earley (1970)	Hybrid	Top-down prediction + bottom-up completion
CYK	Bottom-up	Dynamic programming on substrings
Left-corner ( Rosenkrantz and Lewis 67 )	Hybrid	Bottom-up initiation + top-down prediction

Table 16

Panel of Figure 8 — Figure 8: The three operations: a hierarchy of difficulty. Canonical case ( $k=2$ , simplest tasks). Full ranges: $\mathcal{O}(n)$ to $\notin\mathsf{R}$ — see §4.1.

Panel of Figure 9 — Figure 9: Surprisal asymmetry on the running example "I saw the man with the telescope." The generator (blue) experiences $S=0$ at every position. The parser (red) shows a surprisal spike at "with" — the PP-attachment ambiguity point. The shaded area represents the cumulative temporal asymmetry.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Dim	Name	Gen	Parse	Key ref	Counter-argument	Resolution
D1	Computational	$\mathcal{O}(n)$ to $\notin\mathsf{R}$	$\mathcal{O}(n)$ to $\notin\mathsf{R}$	Younger 1967, Valiant 1975, Satta 1994, Savitch 1970, Barton et al. 1987	Gen NP-hard under semantic constraint	Differential coupling: gen ← task spec., recog ← grammar class; asymmetry changes nature with $k$ (quantitative $k\in\{2,2^{+}\}$ , structural $k=1$ , maximal $k=0$ )
D2	Ambiguity	Function (single-valued)	Relation (multivalued), $C_{n}\sim 4^{n}$ ; inherently ambiguous langs.	Parikh 1966, Brabrand 2007	Deterministic langs. unambig.	DCFLs exclude natural langs.; inherent ambiguity is a theorem
D3	Directionality	Top-down (phrase-struct.)	Free choice (LL, LR, …)	Shieber 1988, 1990	L-systems, shape grammars	Scoped to phrase-struct.; others confirm asym.
D4	Information	$H(X\mid X)=0$	$H(X\mid Y)>0$	Shannon 1948	Bits-Back exploitable	Asymmetry = resource
D5	Inference	gen < recog < infer (canonical $k\!=\!2$ )	Knowledge continuum	Gold 1967	PCFG escapes Gold	Still “hard as RSA” ( Kearns and Valiant 43 )
D6	Temporality	Causal: $S=0$	Expectation-based: $S>0$	Hale 2001, Levy 2008	Stochastic gen $S>0$	Chosen vs. imposed uncertainty

Appendix

Table 19

Text Generation

Text generation studies methods for producing coherent, useful language from prompts, data, and dialogue context.

See all 422 papers

Sep 9, 2026

Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy

Language generation in the limit asks for valid unseen elements from every exhaustive positive presentation of an unknown infinite language. We characterize this task for arbitrary families over a countable universe. Generation is possible exactly when each target can be assigned a finite positive witness so that the targets activated by any finite sample have an infinite common intersection. The necessary direction follows from a universal normalization: a search through unconfirmed histories converts any successful generator into one depending only on the observed set. We then ask how large compatible witnesses must be. Positive separation width records the smallest uniform size bound, with two further levels for unbounded finite witnesses and the absence of any compatible finite-witness assignment. Every level occurs. Countable families admit singleton witnesses, explicit families realize every finite width, and a union of two families with infinite common cores requires unbounded finite witnesses. Finally, countable-support and finite-profile obstructions explain why local combinatorial data cannot determine generation in the limit. The characterization and full width hierarchy are checked in Lean, including the simplified normalization and a direct diagonal capture lemma. The accompanying Lean development is maintained at https://github.com/xiaoyulics/language-generation-characterization

Xiaoyu Li, Andi Han, Jiaojiao Jiang +1

University of New South Wales · University of Sydney

Inductive Inference

Ask PDF

May 11, 2026

A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse

We study language generation in the limit under a global preference ordering on strings, as introduced by Kleinberg and Wei. As is done in previous work, we aim for breadth, but impose an additional requirement of timeliness: higher-ranked strings should be generated earlier. A string is then only credited if it is generated before a deadline, where its deadline is defined by a function that maps a string's rank in the target language to the time by which it must be produced. This is in keeping with a central consideration in machine learning, where inductive bias favors simpler'' or more plausible'' outputs, all else being equal. We show that timely generation is impossible in a strong sense for eventually consistent generators -- the protagonists of most prior related work. Under what is perhaps the mildest natural relaxation of consistency, a hallucination rate that vanishes over time, we show that we can circumvent our impossibility result. In particular, we can achieve optimal density with respect to any superlinear deadline function. We also show this is tight by ruling out timely generation with linear deadlines and vanishing hallucination rate.

Atul Ganju, Travis McVoy, Shaddin Dughmi +1

University of Southern California

Hallucination in Language Models Language Modeling Text Generation

Ask PDF

Jul 25, 2026

Hallucination Rates in Language Generation

Language generation in the limit is an elegant model introduced by Kleinberg and Mullainathan [KM24] to formally study language generation by an algorithm that learns solely based on example strings. In this model, an algorithm is said to correctly generate from a language if it never makes an error after some finite time. In contrast, even sophisticated language models are known to regularly hallucinate in practice. In this paper, we initiate the study of language generation in the limit with (infinite) hallucination, i.e., the algorithm may generate incorrect strings infinitely often, but the errors occur at a limited rate (possibly even with 0-measure). We first show that hallucination, even at rate 0, makes generation in the limit strictly more powerful: there are language collections that cannot be generated with finite error but can be generated with infinite error, even when errors occur on a 0-measure set of time-steps. Furthermore, while all countable collections are generatable with finite error, we show a strict hierarchy of (uncountable) language collections characterized by the hallucination rate. This hierarchy extends to breadth, the fraction of the target language generated. While all countable collections can attain the optimal breadth of 1/2 [KW26b], we show strict separation at every breadth and hallucination rate. Finally, we study generation in the limit without repetition, where the algorithm may not repeat strings. This lets us compare the sets of correct and incorrect strings generated, rather than the fractions of correct and incorrect time-steps. Once again, we demonstrate a strict hierarchy at every hallucination rate and breadth. Taken together, these results reveal rich structure in language collections generatable in the limit with hallucination and establish hallucination rate as an important parameter in the theoretical study of language generation.

Debmalya Panigrahi, Fan Wei, Ian Zhang

Department of Computer Science, Duke University, 308 Research Drive, Durham, NC 27708, USA. · Department of Mathematics, Duke University, 120 Science Drive, Durham, NC 27710, USA. · Duke University.

Hallucination in Language Models Text Generation

Ask PDF

Abstract

Text Generation

Explore similar work

Characterizing Language Generation in the Limit: Finite Witnesses and a Separation-Width Hierarchy

A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse

Hallucination Rates in Language Generation