【计算理论】正则语言 ( 正则表达式原子定义 | 正则表达式递归定义 | 正则表达式语言原子定义 | 正则表达式语言结构归纳 | 正则表达式语言示例 | 根据正则表达式构造自动机 )
文章目錄
- 一、正則表達式 定義
- 二、 正則表達式語言 原子定義
- 三、正則表達式語言 結構歸納定義
- 四、正則表達式語言 示例
- 五、空集 ?\varnothing? 與 空字符 ε\varepsilonε 差別
- 六、正則表達式 定理
- 七、根據 正則表達式 語言 構造 自動機 ( 定理正向證明 )
- 八、構造原子自動機
- 九、使用 原子自動機 拼裝 正則表達式對應的自動機
一、正則表達式 定義
1 . 正則表達式原子定義 :
如果 RRR 是
- 字符集 Σ\SigmaΣ 中的 111 個字符 ,
- 空字符串 ε\varepsilonε , 或
- 空集 {?}\{ \varnothing \}{?} ,
那么稱 RRR 是正則表達式 ;
2 . 正則表達式遞歸定義 :
如果 R1,R2R_1 , R_2R1?,R2? 是正則表達式 , 那么
- R1∪R2R_1 \cup R_2R1?∪R2? 是正則表達式 ;
- R1°R2R_1 \circ R_2R1?°R2? 是正則表達式 ;
- R1?R_1^*R1?? 是正則表達式 ;
上述是正則表達式的定義 , 這是一個結構歸納定義 ;
二、 正則表達式語言 原子定義
正則表達式語言表示方式 : RRR 是正則表達式 , L(R)L(R)L(R) 是正則表達式代表的語言 ;
1 . 單個字符代表的語言 :
L(a)={a}L(a) = \{a\}L(a)={a}
aaa 是字符集中的字符 , 那么其所代表的的語言是 {a}\{a\}{a} 單元集 , 是由一個元素的字符構成的 ;
2 . 空字符串代表的語言 :
L(ε)={ε}L(\varepsilon) = \{ \varepsilon \}L(ε)={ε}
如果 ε\varepsilonε 是正則表達式 , 其所代表的的語言 L(ε)L(\varepsilon)L(ε) , 是由空字符串組成的集合 {ε}\{ \varepsilon \}{ε} ;
3 . 空集代表的語言 :
L(?)=?L(\varnothing) = \varnothingL(?)=?
空集 ?\varnothing? 所代表的的語言 , 就是空集 ;
三、正則表達式語言 結構歸納定義
1 . 正則表達式并集 的 語言 :
L(R1∪R2)=L(R1)∪L(R2)L(R_1 \cup R_2) = L(R_1) \cup L(R_2)L(R1?∪R2?)=L(R1?)∪L(R2?)
R1,R2R_1 , R_2R1?,R2? 是兩個正則表達式 , 其并集的語言 , 就是其 兩個語言的并集 ;
2 . 正則表達式串聯 的 語言 :
L(R1°R2)=L(R1)°L(R2)L(R_1 \circ R_2) = L(R_1) \circ L(R_2)L(R1?°R2?)=L(R1?)°L(R2?)
R1,R2R_1 , R_2R1?,R2? 是兩個正則表達式 , 其串聯運算結果正則表達式的語言 , 就是其 兩個正則表達式語言的 串聯運算結果 ;
3 . 正則表達式星運算 的 語言 :
L(R?)=(L(R))?L(R^*) = ( L(R) ) ^*L(R?)=(L(R))?
RRR 正則表達式 星運算 結果 正則表達式 的語言 , 就是 RRR 正則表達式的語言 進行 星運算的結果 ;
四、正則表達式語言 示例
字符集 : Σ={0,1}\Sigma = \{0, 1\}Σ={0,1} ;
正則表達式 : (0∪1)?10(0∪1)?( 0 \cup 1 )^* 1 0 ( 0 \cup 1 )^*(0∪1)?10(0∪1)? ;
正則表達式轉化成語言 :
L((0∪1)?10(0∪1)?)=L((0∪1)?)°L(1)°L(0)°L((0∪1)?)={0,1}?°{1}°{0}°{0,1}?\begin{array}{lcl} && L( ( 0 \cup 1 )^* 1 0 ( 0 \cup 1 )^* ) \\\\ &=& L( ( 0 \cup 1 )^* ) \circ L(1) \circ L(0) \circ L( ( 0 \cup 1 )^* ) \\\\ &=& \{0,1\}^* \circ \{ 1 \} \circ \{ 0 \} \circ \{ 0, 1 \}^* \end{array}?==?L((0∪1)?10(0∪1)?)L((0∪1)?)°L(1)°L(0)°L((0∪1)?){0,1}?°{1}°{0}°{0,1}??
上述 {0,1}?\{0,1\}^*{0,1}? 就是 0,10,10,1 有限個字符串組成的字符 ;
正則表達式表示的語言 , 剛好是自動機所識別的語言 ; 可以根據該語言將自動機設計出來 ;
五、空集 ?\varnothing? 與 空字符 ε\varepsilonε 差別
空集 ?\varnothing? 是正則表達式 , 類似于數中的 000 ;
空字符 ε\varepsilonε 是正則表達式 , 類似于數中的 111 ;
( 后續待補充 )
六、正則表達式 定理
1 . 定理 : 一個語言如果是正則語言 , 當且僅當 , 該語言可以通過正則表達式表示出來 ;
2 . 有以下兩層含義 :
-
① 正則表達式 -> 自動機識別 :正則表達式 表達出的語言 剛好 能夠被自動機識別 ;
-
② 自動機識別 -> 正則表達式 : 自動機識別某個語言 , 那么該語言可以被正則表達式表達出來 ;
3 . 定理證明 :
① 正則表達式 -> 自動機識別 證明 : 給定一個正則表達式 , 設計一個自動機 , 該自動機所 接受 ( 識別 / 認識 ) 的語言 , 剛好是該正則表達式所表達的語言 ;
下面的 " 根據 正則表達式 語言 構造 自動機 " 小節的示例 , 證明了正則表達式語言必有自動機識別 ;
② 自動機識別 -> 正則表達式 證明 : 給定一個自動機 , 找到其所識別的 正則表達式語言 ;
七、根據 正則表達式 語言 構造 自動機 ( 定理正向證明 )
1 . 需求 : 根據下面的 正則表達式 構造 非確定性有限自動機 ( NFA ) , 剛好能 識別上述正則表達式表示的語言 ;
(ab∪a)?( ab \cup a )^*(ab∪a)?
構造能識別 (ab∪a)?( ab \cup a )^*(ab∪a)? 語言 的 自動機 ;
八、構造原子自動機
構造原子自動機 : 先構造能接收 單個字符 的自動機 ;
① 接收 aaa 字符的自動機 : 下面的自動機是可以識別 aaa 字符串的 ;
② 接收 bbb 字符的自動機 : 下面的自動機是識別 bbb 字符串的 ;
九、使用 原子自動機 拼裝 正則表達式對應的自動機
拼裝上述識別單個字符的 自動機 :
1 . 擺放自動機位置 : 將 222 個能識別 aaa 字符串的自動機 , 與 111 個能識別 bbb 字符串的自動機 , 按照如下排列放置 ;
2 . ababab 對應自動機構造 :
① 自動機連接方式 : aaa 正則表達式語言 自動機 與 bbb 正則表達式語言 自動機 是串聯在一起的 ;
② 串聯兩個自動機的狀態 : 使用 ε\varepsilonε 箭頭 , 串聯 aaa 對應自動機的接受狀態 -> bbb 對應自動機的開始狀態 ;
③ 修改 前者 的狀態 : 同時將 aaa 對應自動機的接受狀態 改為非接受狀態 ;
下面是 ababab 正則表達式 表達的語言 對應的自動機表示 :
3 . ab∪aab \cup aab∪a 對應自動機構造 :
① 添加新開始狀態 : 重新添加一個開始狀態 ;
② 連接并運算前者 : 使用 ε\varepsilonε 箭頭 從這個新添加的開始狀態 指向 ababab 自動機開始狀態 ;
③ 連接并運算后者 : 使用 ε\varepsilonε 箭頭 從這個新添加的開始狀態 指向 aaa 自動機開始狀態 ;
下面是 ab∪aab \cup aab∪a 正則表達式 表達的語言 對應的自動機表示 :
4 . (ab∪a)?( ab \cup a )^*(ab∪a)? 對應自動機構造 :
① 構造方法 : 就是 在 (ab∪a)( ab \cup a )(ab∪a) 對應自動機的基礎上 , 使用 ε\varepsilonε 箭頭 , 從 接受狀態 指向 開始狀態 ;
② 連接個數 : 所有的接受狀態 , 都 使用 ε\varepsilonε 箭頭 指向開始狀態 , 這里有兩個接受狀態 , 需要都指向開始狀態 ;
總結
以上是生活随笔為你收集整理的【计算理论】正则语言 ( 正则表达式原子定义 | 正则表达式递归定义 | 正则表达式语言原子定义 | 正则表达式语言结构归纳 | 正则表达式语言示例 | 根据正则表达式构造自动机 )的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 【计算理论】非确定性有限自动机 ( 计算
- 下一篇: 【计算理论】正则语言 ( 推广型的非确定