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

ArXi:2603.10139v1 Announce Type: cross 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.