正規語言
 | 此條目可參照外語維基百科相應條目來擴充。 |
正規語言又稱正則語言是滿足下述相互等價的一組條件的一類形式語言：
例子
- 所有的有限語言都是正則的。
- 字母表{a, b}上包含偶數個a的所有字串構成的語言是正則的。
- 字母表{a, b}上取若干個a後緊跟若干個b形式的所有字串構成的語言是正則的。
定義
在字母表集合Σ上的正規語言定義如下：
- 空集合Ø是正規語言
- 只包含一個空字串的語言{ε}是正規語言
- 對所有，{a}是正規語言
- 若A, B是正規語言，則(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).
- https://web.archive.org/web/20060404094049/http://www.csd.uwo.ca/Research/grail/ ：西安大略大學電腦科學系Grail+， 一個可以操作正規表示式、有限狀態自動機和有限語言的自由軟體套件。