正則文法
正則文法
正則文法：又稱為3型文法，是一種形式語言。這種文法分為兩種類型：第一類要求生成式的形式必須是A→ωB或A→ω，其中A，B都是變元，ω是終結符串，這種特殊的正則文法稱為右線性文法。第二類正則文法稱為左線性文法，它要求生成式必須是A→Bω，或A→ω的形式。由正則文法生成的語言稱為正則語言，它恰是有窮自動機所識別的語言類。
在計算機科學中，正則文法是產生式規則取下述形式的一種形式文法（ N, Σ, P, S）：
A->a，此處的A是N中的非終結符號，a是Σ中的終結符號；
A->aB，此處的A和B是N中的非終結符號，a是Σ中的終結符號；
C-> ε，此處的C是N中的非終結符號。
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* 來表達。
正則文法描述的語言構成了正則語言類，正則語言類中的語言也可以由有限狀態自動機或正則表達式來表達。
正則語言又稱 正規語言是滿足下述相互等價的一組條件的一類形式語言：
• 可以被確定有限狀態自動機識別；
• 可以被非確定有限狀態自動機識別；
• 可以被只讀圖靈機識別；
• 可以用正則表達式描述；
• 可以用正則文法生成。
• 可以用前綴文法生成。
這裡語言的運算參見條目形式語言。
• 正則語言的交、並、差、補運算得到的語言仍然是正則語言；
• 兩個正則語言連接（把第一個語言的所有字元串同第二個語言的所有字元串連接起來）后得到的語言仍然是正則語言；
• 正則語言閉包運算后得到的語言仍然是正則語言；
• 正則語言的每個字元串轉置后得到的語言仍然是正則語言；
• 正則語言被任意語言的字元串商（左商或右商）后得到的語言仍然是正則語言。
• 正則語言字元串代換后得到的語言仍然是正則語言。
• 與正則語言字元串同態或逆同態的語言仍然是正則語言。