查看“︁正则文法”︁的源代码

[[分类:形式语言]]
{{InfoBox
|name=正则语言
|eng_name=regular language
|aliases=正规语言
}}
{{InfoBox
|name=正则文法
|eng_name=regular grammar
|aliases=正规文法
}}
{{InfoBox
|name=3型语言
|eng_name=type-3 language
}}
{{InfoBox
|name=3型文法
|eng_name=type-3 grammar
}}
'''正则文法'''('''regular grammar''')指一种[[形式语言]]的[[生成文法]]，要求每个符号生成其他符号时，每次或者生成一个终结符，或者生成一个非终结符和一个终结符。是 [[Chomsky 生成语法理论]]中的'''3 型文法'''('''type-3 grammar''')。

== 定义 ==

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

<math>A \rightarrow a</math>
<math>A \rightarrow aB</math>
<math>A \rightarrow \epsilon</math>

其中， <math>A,B</math> 为一个非终结符， <math>a</math> 为一个终结符， <math>\epsilon</math> 为空符号串，

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

若改为

<math>A \rightarrow a</math>
<math>A \rightarrow Ba</math>
<math>A \rightarrow \epsilon</math>

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

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

=== 说明 ===

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

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

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

== 自动机等价 ==

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