-
正則文法
鎖定
- 中文名
- 正則文法
- 外文名
- Regular grammar
- 別 名
- 3型文法
- 類 型
- A→ωB或A→ω
正則文法基本概念
正則文法：又稱為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中的非終結符號。
下面給出一個正則文法的例子： 文法G= (N, Σ,P,S)，其中N= {S, A}，Σ = {a, b, c}，S是起始符號，P包含下述規則：
- S -> aS
- S -> bA
- A -> ε
- A -> cA
這個文法描述的語言也可以用正則表達式a*bc* 來表達。
正則文法正則語言
正則語言又稱正規語言是滿足下述相互等價的一組條件的一類形式語言：
正則文法封閉性質
這裏語言的運算參見條目形式語言。
- 正則語言的交、並、差、補運算得到的語言仍然是正則語言；
- 兩個正則語言連接（把第一個語言的所有字符串同第二個語言的所有字符串連接起來）後得到的語言仍然是正則語言；
- 正則語言閉包運算後得到的語言仍然是正則語言；
- 正則語言的每個字符串轉置後得到的語言仍然是正則語言；
- 正則語言被任意語言的字符串商（左商或右商）後得到的語言仍然是正則語言。
- 正則語言字符串代換後得到的語言仍然是正則語言。
- 與正則語言字符串同態或逆同態的語言仍然是正則語言。
- 參考資料
-
- 1. 陳火旺．編譯原理（第三版）．北京市海定區紫竹院南路23號：國防工業出版社，2010年2月：47-49
- 2. Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 978-0-534-94728-6. Chapter 1: Regular Languages, pp.31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp.152–155.
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：11次歷史版本
- 最近更新： 米嘛里哄123