正則語(yǔ)言課件

1、編譯原理Principles of Compiler第三章 正則語(yǔ)言第三章 正則語(yǔ)言正則語(yǔ)言(Regular Language)一種最簡(jiǎn)單的形式語(yǔ)言。計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的詞法屬于正則語(yǔ)言的范疇。本章內(nèi)容：正則語(yǔ)言的三種模型有窮狀態(tài)自動(dòng)機(jī)正則表達(dá)式正則文法3.1 有窮狀態(tài)自動(dòng)機(jī)一個(gè)識(shí)別 = a, 1 中所有標(biāo)識(shí)符的程序：int nStatus = 0;while( ch = getch() ) if( nStatus = 0 ) if( ch = a ) nStatus = 1; else return ERROR; else if( ch != a & ch != 1 ) return ERR

2、OR; return 0;3.1 有窮狀態(tài)自動(dòng)機(jī)識(shí)別算法可以用圖形表示：3.1 有窮狀態(tài)自動(dòng)機(jī)有窮狀態(tài)自動(dòng)機(jī)( Finite Automata )一臺(tái)只有一個(gè)變量的計(jì)算機(jī)。變量的取值范圍有限，變量的一個(gè)值稱為該計(jì)算機(jī)的狀態(tài)。計(jì)算機(jī)從初始狀態(tài)開始運(yùn)行，從坐向右讀入輸入的字符。每讀一個(gè)字符，根據(jù)一定規(guī)則修改狀態(tài)值。如果輸入結(jié)束，當(dāng)前狀態(tài)為接受狀態(tài)，則接受輸入的串；否則拒絕輸入串。3.1 有窮狀態(tài)自動(dòng)機(jī)FA的表示方法-狀態(tài)圖：狀態(tài)：用圓圈表示，圓圈中符號(hào)標(biāo)識(shí)狀態(tài)遷移：用連接兩個(gè)狀態(tài)的箭頭表示，箭頭上的符號(hào)為遷移的激活符號(hào)初始狀態(tài)：無(wú)源的箭頭標(biāo)識(shí)初始狀態(tài)接受狀態(tài)：用雙圈表示接受狀態(tài)3.1 有窮狀態(tài)自動(dòng)

3、機(jī)FA的表示方法-遷移表：a101111FA的語(yǔ)法一臺(tái)FA M = ( Q, , , q0, F )，其中：Q為一個(gè)非空有窮的狀態(tài)集合；為有窮的字母表( 符號(hào)集 )；：Q Q為狀態(tài)遷移函數(shù)；q0 Q為初始狀態(tài)；F Q為接受狀態(tài)集合。3.1 有窮狀態(tài)自動(dòng)機(jī) M = ( Q, , , q0, F )，其中：Q = 0, 1 ； = a, 1 ； = (0, a), 1), (1, a), 1), (1, 1), 1)；q0 = 0；F = 1 。FA的語(yǔ)義( FA與語(yǔ)言的關(guān)系 )FA的運(yùn)行：給定一臺(tái)FA M = ( Q, , , q0, F )M的一個(gè)運(yùn)行是一個(gè)有窮的狀態(tài)序列 = s0s1sn，其

4、中：s0 = q0；sn F；0in( a( (si, a) = si+1 ) )。例：01，011，0111都是圖中自動(dòng)機(jī)的運(yùn)行。FA的語(yǔ)義( FA與語(yǔ)言的關(guān)系 )FA接受（識(shí)別）的串：給定一臺(tái)FA M = ( Q, , , q0, F )稱一個(gè)串 = a1a2an被M接受（識(shí)別），如果M存在一個(gè)運(yùn)行 = s0s1sn，使得：0in(si, ai+1) = si+1 )。如果串不被M接受，則稱M拒絕 。FA M的語(yǔ)言L(M)為所有M接受的串的集合。FA的語(yǔ)義( FA與語(yǔ)言的關(guān)系 )例：FA與正則語(yǔ)言定義：稱FA M識(shí)別語(yǔ)言L，如果M恰好接受L中的所有串。定義：一個(gè)語(yǔ)言是正則的，當(dāng)且僅當(dāng)存在一

5、臺(tái)FA識(shí)別它。3.2 正則語(yǔ)言的封閉性正則語(yǔ)言在并運(yùn)算下的封閉性定理：如果L1與L2為正則語(yǔ)言，則L1L2也是正則語(yǔ)言。證明思路：構(gòu)造一臺(tái)FA恰好識(shí)別L1L2。語(yǔ)言的性質(zhì)語(yǔ)言是符號(hào)串的集合補(bǔ)運(yùn)算封閉性如果語(yǔ)言A為正則語(yǔ)言，那么A的補(bǔ)集也是正則語(yǔ)言語(yǔ)言封閉性的意義3.2.3 正則語(yǔ)言的補(bǔ)運(yùn)算全集為*，即所有可能的符號(hào)串的集合。證明思路由于A為正則語(yǔ)言所以存在一臺(tái)DFA M恰好識(shí)別A根據(jù)M，構(gòu)造一臺(tái)DFA M，恰好識(shí)別A的補(bǔ)集對(duì)任何一個(gè)符號(hào)串，如果M接受，則M拒絕如果M拒絕，則M接受證明L(M) = A的補(bǔ)集例：一個(gè)正則語(yǔ)言的補(bǔ)集01補(bǔ)自動(dòng)機(jī)的構(gòu)造原始自動(dòng)機(jī)補(bǔ)自動(dòng)機(jī)證明證明方法引理1在FA的計(jì)算過(guò)

6、程中，有的時(shí)候需要“猜測(cè)”的功能例：證明正則語(yǔ)言在乘積運(yùn)算下封閉普通的FA無(wú)法“猜測(cè)”需要一種機(jī)制能夠同時(shí)計(jì)算所有的可能-非確定性3.3 非確定性的有窮自動(dòng)機(jī)NFA( Nondeterministic Finite Automata )DFA( Deterministic Finite Automata )NFA與DFA的區(qū)別從DFA的每一個(gè)狀態(tài)出發(fā)，對(duì)于字母表中的每一個(gè)符號(hào)，最多只有一條遷移，而NFA可以有多條。NFA允許“空轉(zhuǎn)移”，也就是能夠不讀入任何符號(hào)就遷移到另外的狀態(tài)。3.3 非確定性的有窮自動(dòng)機(jī)3.3 非確定性的有窮自動(dòng)機(jī)對(duì)同樣的符號(hào)有多條遷移允許空轉(zhuǎn)移3.3 非確定性的有窮自動(dòng)機(jī)

7、NFA的計(jì)算方式每當(dāng)遇到多種選擇的時(shí)候就分裂，并發(fā)計(jì)算這些選擇。當(dāng)輸入結(jié)束的時(shí)候，只要有一個(gè)分支接受，則接受。例：輸入為1011一臺(tái)NFA M = ( Q, , , q0, F )，其中：Q為一個(gè)非空有窮的狀態(tài)集合；為有窮的字母表( 符號(hào)集 )；：Q 2Q為狀態(tài)遷移函數(shù)，其中=；q0 Q為初始狀態(tài)；F Q為接受狀態(tài)集合。3.3.1 NFA的形式定義3.3.1 NFA的形式定義表格表示方法01q1q1q1,q2q2q3q3q3q4q4q4q4NFA的運(yùn)行：M的一個(gè)運(yùn)行是一個(gè)有窮的狀態(tài)序列 = s0s1sn，其中：s0 = q0；sn F；0in( a(si+1 (si, a) )。3.3.2 N

8、FA的語(yǔ)言NFA接受的串：稱一個(gè)串 = a1a2am被M接受（識(shí)別），如果存在一個(gè)串 = a1a2an，其中a1,a2,an ，使得 = ，而且M存在一個(gè)運(yùn)行 = s0s1sn，使得：0in(si+1 (si, ai+1)。如果串不被M接受，則稱M拒絕 。例：0111可以寫為01113.3.2 NFA的語(yǔ)言NFA M的語(yǔ)言L(M)為所有M接受的串的集合。3.3.2 NFA的語(yǔ)言定義：如果兩臺(tái)自動(dòng)機(jī)識(shí)別相同的語(yǔ)言，則稱這兩臺(tái)自動(dòng)機(jī)等價(jià)。定理：對(duì)于任意一臺(tái)NFA，都存在等價(jià)的DFA。證明思路：對(duì)任意的NFA，構(gòu)造一臺(tái)DFA，模擬NFA的運(yùn)行，用DFA的一個(gè)狀態(tài)去記錄所有分支的狀態(tài)。3.3.3 NF

9、A與DFA的等價(jià)性3.3.3 NFA與DFA的等價(jià)性例：證明：首先不考慮空轉(zhuǎn)移的情況令NFA N = ( Q, , , q0, F )構(gòu)造DFA M = ( Q, , , q0, F )，其中Q = 2Q對(duì)所有q Q，a，令(q,a) = rq (r,a)q0 = q0F = q Q | q包含N的一個(gè)接受狀態(tài) 3.3.3 NFA與DFA的等價(jià)性考慮空轉(zhuǎn)移的情況定義函數(shù)-Closure對(duì)M的一個(gè)狀態(tài)q Q， -Closure(q)表示從q中的狀態(tài)出發(fā)，只經(jīng)過(guò)空轉(zhuǎn)移能到達(dá)的所有狀態(tài)的集合改寫轉(zhuǎn)移函數(shù)：(q,a) = qQ | 存在r q，使得q -Closure(r,a) 。改寫起始狀態(tài)q0 =

10、 -Closure(q0)3.3.3 NFA與DFA的等價(jià)性子集法構(gòu)造狀態(tài)集的冪集，作為DFA的狀態(tài)集；對(duì)DFA的每一個(gè)狀態(tài)，構(gòu)造由其出發(fā)的遷移。造表法( On-the-fly )首先構(gòu)造DFA的初始狀態(tài)；對(duì)于現(xiàn)有DFA的狀態(tài)，構(gòu)造由其出發(fā)的遷移，如果遷移的目標(biāo)為新狀態(tài)則構(gòu)造一個(gè)新的狀態(tài)。3.3.4 從NFA到DFA的轉(zhuǎn)換例：3.3.4 從NFA到DFA的轉(zhuǎn)換推論：一個(gè)語(yǔ)言是正則的，當(dāng)且僅當(dāng)存在一臺(tái)NFA識(shí)別它。定理：正則語(yǔ)言在并運(yùn)算、乘積運(yùn)算、閉包運(yùn)算下封閉。3.3.5 正則語(yǔ)言的封閉性并運(yùn)算3.3.5 正則語(yǔ)言的封閉性乘積運(yùn)算3.3.5 正則語(yǔ)言的封閉性閉包運(yùn)算3.3.5 正則語(yǔ)言的封閉性

11、利用運(yùn)算符來(lái)構(gòu)造語(yǔ)言運(yùn)算的表達(dá)式，從而得到復(fù)雜的語(yǔ)言。如果這些運(yùn)算符為正則運(yùn)算，則稱這樣的表達(dá)式為正則表達(dá)式。正則運(yùn)算：并、乘積、閉包。3.4 正則表達(dá)式語(yǔ)法：歸納定義稱R為一個(gè)正則表達(dá)式，如果R為以下情況的一種：a，aR1 | R2，R1 R2，如果R1與R2都是正則表達(dá)式R1 R2，如果R1與R2都是正則表達(dá)式R1*，如果R1是正則表達(dá)式3.4.1 正則表達(dá)式的定義語(yǔ)義：歸納定義如果R為一個(gè)正則表達(dá)式，那么R的語(yǔ)言L(R)可以歸納定義如下：L(a) = aL() = L() = L(R1 | R2) = L(R1) L(R2)L(R1 R2) = L(R1) L(R2)L(R1* ) =

12、L(R1)*3.4.1 正則表達(dá)式的定義R1 | R2 = R2 | R1 (R1 R2) R3 = R1 (R2 R3)(R1 R2) R3 = R1 (R2 R3)R1 (R2 R3) = (R1 R2 ) (R1 R3)3.4.2 正則表達(dá)式的性質(zhì)定理：一個(gè)語(yǔ)言是正則的，當(dāng)且僅當(dāng)存在一個(gè)正則表達(dá)式描述它。引理1：如果一個(gè)語(yǔ)言可以用正則表達(dá)式描述，則它是正則語(yǔ)言。引理2：如果一個(gè)語(yǔ)言是正則的，那么可以用正則表達(dá)式描述它。3.4.3 正則表達(dá)式與FA的等價(jià)引理1：如果一個(gè)語(yǔ)言可以用正則表達(dá)式描述，則它是正則語(yǔ)言。證明思路：對(duì)任意一個(gè)正則表達(dá)式，都存在等價(jià)的FA。證明方法：歸納法，按照正則運(yùn)算的次數(shù)歸納歸納基礎(chǔ)：運(yùn)算次數(shù)n = 0；歸納假設(shè)：假設(shè)運(yùn)算次數(shù)n 0；| p。證明思路：令DFA M識(shí)別L，p為M的狀態(tài)數(shù)。的長(zhǎng)度大于等于p，對(duì)應(yīng)的運(yùn)行 = s0s1sm，滿足m p，因此中存在重復(fù)的狀態(tài)。3.7 附錄：正