形式語言與自動機(jī)-6-正則表達(dá)式

8/13/20243:15PM/1第六章正則表達(dá)式6.1引例6.2正則表達(dá)式的形式定義6.2.1形式定義6.2.2例題 6.3正則表達(dá)式與有窮自動機(jī)的等價性6.3.1充分性證明6.3.2必要性的證明(1)首先說明如何把DFA轉(zhuǎn)換成GNFA(2)說明如何把GNFA轉(zhuǎn)換成正則表達(dá)式8/13/20243:15PM/2例題1：：

算術(shù)表達(dá)式：(5+4)×2,值為18，是一個數(shù)字

正則表達(dá)式：(0∪1)0*,正則表達(dá)式的值是一個語言注意：(0∪1)0*表示的是01后加任意多個0構(gòu)成的字符串所組成的語言0和1是集合{0}和{1}的縮寫，就是{0}∪{1},這部分的值是語言{0,1}0*就是{0}*,其值為所有包含任意個0的字符串構(gòu)成的語言在正則表達(dá)式中省略了連結(jié)運算符號o,(0∪1)0*實際上是(0∪1)o0*正則表達(dá)式可以用來描述滿足“某種模式”的字符串。8/13/20243:15PM/3

很多應(yīng)用程序及現(xiàn)代程序設(shè)計語言、文本編輯程序都提供用正則表達(dá)式描述模式的手段。例題2：正則表達(dá)式(0∪1)*其值為：由0和1的所有字符串組成的語言，也表示為{0,1}*表示方法：記∑為字母表，∑也可以表示該字母表中所有長度為1的字符串，而∑*為由該字母表中所有字符串組成的語言。如：(0∑*)∪(∑*1)表示所有以0開頭而以1結(jié)尾的字符串正則運算的優(yōu)先級：先星號，后連結(jié)，最后并，要改變這種慣常的順序需要用括號。8/13/20243:15PM/4第六章正則表達(dá)式6.1引例6.2正則表達(dá)式的形式定義6.2.1形式定義6.2.2例題 6.3正則表達(dá)式與有窮自動機(jī)的等價性6.3.1充分性證明6.3.2必要性的證明(1)首先說明如何把DFA轉(zhuǎn)換成GNFA(2)說明如何把GNFA轉(zhuǎn)換成正則表達(dá)式8/13/20243:15PM/5定義稱R是一個正則表達(dá)式，如果R是a,這里a是字母表∑中的一個元素；ε；φ；(R1∪R2)，這里R1和R2是正則表達(dá)式；(R1oR2)，這里R1和R2是正則表達(dá)式；(R1*)，這里R1是正則表達(dá)式；8/13/20243:15PM/6說明：在(1)和(2)中，a和ε分別表示{a}和{ε}在(3)條中，φ表示空語言在第(4)、(5)、(6)表示通過正則運算并、連結(jié)和星號獲得正則表達(dá)式（用較小的正則表達(dá)式定義較大的正則表達(dá)式，是歸納定義中的歸納步驟）此處ε和φ的區(qū)別：有一個空語句的語言，和空語言要想明顯的區(qū)分正則表達(dá)式R和它所表示的語言時，后者用L(R)表示。8/13/20243:15PM/7第六章正則表達(dá)式6.1引例6.2正則表達(dá)式的形式定義6.2.1形式定義6.2.2例題

6.3正則表達(dá)式與有窮自動機(jī)的等價性6.3.1充分性證明6.3.2必要性的證明(1)首先說明如何把DFA轉(zhuǎn)換成GNFA(2)說明如何把GNFA轉(zhuǎn)換成正則表達(dá)式8/13/20243:15PM/8例題3：在下面的句子中，字母表為{0,1}0*10*{ω|ω恰好有一個1}∑*1∑*{ω|ω至少有一個1}∑*001∑*{ω|ω中含有子串001}(∑∑)*{ω|ω是偶長度的字符串}(∑∑∑)*{ω|ω是長度為3的字符串}01∪10{01,10}0∑*0∪1∑*1∪0∪1{ω|ω以相同的字符開始和結(jié)束}(0∪ε)1*01*∪1*說明：(0∪ε)表示語言{0,ε}(0∪ε)(1∪ε){ε,0,1,01}1*φφφ*{ε}說明：*運算只能把0個字符串連接在一起，得到的唯一的一個字符串是ε8/13/20243:15PM/9例題4：設(shè)R是任意的正則表達(dá)式，有下述恒等式成立。幾個正則表達(dá)式的恒等式這些恒等式有助于對正則表達(dá)式定義的理解R∪φ=R空語言加上任何一個語言不改變這個語言Roε=R空串加上任何一個字符串上不改變這個字符串但是：R∪ε不一定等于R，Roφ不一定等于R8/13/20243:15PM/10例題5：程序設(shè)計語言中的基本單位稱為單字，如變量名和常量，這些東西可以用正則表達(dá)式描述。通常是包括小數(shù)部分和正負(fù)號的的數(shù)值常量可以描述成下述語言的一個成員：{+,--,ε}(DD*∪DD*.D*∪D*.DD*)其中，D＝{0,1,2,…,9}，則72，3.14,+7.和-.01是該語言的字符串。在編譯中，只要程序設(shè)計語言中的單字的語法用正則表達(dá)式描述出來，自動系統(tǒng)能夠生成詞法分析程序。這是編譯程序的一部分，用來在開始階段處理輸入程序。8/13/20243:15PM/11第六章正則表達(dá)式6.1引例6.2正則表達(dá)式的形式定義6.2.1形式定義6.2.2例題 6.3正則表達(dá)式與有窮自動機(jī)的等價性6.3.1充分性證明6.3.2必要性的證明(1)首先說明如何把DFA轉(zhuǎn)換成GNFA(2)說明如何把GNFA轉(zhuǎn)換成正則表達(dá)式8/13/20243:15PM/12定理1：一個語言是正則的，當(dāng)且僅當(dāng)可以用正則表達(dá)式描述它。8/13/20243:15PM/13第六章正則表達(dá)式6.1引例6.2正則表達(dá)式的形式定義6.2.1形式定義6.2.2例題 6.3正則表達(dá)式與有窮自動機(jī)的等價性6.3.1充分性證明6.3.2必要性的證明(1)首先說明如何把DFA轉(zhuǎn)換成GNFA(2)說明如何把GNFA轉(zhuǎn)換成正則表達(dá)式8/13/20243:15PM/14引理1如果一個語言可以用正則表達(dá)式描述，則它是正則的。證明：考慮正則表達(dá)式R定義的6種情況(1)R=a,這里a是字母表∑中的一個元素，那么L(R)={a},下述NFA識別L(R)(注意：這臺機(jī)器符合NFA的定義，但是不符合DFA的定義，因為(1)…(2)…)形式的表示，N=({q1,q2},∑,δ,q1,{,q2}),其中δ

的定義為δ(q1,a)=q2δ(q1,b)=φ,若8/13/20243:15PM/15R=ε；下述NFA識別L(R)R=φ；那么L(R)=φ,下述NFA識別L(R)(R1∪R2)，這里R1和R2是正則表達(dá)式；(R1oR2)，這里R1和R2是正則表達(dá)式；(R1*)，這里R1是正則表達(dá)式；(4)、(5)、(6)三種情況由正則語言類在正則運算下的封閉性的證明中給出的構(gòu)造證明方法，很容易得出需要的NFA。8/13/20243:15PM/16例題6：分若干階段把正則表達(dá)式(ab∪a)*轉(zhuǎn)換成NFA，從最小的子表達(dá)式到大一點到大一點的子表達(dá)式逐步建立。使用構(gòu)造證明中的方法一般不能給出狀態(tài)最少的NFA。a和b(1)8/13/20243:15PM/17ab(2)ab∪a(3)8/13/20243:15PM/18(ab∪a)*(4)思考：本例題一共給出了8個狀態(tài)，而最小的表示該表達(dá)式的NFA，只要2個狀態(tài)，怎么表示？習(xí)題：把正則表達(dá)式(a∪b)*aba轉(zhuǎn)換成一臺NFA。請一步步根據(jù)步驟給出。8/13/20243:15PM/19第六章正則表達(dá)式6.1引例6.2正則表達(dá)式的形式定義6.2.1形式定義6.2.2例題 6.3正則表達(dá)式與有窮自動機(jī)的等價性6.3.1充分性證明6.3.2必要性的證明(1)首先說明如何把DFA轉(zhuǎn)換成GNFA(2)說明如何把GNFA轉(zhuǎn)換成正則表達(dá)式8/13/20243:15PM/20引理2如果一個語言是正則的，那么它可以用正則表達(dá)式描述。8/13/20243:15PM/21第六章正則表達(dá)式6.1引例6.2正則表達(dá)式的形式定義6.2.1形式定義6.2.2例題 6.3正則表達(dá)式與有窮自動機(jī)的等價性6.3.1充分性證明6.3.2必要性的證明(1)首先說明如何把DFA轉(zhuǎn)換成GNFA(2)說明如何把GNFA轉(zhuǎn)換成正則表達(dá)式8/13/20243:15PM/22廣義非確定型有窮自動機(jī)GNFA8/13/20243:15PM/23GNFA其實就是NFA，只是轉(zhuǎn)移箭頭可以用任何正則表達(dá)式作標(biāo)號，而不是只能用字母和ε做標(biāo)號。GNFA讀入輸入符號段，而不必一次值讀一個符號。GNFA是非確定性的，有幾種不同的方式處理同一個符號串8/13/20243:15PM/24對GNFA的一些特殊要求：起始狀態(tài)有射到其他每一個狀態(tài)的箭頭，但是沒有從其他任何狀態(tài)射入的箭頭有唯一的一個接受狀態(tài)，并且它有從其它每一個狀態(tài)射入的箭頭，但是沒有射到其他任何狀態(tài)的箭頭；除起始狀態(tài)和接受狀態(tài)外，每一個狀態(tài)到自身或其他狀態(tài)都有一個箭頭。8/13/20243:15PM/25DFA能夠很容易的轉(zhuǎn)化成這種特殊形式的GNFA添加一個新的起始狀態(tài)和一個新的接受狀態(tài)；從新的起始狀態(tài)到老的起始狀態(tài)有一個ε箭頭；從每一個老的接受狀態(tài)到新接受狀態(tài)有一個ε箭頭；如果一個箭頭有多個標(biāo)記(即兩個狀態(tài)之間有多個方向相同的箭頭)，則把它替換為一個標(biāo)記著原先標(biāo)記的并集的箭頭；在沒有箭頭的狀態(tài)之間添加φ標(biāo)記。(此步驟不改變識別的語言，因為φ標(biāo)記的箭頭永遠(yuǎn)不能被使用)8/13/20243:15PM/26第六章正則表達(dá)式6.1引例6.2正則表達(dá)式的形式定義6.2.1形式定義6.2.2例題 6.3正則表達(dá)式與有窮自動機(jī)的等價性6.3.1充分性證明6.3.2必要性的證明(1)首先說明如何把DFA轉(zhuǎn)換成GNFA(2)說明如何把GNFA轉(zhuǎn)換成正則表達(dá)式8/13/20243:15PM/27第一步：每一個GNFA都有一個等價的僅2個狀態(tài)的GNFA每一個GNFA都有個狀態(tài)(證明：GNFA都有起始狀態(tài)和接受狀態(tài)，且是兩個不同的狀態(tài))每一個個狀態(tài)的GNFA都可以轉(zhuǎn)為為等價的狀態(tài)的GNFA(如何轉(zhuǎn)變才是本部分的關(guān)鍵所在)8/13/20243:15PM/28第二步：僅2個狀態(tài)的GNFA，可以很容易的轉(zhuǎn)換成為正則表達(dá)式證明：因為只有起始狀態(tài)和接受狀態(tài)兩個狀態(tài)，因此，只有一個從起始狀態(tài)到接受狀態(tài)的轉(zhuǎn)移箭頭，這個箭頭上的標(biāo)記就是等價的正則表達(dá)式。解決這個關(guān)鍵環(huán)節(jié)：當(dāng)k>2時，如何構(gòu)造等價的少一個狀態(tài)的GNFA8/13/20243:15PM/29基本思路：任選一個不是起始狀態(tài)和接受狀態(tài)的中間狀態(tài)，將其刪除，記為q刪除并通過修改留下來的部分，使其仍然識別相同的語言。(這個q刪除一定能找到嗎？)

刪除q刪除后，改動每一個留下來的箭頭上標(biāo)記的正則表達(dá)式。新標(biāo)記中加入失去的計算，從而彌補(bǔ)由于刪除來的損失。從狀態(tài)qi到qj的新標(biāo)記是描述使機(jī)器直接從從狀態(tài)qi到qj或通過狀態(tài)q刪除帶到qj的所有字符串的表達(dá)式。圖示給出了一個例子：8/13/20243:15PM/30思考題：