正規語言

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

1.L可以被一個確定有窮自動機識別；

2.L可以被一個非確定有窮自動機識別；

3.L可以用正則表達式表達；

4.L可以用正則文法生成；

5.L可以由前綴文法生成；

一、封閉性

1.正規語言的交、並、差、補運算得到的語言仍然是正則語言；

2.兩個正規語言連接（把第一個語言的所有字元串同第二個語言的所有字元串連接起來）后得到的語言仍然是正規語言；

3.正規語言閉包運算后得到的語言仍然是正規語言；

4.正規語言的每個字元串轉置后得到的語言仍然是正規語言；

5.正規語言被任意語言的字元串商（左商或右商)后得到的語言仍然是正規語言；

6.正規語言字元串代換后得到的語言仍然是正規語言；

7.與正規語言字元串同態或逆同態的語言仍然是正規語言；

二、判定準則

1.判定一個語言不是正則語言通常使用泵引理，或者其加強形式；

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

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