形式語言與自動機 正則表達式

形式語言與自動機正則表達式第一頁，共三十五頁，編輯于2023年，星期二6/10/202311:21AM/2第六章正則表達式6.1引例6.2正則表達式的形式定義6.2.1形式定義6.2.2例題 6.3正則表達式與有窮自動機的等價性6.3.1充分性證明6.3.2必要性的證明(1)首先說明如何把DFA轉(zhuǎn)換成GNFA(2)說明如何把GNFA轉(zhuǎn)換成正則表達式第二頁，共三十五頁，編輯于2023年，星期二6/10/202311:21AM/3例題1：：

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

正則表達式：(0∪1)0*,正則表達式的值是一個語言注意：(0∪1)0*表示的是01后加任意多個0構(gòu)成的字符串所組成的語言0和1是集合{0}和{1}的縮寫，就是{0}∪{1},這部分的值是語言{0,1}0*就是{0}*,其值為所有包含任意個0的字符串構(gòu)成的語言在正則表達式中省略了連結(jié)運算符號o,(0∪1)0*實際上是(0∪1)o0*正則表達式可以用來描述滿足“某種模式”的字符串。第三頁，共三十五頁，編輯于2023年，星期二6/10/202311:21AM/4

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

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

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