正則語言

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

例子

  • 所有的有限語言都是正則的。
  • 字母表{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為一個么半群同態,集合SM的一個子集,於是S的逆同態象f -1(S)是正規的。每一個正規語言都可以依這種方式來定義。

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

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

相關條目

參照


外部連結