正則表達(dá)式與正則語(yǔ)言

1、第三章正則表達(dá)式與正則語(yǔ)言13.1 正則表達(dá)式（Regular expression,RE） 兩個(gè)語(yǔ)言L和M的連接，記作 ，定義為 則明顯地， 兩個(gè)語(yǔ)言L和M的并，記作 ，為集合并 語(yǔ)言類(lèi)的運(yùn)算：設(shè)L，M 為 上的語(yǔ)言，則 2語(yǔ)言L的Kleene閉包，記作 定義為 其中 歸納定義為 例如： 為 的Kleene閉包。 3.1 正則表達(dá)式（Regular expression,RE）3正則表達(dá)式（遞歸定義）：（1） 是 上的正則表達(dá)式，它表示語(yǔ)言 ，即 。（2） 是 上的正則表達(dá)式，它表示語(yǔ)言 ，即 。 3.1 正則表達(dá)式（Regular expression,RE）的語(yǔ)言 ：定義 設(shè)是一個(gè)字母表

2、，上的正則表達(dá)式E與所代表（3） ，是 正則表達(dá)式，它表示語(yǔ)言 。 4（4）如果E和F分別是 上的正則表達(dá)式，則表示的語(yǔ)言為L(zhǎng)(E) 和L(F)，E和F的“和”（E+F)是 上的正則表達(dá)式且 L(E+F)=L(E)L(F)。E和F的“乘積”（EF）是 上的正則表達(dá)式且L(EF)=L(E)L(F)。E的克林閉包 是 上的正則表達(dá)式且 。（5）只有滿足（1）（4）的表達(dá)式才是 上的正則表達(dá)式。3.1 正則表達(dá)式（Regular expression,RE）5例1.設(shè) 0是正則表達(dá)式，表示語(yǔ)言 。1是正則表達(dá)式，表示語(yǔ)言 。(0+1)是正則表達(dá)式，表示語(yǔ)言 。（01）是正則表達(dá)式，表示語(yǔ)言 。 是正

3、則表達(dá)式，表示所有以01結(jié)尾的字符串組成的語(yǔ)言。3.1 正則表達(dá)式（Regular expression,RE）6例2.寫(xiě)一個(gè)表達(dá)式，它表示了交替0和1的串的集合。例如：1010101，010101 等等3.1 正則表達(dá)式（Regular expression,RE）7正則表達(dá)式的運(yùn)算優(yōu)先級(jí)規(guī)定如下：1）星運(yùn)算符有最高優(yōu)先級(jí)；2）下一個(gè)運(yùn)算級(jí)是連接運(yùn)算符（乘積）；3）并（和）是最低級(jí)。例如：3.1 正則表達(dá)式（Regular expression,RE）83.2 有窮自動(dòng)機(jī)和正則表達(dá)式 已證明DFA,NFA, 識(shí)別的語(yǔ)言類(lèi)是一致的，下面進(jìn)一步證明它們和正則表達(dá)式的語(yǔ)言也是一致的。定理3.4 如

4、果對(duì)于某個(gè)DFA A, L=L(A)，則存在一個(gè)正則表達(dá)式R,使得L=L(R)。 證明 設(shè)DFA 令 93.2 有窮自動(dòng)機(jī)和正則表達(dá)式 即 是所有那些將DFA從給定狀態(tài) 引導(dǎo)到狀態(tài) ，并且“途中”不經(jīng)過(guò)（進(jìn)入并離開(kāi)）下標(biāo)大于k的狀態(tài)的所有字符串。但i,j不受k的限制。 這樣 是所有可以將DFA從狀態(tài) 引導(dǎo)到狀態(tài) 的字符串的集合。這時(shí) 可遞歸定義為：103.2 有窮自動(dòng)機(jī)和正則表達(dá)式 可證11假設(shè)存在從i到j(luò)的路徑不經(jīng)過(guò)比k高的狀態(tài)，有類(lèi)似情形3.2 有窮自動(dòng)機(jī)和正則表達(dá)式 123.2 有窮自動(dòng)機(jī)和正則表達(dá)式 從而 表示某個(gè)正則表達(dá)式的語(yǔ)言，因?yàn)?是正則表達(dá)式且 是由遞歸定義方法進(jìn)行定義的。 明

5、顯地 有正則表達(dá)式 ，遞歸定義！ 從而 可以用正則表達(dá)式表示出來(lái)。 ，（假設(shè)狀態(tài)1是初始狀態(tài)）133.2 有窮自動(dòng)機(jī)和正則表達(dá)式 例1 給出這個(gè)自動(dòng)機(jī)語(yǔ)言的正則表達(dá)式，求正則表達(dá)式 即可143.2 有窮自動(dòng)機(jī)和正則表達(dá)式 而而153.2 有窮自動(dòng)機(jī)和正則表達(dá)式 定理3.7 每一個(gè)用正則表達(dá)式來(lái)定義的語(yǔ)言都可以用有窮自動(dòng)機(jī)來(lái)定義。證明 根據(jù)正則表達(dá)式與其表示的語(yǔ)言的定義，我們遞歸地來(lái)證明這個(gè)定理。（1） 空語(yǔ)言可以被下面的自動(dòng)機(jī)接受 163.2 有窮自動(dòng)機(jī)和正則表達(dá)式 （2） 可以被下面的自動(dòng)機(jī)接受 173.2 有窮自動(dòng)機(jī)和正則表達(dá)式 （3） 可以被下面的自動(dòng)機(jī)接受 遞歸地，設(shè)E、F為兩個(gè)正則表

6、達(dá)式，L(E)，L(F)可以被自動(dòng)機(jī) 與 接受，下面證明 ， 與 也能被有窮自動(dòng)機(jī)接受。 183.2 有窮自動(dòng)機(jī)和正則表達(dá)式 . 能被下面的自動(dòng)機(jī)接受 193.2 有窮自動(dòng)機(jī)和正則表達(dá)式 . 可以被如下的自動(dòng)機(jī)接受 203.2 有窮自動(dòng)機(jī)和正則表達(dá)式 . 可以被如下的自動(dòng)機(jī)接受 213.2 有窮自動(dòng)機(jī)和正則表達(dá)式 例2 求表達(dá)式 的 0+1：010:1:223.2 有窮自動(dòng)機(jī)和正則表達(dá)式 233.2 有窮自動(dòng)機(jī)和正則表達(dá)式 24一些討論： 3.2 有窮自動(dòng)機(jī)和正則表達(dá)式 定理3.4把DFA轉(zhuǎn)化成正則表達(dá)式的方法總是成立的，但代價(jià)太高：對(duì)于一個(gè)n狀態(tài)的自動(dòng)機(jī)，不僅要構(gòu)造大約 個(gè)表達(dá)式，而且如果不

7、化簡(jiǎn)表達(dá)式，則在n個(gè)歸納步驟的每一步，表達(dá)式的長(zhǎng)度平均增加到4倍。因此，這些表達(dá)式本身可能達(dá)到 個(gè)符號(hào)的長(zhǎng)度級(jí)別。有一種通過(guò)消除狀態(tài)把 DFA 轉(zhuǎn)化為正則表達(dá)式的方法，在某些地方避免了重復(fù)工作。例如，在定理3.4的構(gòu)造中，所有帶上標(biāo) 的表達(dá)式都利用同一個(gè)子表達(dá)式 ；因此寫(xiě)這個(gè)表達(dá)式的工作重復(fù)了 次。253.4 正則表達(dá)式的代數(shù)定律設(shè)E，F(xiàn)，G為 上的正則表達(dá)式，則 （1）結(jié)合律： （2）交換律：E+F=F+E （3）分配律：設(shè)E和F為 的兩個(gè)正則表達(dá)式，若 ，則稱(chēng)E和F等價(jià)，也記做E=F。 下面討論正則表達(dá)式的一些基本代數(shù)定律。263.4 正則表達(dá)式的代數(shù)定律(4) 冪等律：E+E=E(5) 加法運(yùn)算零元素：(6) 乘法運(yùn)算單位元：(7) 乘法運(yùn)算零元素： (8)(9)(10)273.4 正則表達(dá)式的代數(shù)定律（11）我們證明（11）即證：也即：設(shè) ，則 ，其中 ，從而 或 ，這樣 或 ，因此 283.4 正則表達(dá)式的代數(shù)定律反之，明顯地， 293.4 正則表達(dá)式的代數(shù)定律證明： ， r，s 為正則表達(dá)式， 若 ，則 為唯一解。 練習(xí)題30本章小結(jié)正則表達(dá)式 ： 這種代數(shù)記號(hào)恰好與有窮自動(dòng)機(jī)描述相同的語(yǔ)言：正則語(yǔ)言。正則表達(dá)式運(yùn)算符是：并、連接（或“點(diǎn)”）和閉包（或“星”）。正則表達(dá)式與有窮自動(dòng)機(jī)的等價(jià)性：用歸納構(gòu)造把 轉(zhuǎn)化成正則表達(dá)式，其中構(gòu)造出一些表達(dá)式作為路徑標(biāo)記，這些路