arXiv:2603.10139cs.CLcs.AI2026-03被引 1

揭示语言生成与识别在六个维度上的根本差异,挑战‘生成易、解析难’的常见误解。

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

  • 从计算复杂度、歧义性等六方面系统分析生成与识别的操作不对称性
  • 指出约束生成可能为NP难问题,而解析始终受输入约束,本质更复杂
  • 关联心理语言学中的预期意外(surprisal)理论,解释时间维度上的差异

每个形式文法定义一种语言,可应用于三种方式:生成字符串(产生)、识别字符串(解析),或仅通过样例推断文法本身(文法归纳)。生成与识别在扩展意义上等价,但操作上存在多重独立的不对称性。归纳是质性更难的问题,因缺乏已知文法。尽管这三者对编译器设计、自然语言处理和形式语言理论至关重要,但尚无综述将其视为统一的多维现象。本文识别出六个生成与识别之间的差异维度:计算复杂度、歧义性、方向性、信息可得性、文法归纳、时间性。研究表明,‘生成容易,解析困难’的常见说法具有误导性:无约束生成虽简单,但在约束条件下可能为NP难。真正的不对称在于解析始终受输入约束,而生成未必如此。其中方向性和时间性两个维度此前未被明确识别。本文将时间维度与Hale(2001)和Levy(2008)的预期意外框架相联系,认为预期意外形式化了生成器(预期意外=0)与在不确定性下预测的解析器(预期意外>0)之间的时序不对称。回顾自然语言处理中的双向系统,指出双向性已存在五十年,却未广泛应用于多数特定领域。最后讨论大语言模型,其架构上统一了生成与识别,但操作上仍保留不对称性。

原文摘要 · Abstract (English)

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.

形式语言生成模型认知科学语言模型

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。