正則語言

正則語言又稱正規語言是滿足下述相互等價的一組條件的一類形式語言：

• 可被確定有限狀態自動機辨識；
• 可被非確定有限狀態自動機辨識；
• 可被唯讀圖靈機辨識；
• 可用正則表達式描述；
• 可用正則文法生成。
• 可用字首文法生成。

例子

• 所有的有限語言都是正則的。
• 字母表{a, b}上包含偶數個a的所有字串構成的語言是正則的。
• 字母表{a, b}上取若干個a後緊跟若干個b形式的所有字串構成的語言是正則的。

定義

在字母表集合Σ上的正則語言定義如下：

• 空集合Ø是正則語言
• 只包含一個空字串的語言{ε}是正則語言
• 對所有$a\in \Sigma$，{a}是正則語言
• 若A, B是正則語言，則$A\cdot B,A\bigcup B,A^{*}$(kleene星號)都是正則語言
• 除此之外都不是正則語言

如果一個語言不是正則語言，它需要一個記憶體至少是Ω(log log n)的自動機才能辨認。換句話說，DSPACE(o(log log n))等於所有正則語言的集合。實際上，大部份的非正則語言需要至少O(log n)的空間。

封閉性質

這裏語言的運算參見條目形式語言。

• 正則語言的交、並、差、補運算得到的語言仍然是正則語言；
• 兩個正則語言連接（把第一個語言的所有字串同第二個語言的所有字串連接起來）後得到的語言仍然是正則語言；
• 正則語言閉包運算後得到的語言仍然是正則語言；
• 正則語言的每個字串轉置後得到的語言仍然是正則語言；
• 正則語言被任意語言的字串商（左商或右商）後得到的語言仍然是正則語言。
• 正則語言字串代換後得到的語言仍然是正則語言。
• 與正則語言字串同態或逆同態的語言仍然是正則語言。

純代數定義

正則語言也可以以純粹代數的方式來定義。

Σ是一個有窮的字母表，Σ*是Σ上的自由么半群，Σ*構成了Σ上的所有字串。令M為一個有限么半群，對映f : Σ* -> M為一個么半群同態，集合S是M的一個子集，於是S的逆同態象f ^-1(S)是正規的。每一個正規語言都可以依這種方式來定義。

另外一種定義方式藉助於一個等價關係。

取L為Σ*的任意子集，定義如下的Σ*上的等價關係~ (叫做「語法關係」)： u ~ v，即對Σ*中所有的的字串w有uw在L中若且唯若vw在L中。於是對正規語言有下面的結論：語言L是正規的若且唯若關係~的等價類的數量是有限的（其證明在條目語法么半群中）。在此情況下，等價類的數量就是接受語言L的最小確定有限狀態自動機的狀態數。

相關條目

• 形式語言
• 有限狀態自動機
• 正則表達式
• 正則文法
• 喬姆斯基體系

參照

• 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.

外部連結

• Department of Computer Science at the University of Western Ontario: Grail+, https://web.archive.org/web/20060404094049/http://www.csd.uwo.ca/Research/grail/. A software package to manipulate regular expressions, finite-state machines and finite languages. Free for non-commercial use.

• Chalchalero! http://www.ucse.edu.ar/fma/sepa/chalchalero.htm （頁面存檔備份，存於互聯網檔案館）. A free visual software to manipulate regular expressions, regular grammars, finite-state machines and finite languages developed by the SEPa! Project Team (Universidad Católica de Santiago del Estero).

• REG at Complexity Zoo

• https://web.archive.org/web/20060404094049/http://www.csd.uwo.ca/Research/grail/ ：西安大略大學電腦科學系Grail+， 一個可以操作正則表達式、有限狀態自動機和有限語言的自由軟件套件。