正則文法

正則文法：又稱為3型文法。這種文法分為兩種類型：第一類要求生成式的形式必須是A→ωB或A→ω，其中A，B都是變元，ω是終結符串，這種特殊的正則文法稱為右線性文法。第二類正則文法稱為左線性文法，它要求生成式必須是A→Bω，或A→ω的形式。由正則文法生成的語言稱為正則語言，它恰是有窮自動機所識別的語言類。

基本介紹

• 中文名：正則文法
• 外文名：Regular grammar
• 別名：3型文法
• 類型：A→ωB或A→ω

基本概念

正則文法：又稱為3型文法。這種文法分為兩種類型：第一類要求生成式的形式必須是A→ωB或A→ω，其中A，B都是變元，ω是終結符串（可以是空串），這種特殊的正則文法稱為右線性文法。第二類正則文法稱為左線性文法，它要求生成式必須是A→Bω，或A→ω的形式。由正則文法生成的語言稱為正則語言，它恰是有窮自動機所識別的語言類。

定義

在計算機科學中，正則文法是產生式規則取下述形式的一種形式文法（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* 來表達。

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

正則語言

正則語言又稱正規語言是滿足下述相互等價的一組條件的一類形式語言：

• 可以被確定有限狀態自動機識別；
• 可以被非確定有限狀態自動機識別；
• 可以被唯讀圖靈機識別；
• 可以用正則表達式描述；
• 可以用正則文法生成。
• 可以用前綴文法生成。

封閉性質

這裡語言的運算參見條目形式語言。

• 正則語言的交、並、差、補運算得到的語言仍然是正則語言；
• 兩個正則語言連線（把第一個語言的所有字元串同第二個語言的所有字元串連線起來）後得到的語言仍然是正則語言；
• 正則語言閉包運算後得到的語言仍然是正則語言；
• 正則語言的每個字元串轉置後得到的語言仍然是正則語言；
• 正則語言被任意語言的字元串商（左商或右商）後得到的語言仍然是正則語言。
• 正則語言字元串代換後得到的語言仍然是正則語言。
• 與正則語言字元串同態或逆同態的語言仍然是正則語言。