形式語言與自動機理論二課件

形式語言與自動機理論山東大學計算機科學與技術(shù)學院2007.3形式語言與自動機理論山東大學計算機科學與技術(shù)學院2007.31第四章正規(guī)表達式4.1正規(guī)表達式的形式定義定義：設(shè)是一個字母表，字母表上正規(guī)式（RegularExpression,RE）和正規(guī)集定義如下：（1）是上的正規(guī)式，對應(yīng)的正規(guī)集為；（2）是上的正規(guī)式，對應(yīng)的正規(guī)集為{}；（3）對a，a是上的正規(guī)式，對應(yīng)的正規(guī)集為{a}；第四章正規(guī)表達式4.1正規(guī)表達式的形式定義定義：設(shè)是2第四章正規(guī)表達式4.1正規(guī)表達式的形式定義（4）如果r和s分別是上的正規(guī)式，對應(yīng)的正規(guī)集為R和S。那么(r+s)為正規(guī)式，對應(yīng)的正規(guī)集為RS；(rs)為正規(guī)式，對應(yīng)的正規(guī)集為RS；(r*)為正規(guī)式，對應(yīng)的正規(guī)集為R*（5）只有滿足上述形式定義的表達式才是上的正規(guī)式，它所表達的語言是正規(guī)集。第四章正規(guī)表達式4.1正規(guī)表達式的形式定義（4）如果r和3第四章正規(guī)表達式正規(guī)表達式的運算性質(zhì)假設(shè)r,s,t都是上正規(guī)式，則有以下性質(zhì)：（1）結(jié)合律；（2）分配律；（3）交換律；（4）冪等律；（5）加運算單位元；（6）乘運算單位元；（7）乘運算零元；（8）(r*)*=r*；（9）r*=r++；（10）*=（11）*=

4.1正規(guī)表達式的形式定義第四章正規(guī)表達式正規(guī)表達式的運算性質(zhì)4.1正規(guī)表達式的形4第四章正規(guī)表達式4.2正規(guī)表達式與FA的等價假設(shè)r是上的正規(guī)式，M是一個FA。若L(r)=L(M)，則稱正規(guī)式r

與FAM等價。第四章正規(guī)表達式4.2正規(guī)表達式與FA的等價假設(shè)5第四章正規(guī)表達式4.2正規(guī)表達式與FA的等價定理：每個正規(guī)表達式r都存在一個

-NFAM

使得L(M)

=

L(r)。(1)運算符個數(shù)為0q0qfq0aq0qf第四章正規(guī)表達式4.2正規(guī)表達式與FA的等價定理：每個正6第四章正規(guī)表達式定理：每個正規(guī)表達式r都存在一個

-NFAM

使得L(M)

=

L(r)。(2)運算符個數(shù)不為0

r=r1+r2

M2M1q0f1q1f2q2f0

第四章正規(guī)表達式定理：每個正規(guī)表達式r都存在一個-N7第四章正規(guī)表達式定理：每個正規(guī)表達式r都存在一個

-NFAM

使得L(M)

=

L(r)。(2)運算符個數(shù)不為0

r=r1r2M2M1f1q1f2q2

第四章正規(guī)表達式定理：每個正規(guī)表達式r都存在一個-N8第四章正規(guī)表達式定理：每個正規(guī)表達式r都存在一個

-NFAM

使得L(M)

=

L(r)。(2)運算符個數(shù)不為0

r=r1*

M1q0f1q1f0

第四章正規(guī)表達式定理：每個正規(guī)表達式r都存在一個-N9第四章正規(guī)表達式4.2正規(guī)表達式與FA的等價定理：設(shè)L是被DFAM接受的語言，則L可以被正規(guī)表達式表示。-NFANFADFARGRE第四章正規(guī)表達式4.2正規(guī)表達式與FA的等價定理：設(shè)L10第五章正規(guī)語言的性質(zhì)5.1Pumping引理定理：假設(shè)

為有限字母表，L

*。若L是正規(guī)語言，那么存在正整數(shù)n使得對任意的w1,w2,w3

*,當w1w2w3L并且|w2|n,可以寫成w2=,這里，，||n.則w1

kw3L(k=0,1,2,….)。(1)Pumping引理的提出第五章正規(guī)語言的性質(zhì)5.1Pumping引理定理：假設(shè)11第五章正規(guī)語言的性質(zhì)5.1Pumping引理(1)Pumping引理的提出Pumping引理：假設(shè)L是正規(guī)集，那么存在正整數(shù)n使得當w

L并且|w|n,就可以寫出w=，這里，，||n，且對k0,則

kL。第五章正規(guī)語言的性質(zhì)5.1Pumping引理(1)P12第五章正規(guī)語言的性質(zhì)5.1Pumping引理(2)Pumping引理的應(yīng)用例1：證明L1={anbn|n1}不是RL。例2：證明L2={w|w

*且={0,1},w=w-1}

不是RL。這里w是回文。即w與w的逆相同。第五章正規(guī)語言的性質(zhì)5.1Pumping引理(2)P13第五章正規(guī)語言的性質(zhì)5.1Pumping引理(2)Pumping引理的應(yīng)用例3：證明L3={an2|nN}不是RL。例4：證明L4={ap|p是素數(shù)}不是RL。第五章正規(guī)語言的性質(zhì)5.1Pumping引理(2)P14第五章正規(guī)語言的性質(zhì)5.2正規(guī)語言的封閉性正規(guī)語言在并、乘積、閉包運算下是封閉的；(2)正規(guī)語言類在補運算下是封閉的；(3)正規(guī)語言類在交運算下是封閉的；第五章正規(guī)語言的性質(zhì)5.2正規(guī)語言的封閉性正規(guī)語言在并15第五章正規(guī)語言的性質(zhì)5.2正規(guī)語言的封閉性(4)

代換定義：設(shè)，是兩個字母表，映射

f:

p(

*)稱為到的代換。如果對a,f(a)是上的RL，則稱f是正則代換或正規(guī)代換。正規(guī)語言類在代換下是封閉的。第五章正規(guī)語言的性質(zhì)5.2正規(guī)語言的封閉性(4)代換定16第五章正規(guī)語言的性質(zhì)(5)同態(tài)5.2正規(guī)語言的封閉性定義：設(shè)，是兩個字母表，映射

f:

*如果對x,y

*,有f(xy)=f(x)f(y)，則稱f是從

到*的同態(tài)映射。正規(guī)語言在同態(tài)和逆同態(tài)下是封閉的。第五章正規(guī)語言的性質(zhì)(5)同態(tài)5.2正規(guī)語言的封閉性定17第五章正規(guī)語言的性質(zhì)5.2正規(guī)語言的封閉性正規(guī)語言在商運算下是封閉的。定義：假設(shè)L1,L2

*,則L1和L2的商定義為：

L1/L2={x|yL2，使得xyL1}第五章正規(guī)語言的性質(zhì)5.2正規(guī)語言的封閉性正規(guī)語言在商運18第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理和DFA極小化一、相關(guān)概念1、等價關(guān)系2、劃分3、劃分加細4、等價類5、商集6、等價關(guān)系的指數(shù)第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理19第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理和DFA極小化二、Myhill-Nerode定理定理：假設(shè)是有限字母表，L

*,以下三個命題等價：（1）L是正規(guī)語言；（2）L是*上具有有窮指數(shù)的右不變等價關(guān)系的某些等價類的并；（3）如果RL={<x,y>|x,y

*,對z

*,xzL當且僅當yzL}，則RL的指數(shù)有窮。第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理20第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理和DFA極小化例：假設(shè)L=0*10*它被下列自動機接受。能否簡化？q0q1q2q3q4q500110110100,1q0:(00)nR(00)mq1:0(00)nR(00)m0q2:(00)n1R(00)m1q3:(00)n01R(00)m01q4:(0)n10(0)mR(0)p10(0)qq5:xRmy,x和y至少含有兩個1的串。(這里m,n,p,q0)第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理21第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理和DFA極小化二、Myhill-Nerode定理推論1：對任意正規(guī)語言L，如果DFAM滿足L(M)=L，則|*/RL||Q|推論2：在同構(gòu)（即狀態(tài)重新命名）的意義下，接受一個語言L的最小DFA是唯一的。第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理22第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理和DFA極小化三、DFA的極小化1、狀態(tài)等價和可區(qū)分設(shè)DFAM=(Q,,,q0,F)，如果

x*，使得Q中的兩個狀態(tài)q1,q2，(q1,x)F和(q2,x)F中僅有一個成立，則稱q1和q2是可區(qū)分的。若對不同的狀態(tài)q1,q2和任意的串x

*，有(q1,x)F當且僅當(q2,x)F。則稱q1和q2是等價的，記為q1

q2。第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理23第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理和DFA極小化三、DFA的極小化2、利用等價和可區(qū)分概念，標記填表求極小化（1）構(gòu)造一個二維表（2）標識可區(qū)分狀態(tài)（3）對剩余的每對狀態(tài)進行標識（4）重復(fù)（3）直到所有狀態(tài)對處理完畢。第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理24第五章正規(guī)語言的性質(zhì)例：設(shè)DFAM=({q0,q1,..,q5},{0,1},,q0,F)q2q0q1q4q3q5010100111100第五章正規(guī)語言的性質(zhì)例：設(shè)DFAM=({q0,q1,..25第五章正規(guī)語言的性質(zhì)5.3Myhill-Nerode定理和DFA極小化四、正規(guī)語言的判定算法1、空性、有窮性、無窮性定理：具有n個狀態(tài)的有限自動機接受的串集合是：（1）非空的當且僅當這個有限自動機接受一個長度小于n的串，