正則文法

在計算機科學中，正則文法是產生式規則取下述形式的一種形式文法（N, Σ, P, S）：

1. A -> a ，此處的A是N中的非終結符號，a是Σ中的終結符號；
2. A -> aB，此處的A和B是N中的非終結符號，a是Σ中的終結符號；
3. C -> ε，此處的C是N中的非終結符號。

下面給出一個正則文法的例子： 文法G = (N, Σ, P, S)，其中N = {S, A}，Σ = {a, b, c}，S是起始符號，P包含下述規則：

S -> aS

S -> bA

A -> ε

A -> cA

這個文法描述的語言也可以用正則表達式a*bc* 來表達。

正則文法描述的語言構成了正則語言類，正則語言類中的語言也可以由有限狀態自動機或正則表達式來表達。

相關條目

• 喬姆斯基譜系
• 正則語言
• 正則表達式
• 有限狀態自動機