複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/正規語言/7062658
複製
複製成功

正規語言

鎖定
正規語言又稱正則語言，是形式語言與自動機理論中討論的最基本的語言系，可以架起有窮自動機和正則表達式之間的橋樑。
中文名
正規語言
外文名
Formal language
別    稱
正則語言
所屬領域
語言學

目錄

  1. 1 正規語言的定義
  2. 2 正規語言的性質
  3. 3 正則語言的應用

正規語言正規語言的定義

設∑為有窮字母表，∑*為其Kleene閉包（見作用代數）。那麼稱字符串集L∈∑*為正規語言，當且僅當滿足下列條件之一：
  1. L可以被一個確定有窮自動機識別；
  2. L可以被一個非確定有窮自動機識別；
  3. L可以用正則表達式表達；
  4. L可以用正則文法生成；
  5. L可以由前綴文法生成；

正規語言正規語言的性質

一、封閉性
  2. 正規語言的交、並、差、補運算得到的語言仍然是正則語言；
  3. 兩個正規語言連接（把第一個語言的所有字符串同第二個語言的所有字符串連接起來）後得到的語言仍然是正規語言；
  4. 正規語言閉包運算後得到的語言仍然是正規語言；
  5. 正規語言的每個字符串轉置後得到的語言仍然是正規語言；
  6. 正規語言被任意語言的字符串商（左商或右商）後得到的語言仍然是正規語言；
  7. 正規語言字符串代換後得到的語言仍然是正規語言；
  8. 與正規語言字符串同態或逆同態的語言仍然是正規語言；
二、判定準則
  2. 判定一個語言不是正則語言通常使用泵引理，或者其加強形式；
  3. 要判斷一個語言是正則語言，一般方法是構造一個識別該語言的有窮自動機或正則表達式。也可以通過邁希爾－尼羅德定理所確定的充要條件來證明；

正規語言正則語言的應用

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