正規語言

正規語言又稱正則語言，是形式語言與自動機理論中討論的最基本的語言系。通過它可以架起有窮自動機和正則表達式之間的一座橋樑。

基本介紹

• 中文名：正規語言
• 外文名：Formal language

正規語言的定義

設∑為有窮字母表，∑*為其Kleene閉包（見作用代數）。那么稱字元串集L∈∑*為正規語言，若且唯若滿足下列條件之一：

1. L可以被一個確定有窮自動機識別；
   
2. L可以被一個非確定有窮自動機識別；
   
3. L可以用正則表達式表達；
   
4. L可以用正則文法生成；
   
5. L可以由前綴文法生成；
   

正規語言的性質

一、封閉性

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

二、判定準則

1. 判定一個語言不是正則語言通常使用泵引理，或者其加強形式；
   
2. 要判斷一個語言是正則語言，一般方法是構造一個識別該語言的有窮自動機或正則表達式。也可以通過邁希爾－尼羅德定理所確定的充要條件來證明；
   

正則語言的套用

由於正則語言可以用有窮自動機識別，所以在進行字元串匹配時可以設計一個無回溯的分析程式。這樣就可以使得字元串匹配可以在O(n)時間內完成，而且很容易編程實現。（正則語言在字元串匹配中的套用可以參見詞條：正則表達式）