正則語言

形式語言理論中最簡單的語言類，是上下文無關語言類的一個真子類，在喬姆斯基語言分層中處於最低層。又稱 3型語言。正則語言有兩種描述方法：①文法描述；②正則表達式與接受器。正則語言已應用於計算機程序語言編譯的詞法分析、開關電路設計等方面。

文法描述：正則語言由正則文法（或稱右線性文法，見形式語言理論）所生成。當限制產生式形式為A→Bt或A→t時,文法為左線性文法（其中A,B是非終結符,t是終結符）。每一右線性文法必有與之等價的左線性文法存在，即這兩種文法生成相同的語言。 ^[1] 

正則表達式與接受器：正則語言是正則集，可以用稱為正則表達式的簡單式子來表示。對任意一個給定的正則表達式可以構造出有限自動機來接收它，反過來，從任意有限自動機可以找出它所接受的正則表達式。

正則表達式：正則表達式描述的語言是正則集。令∑是一個有限集，遞歸地定義如下：

①φ、ε、ɑ(

∑)是∑上的正則表達式,它們所表示的字集分別為空集，{ε}、{ɑ}都是正則集。

②若 α、β是∑上的正則表達式，則α∪β、α·β、α*也是∑上的正則表達式，它們所表示的字集{α}、{β}、{α} ∪{β}、{α}{β}、{α*}是相應的正則集(運算符∪、·、*分別為並、連接、乘冪閉包。式子裏連接符·可以略去不寫，運算的優先順序為：*，·，∪)。

③只有有限次使用①、②確定出的表達式才是∑上的正則表達式，只有這些正則表達式所表示的字集才是∑ 上的正則集。正則集就是正則語言。

正則語言的性質:泵引理(pumping lemma):若R是正則語言，則存在正整數p,對R中所有字長不小於p的字符串s，s = xyz並且滿足以下性質：

①對所有

②

③

這個引理是證明某些語言非正則的有力工具，而且有助於建立算法，以便判斷一個給定的有限自動機所接受的語言是有限還是無限的。

對語言運算的封閉性：封閉的意思是將語言運算用到正則集上，其結果仍然是正則集。這對判別某些語言的正則性是有作用的。正則語言類是對並、連接、乘冪閉包運算封閉的最小語言類，並且對於交、補、逆、商、替換、逆同態等運算也封閉。

M. A. Arbib,Theories of Abstract Automata,PrenticeHall, Englewood Cliffs, N. J., 1969

Michael Sipser-Introduction to the Theory of Computation-Course Technology (2012)