Left-Linear Grammar

释义 Definition

左线性文法：形式语言与自动机理论中的一种文法类型，通常指一种线性文法，其产生式右部至多含有一个非终结符，且该非终结符若出现，必须在最左端。常见形式如：

\(A \rightarrow B\alpha\)（\(B\) 为非终结符，\(\alpha\) 为终结符串）
\(A \rightarrow \alpha\)（仅终结符串或空串，视定义而定）

它与右线性文法（right-linear grammar）相对；两者都与正则语言（regular languages）密切相关（在常见约束下可生成正则语言）。

发音 Pronunciation (IPA)

/lftlnir rmr/

例句 Examples

A left-linear grammar can generate some regular languages.
左线性文法可以生成某些正则语言。

In many textbooks, left-linear grammar is introduced alongside right-linear grammar to show how linear productions relate to finite automata.
在许多教材中，左线性文法会与右线性文法一起介绍，用来说明线性产生式如何与有限自动机对应。

词源 Etymology

left-inear 由 left（左）+ linear（线性的）构成，强调“唯一的非终结符出现在右部的最左侧”；grammar（文法）来自拉丁语 grammatica，指语言规则体系。合起来就是“非终结符位置受限为左侧的线性文法”。

文献与著作 Notable Works

Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages, and Computation（常在讲解正则语言/线性文法时提及左/右线性文法）
Sipser: Introduction to the Theory of Computation（涉及正则语言、文法与自动机的对应关系）
Kozen: Automata and Computability（讨论文法形式与可计算模型的关系）
Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools（“龙书”，在形式语言与文法背景章节中可能涉及相关概念）