Left-Linear Grammar

释义 Definition

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

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

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

发音 Pronunciation (IPA)

/ˌlɛftˈlɪniər ˈɡræmər/

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

文献与著作 Notable Works