計算理論與算法分析設(shè)計課件：有窮自動機

CH2有窮自動機II

2024/6/302

of1582.4正則語言與非正則語言直覺

由于FA只有有限的狀態(tài)，它只能“記住”有限的事物猜想一些非正則的語言2024/6/303

of1582.4正則語言與非正則語言定理(泵引理):設(shè)L是正則語言,則存在正整數(shù)n>0使得對任意wL,|w|n,存在分割w=xyz滿足

1)

i0,xyizL;2)|y|>0;3)|xy|n.2024/6/304

of1582.4正則語言與非正則語言2024/6/305

of1582.4正則語言與非正則語言若FA接受一個“足夠長”的字符串，則它必有重復(fù)狀態(tài)2024/6/306

of1582.4正則語言與非正則語言2024/6/307

of1582.4正則語言與非正則語言應(yīng)用(難點):B={anbn|n0}非正則2024/6/308

of1582.4正則語言與非正則語言2024/6/309

of1582.5狀態(tài)最小化找出與給定的DFA等價的最小的DFA最?。籂顟B(tài)數(shù)最少等價：接受相同的語言2024/6/3010

of1582.5狀態(tài)最小化:消除不可達狀態(tài)

在自動機中，從開始狀態(tài)沒有任何一條路徑能達到的狀態(tài)稱為不可達狀態(tài)。由于不可達狀態(tài)事實上是無用的，因此也稱多余的狀態(tài)，可以刪除它們。下面給出識別可達狀態(tài)的算法。當(dāng)該算法終止時，每一個未標(biāo)記的狀態(tài)就是不可達狀態(tài)。

識別DFA中可達狀態(tài)的算法。

①標(biāo)記開始狀態(tài)S；

②給定任意標(biāo)記過的狀態(tài)P，如果對某個輸入符號存在從狀態(tài)P到Q的轉(zhuǎn)換，則標(biāo)記每一個這樣的狀態(tài)Q；

重復(fù)步驟②，直到不再有可標(biāo)記的狀態(tài)為止。2024/6/3011

of1582.5狀態(tài)最小化:消除不可達狀態(tài)

2024/6/3012

of158DFA的化簡(狀態(tài)最小化)所謂DFA的化簡是指尋找一個狀態(tài)數(shù)比M少的確定的有窮自動機M

，使得L(M)=L(M

)?；喓蟮腄FAM′應(yīng)滿足兩個條件:(1)沒有多余狀態(tài);（不可達狀態(tài)）

(2)它的狀態(tài)集合中,沒有兩個狀態(tài)是相互等價的。定義

假定q1和q2是M中的兩個不同狀態(tài)，稱q1和q2是等價的當(dāng)且僅當(dāng)如果從狀態(tài)q1出發(fā)能掃描任意串w而停止于終態(tài)，那么從狀態(tài)q2出發(fā)也能掃描同一個串w而停止于終態(tài)；定義

如果兩個狀態(tài)q1和q2不等價，則稱這兩個狀態(tài)是可區(qū)分的。2024/6/3013

of158DFA的化簡:劃分法DFAM最小化的方法是把M的狀態(tài)集合Q劃分成一些不相交的子集，使得每個子集中的任何兩個狀態(tài)是等價的，而任何兩個屬于不同子集的狀態(tài)都是可區(qū)分的；然后在每個子集中任取一個狀態(tài)作為代表，而刪去子集中其余狀態(tài)，并把射向其余狀態(tài)的弧都改為射向作為“代表”的狀態(tài)中。2024/6/3014

of158算法:劃分法（1）將DFAM的狀態(tài)集Q分成兩個子集：終態(tài)集F和非終態(tài)集Q-F，形成初始劃分П。（2）對П建立新的劃分ПNew

，對П的每個狀態(tài)子集G，進行如下變換：

①把G劃分成新的子集，使得G的兩個狀態(tài)s和t屬于同一子集，當(dāng)且僅當(dāng)對任何輸入符號a，狀態(tài)s和t轉(zhuǎn)換到的狀態(tài)都屬于П的同一子集。

②用G劃分出的所有新子集替換G，形成新的劃分ПNew

。2024/6/3015

of158算法:劃分法(續(xù))（3）如果ПNew＝П，則執(zhí)行第（4）步；否則令П=ПNew

，重復(fù)第（2）步。（4）劃分結(jié)束后，對劃分中的每個狀態(tài)子集，選出一個狀態(tài)作代表，而刪去其他一切等價的狀態(tài)，并把射向其他狀態(tài)的箭弧改為射向這個作為代表的狀態(tài)。這樣得到的DFAM′是與DFAM等價的一切DFA中狀態(tài)數(shù)最少的DFA。2024/6/3016

of1582024/6/3017

of1582024/6/3018

of158劃分法ab{1,3}2{4,6}253{4,6}355552024/6/3019

of158劃分法ab{1,3}2{4,6}253{4,6}355552024/6/3020

of1582.6有關(guān)有窮自動機的算法(a)有一個指數(shù)算法，給定一臺NFA，構(gòu)造一臺等價的DFA(b)有一個多項式算法，給定一個正則語言，構(gòu)造一臺等價的NFA(c)有一個指數(shù)算法，給定一臺NFA，構(gòu)造一個等價的正則表達式2024/6/3021

of1582.6有關(guān)有窮自動機的算法(a)有一個指數(shù)算法，給定一臺NFA，構(gòu)造一臺等價的DFA2024/6/3022

of1582.6有關(guān)有窮自動機的算法(d)有一個多項式算法，給定一臺DFA，構(gòu)造一臺等價的狀態(tài)