正则文法

3型语言
术语名称	3型语言
英语名称	type-3 language

3型文法
术语名称	3型文法
英语名称	type-3 grammar

正则文法(regular grammar)指一种形式语言的生成文法，要求每个符号生成其他符号时，每次或者生成一个终结符，或者生成一个非终结符和一个终结符。是 Chomsky 生成语法理论中的3 型文法(type-3 grammar)。

定义

若生成文法中，全部文法均有形式：

[math]\displaystyle{ A \rightarrow a }[/math] [math]\displaystyle{ A \rightarrow aB }[/math] [math]\displaystyle{ A \rightarrow \epsilon }[/math]

其中， [math]\displaystyle{ A,B }[/math] 为一个非终结符， [math]\displaystyle{ a }[/math] 为一个终结符， [math]\displaystyle{ \epsilon }[/math] 为空符号串，

则称该文法为一种右正则文法(right-regular grammar)。

若改为

[math]\displaystyle{ A \rightarrow a }[/math] [math]\displaystyle{ A \rightarrow Ba }[/math] [math]\displaystyle{ A \rightarrow \epsilon }[/math]

则称该文法为一种左正则文法(left-regular grammar)。

以上两种文法统称为正则文法(regular grammar)，由这种文法生成的语言称为正则语言(regular language)。

以上为形式化定义。通俗地说，正则无关文法的含义是，文法中每个非终结符一定可以被展开生成其他文法符号串，且这一展开时，或者减少一个可展开文法符号，或者只向符号串中增加一个不可展开的文法符号到左侧或右侧。

需要注意的是，正则文法不可以同时存在左右展开的规则，一种正则文法必须要么是全部规则都只生成非终结符到右侧的右正规文法，要么是全部规则都只生成非终结符到左侧的左正规文法。

每次展开都只依赖于非终结符本身，所以正则文法总是上下文无关文法。

正则文法的表达能力等价于正则表达式，及对应确定的有限自动机。