具有ε動作的NFA的確定化——子集法由于現(xiàn)在的NFA中具有ε動作，故下面要介紹的構(gòu)造相應(yīng)DFA的方法和定理3?1中所給出的方法有所不同。
讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：域名注冊、虛擬主機(jī)、營銷軟件、網(wǎng)站建設(shè)、竹山網(wǎng)站維護(hù)、網(wǎng)站推廣。
設(shè)已給具有ε動作的非確定的有限自動機(jī)
M=(K,Σ,f,S0,Z)
則構(gòu)造相應(yīng)的DFA
M′=(K′,Σ,f′,q0,Z′)
的基本思路是： 首先把從S0出發(fā)，僅經(jīng)過任意條ε矢線所能到達(dá)的狀態(tài)所組成的集合作為M′的初態(tài)q0，然后分別把從q0出發(fā)，經(jīng)過對輸入符號a∈Σ的狀態(tài)轉(zhuǎn)移所能到達(dá)的狀態(tài) (包括轉(zhuǎn)移后再經(jīng)ε矢線所能到達(dá)的狀態(tài))組成的集合作為M′的狀態(tài)，如此等等，直到不再有新的狀態(tài)出現(xiàn)為止。具體地說，構(gòu)造K′及f′的步驟可遞歸地描述如下。
1?令K′={εCLOSURE(S0)}(給出M′的初態(tài)q0)。
2?對于K′中任一尚未標(biāo)記的狀態(tài)qi={Si1,Si2,…,Sim},Sik∈K，做：
(1) 標(biāo)記qi；
(2) 對于每個a∈Σ，置
T=f({Si1,Si2,…,Sim},a)
qj=εCLOSURE(T)
(3) 若qj不在K′中，則將qj作為一個未加標(biāo)記的狀態(tài)添加到K′中，且把狀態(tài)轉(zhuǎn)移
f′(qi,a)=qj
添加到M′。
3?重復(fù)進(jìn)行步驟2，直到K′中不再含有未標(biāo)記的狀態(tài)為止。對于由此構(gòu)造的K′，我們把那些至少含有一個Z中的元素的qi作為M′的終態(tài)。
例3?4再考慮圖310所示的NFA，對它應(yīng)用上述算法進(jìn)行確定化，我們有：
1?因為εCLOSURE(S0)={S0,S1,S2,S3}，故將q0={S0,S1,S2,S3}作為未標(biāo)記的狀態(tài)置于K′中。
2?此時K′中僅有惟一的未標(biāo)記狀態(tài)q0，故
(1) 標(biāo)記q0；
(2) 作
f′(q0,a)=εCLOSURE(f({S0,S1,S2,S3},a))=
εCLOSURE(S0)=q0
f′(q0,b)=εCLOSURE(f({S0,S1,S2,S3},b))=
εCLOSURE({S1,S3})={S1,S3}
且把q1={S1,S3}作為未加標(biāo)記的狀態(tài)加入K′中，再作
f′(q0,c)=εCLOSURE(f({S0,S1,S2,S3},c))=
εCLOSURE({S2})={S2,S3}
且把q2={S2,S3}作為未加標(biāo)記的狀態(tài)加入K′中。
3?此時，K′={q0,q1,q2}，其中q1,q2均未加標(biāo)記，故
(1) 標(biāo)記q1；
(2) 作
f′(q1,a)=εCLOSURE(f({S1,S3},a))=
εCLOSURE(?)=?
f′(q1,b)=εCLOSURE(f({S1,S3},b))=
εCLOSURE({S1,S3})=q1
f′(q1,c)=εCLOSURE(f({S1,S3},c))=此時，K′未增大，但q2尚未標(biāo)記，故
(1) 標(biāo)記q2；(2) 類似地可求得f′(q2,a)=f′(q2,b)=? f′(q2,c)=q2；至此，K′中的狀態(tài)q0,q1,q2已全部標(biāo)記完畢，故確定化的過程結(jié)束。最后，容易看到，Z′={q0,q1,q2}，且所得的DFA M′如圖312所示。
例3?5對于圖311所示的NFA，利用上述算法所得的DFA如圖313所示。其中，圓圈中的數(shù)字都是原NFA的狀態(tài)編號，在圖313中，q0={0,1,7,11,14,19,24,26,28,30,33,35,38,40}。標(biāo)有“#”的狀態(tài)意指在這些狀態(tài)之下，當(dāng)掃視到未在其射出弧上出現(xiàn)過的字母或數(shù)字字符時，將轉(zhuǎn)移到狀態(tài)25。顯然，在按圖313實現(xiàn)詞法分析程序時，同樣應(yīng)采取某種策略，以區(qū)別源程序中的關(guān)鍵字和標(biāo)識符。
圖3－13M確定化后的DFA
最后，順便提及，上面所給出的NFA確定化的算法，同樣可應(yīng)用于不含ε動作的NFA的確定化。
Java中正則表達(dá)式匹配的語法規(guī)則：
以下是整理出來的Java下運(yùn)用正則表達(dá)式實現(xiàn)匹配的程序案例，代碼如下：
package?org.luosijin.test;
import?java.util.regex.Matcher;
import?java.util.regex.Pattern;
/**
*?正則表達(dá)式
*?@version?V5.0
*?@author?Admin
*?@date???2015-7-25
*/
public?class?Regex?{
/**
*?@param?args
*?@author?Admin
*?@date?2015-7-25
*/
public?static?void?main(String[]?args)?{
Pattern?pattern?=?Pattern.compile("b*g");
Matcher?matcher?=?pattern.matcher("bbg");
System.out.println(matcher.matches());
System.out.println(pattern.matches("b*g","bbg"));
//驗證郵政編碼
System.out.println(pattern.matches("[0-9]{6}",?"200038"));
System.out.println(pattern.matches("http://d{6}",?"200038"));
//驗證電話號碼
System.out.println(pattern.matches("[0-9]{3,4}//-?[0-9]+",?"02178989799"));
getDate("Nov?10,2009");
charReplace();
//驗證身份證:判斷一個字符串是不是身份證號碼，即是否是15或18位數(shù)字。
System.out.println(pattern.matches("^//d{15}|//d{18}$",?"123456789009876"));
getString("D:/dir1/test.txt");
getChinese("welcome?to?china,江西奉新,welcome,你!");
validateEmail("luosijin123@163.com");
}
/**
*?日期提取:提取出月份來
*?@param?str
*?@author?Admin
*?@date?2015-7-25
*/
public?static?void?getDate(String?str){
String?regEx="([a-zA-Z]+)|//s+[0-9]{1,2},//s*[0-9]{4}";
Pattern?pattern?=?Pattern.compile(regEx);
Matcher?matcher?=?pattern.matcher(str);
if(!matcher.find()){
System.out.println("日期格式錯誤!");
return;
}
System.out.println(matcher.group(1));????//分組的索引值是從1開始的，所以取第一個分組的方法是m.group(1)而不是m.group(0)。
}
/**
*?字符替換:本實例為將一個字符串中所有包含一個或多個連續(xù)的“a”的地方都替換成“A”。
*?
*?@author?Admin
*?@date?2015-7-25
*/
public?static?void?charReplace(){
String?regex?=?"a+";
Pattern?pattern?=?Pattern.compile(regex);
Matcher?matcher?=?pattern.matcher("okaaaa?LetmeAseeaaa?aa?booa");
String?s?=?matcher.replaceAll("A");
System.out.println(s);
}
/**
*?字符串提取
*?@param?str
*?@author?Admin
*?@date?2015-7-25
*/
public?static?void?getString(String?str){
String?regex?=?".+/(.+)$";
Pattern?pattern?=?Pattern.compile(regex);
Matcher?matcher?=?pattern.matcher(str);
if(!matcher.find()){
System.out.println("文件路徑格式不正確！");
return;
}
System.out.println(matcher.group(1));
}
/**
*?中文提取
*?@param?str
*?@author?Admin
*?@date?2015-7-25
*/
public?static?void?getChinese(String?str){
String?regex?=?"[//u4E00-//u9FFF]+";//[//u4E00-//u9FFF]為漢字?
Pattern?pattern?=?Pattern.compile(regex);
Matcher?matcher?=?pattern.matcher(str);
StringBuffer?sb?=?new?StringBuffer();
while(matcher.find()){
sb.append(matcher.group());
}
System.out.println(sb);
}
/**
*?驗證Email
*?@param?email
*?@author?Admin
*?@date?2015-7-25
*/
public?static?void?validateEmail(String?email){
String?regex?=?"[0-9a-zA-Z]+@[0-9a-zA-Z]+//.[0-9a-zA-Z]+";
Pattern?pattern?=?Pattern.compile(regex);
Matcher?matcher?=?pattern.matcher(email);
if(matcher.matches()){
System.out.println("這是合法的Email");
}else{
System.out.println("這是非法的Email");
}
}
}
NFA確定化的時候，包含NFA初態(tài)的那個DFA狀態(tài)就是確定后的DFA的初態(tài)
DFA的終態(tài)就是所有包含了NFA終態(tài)的DFA的狀態(tài)
就如下邊的例子，是一個初態(tài)為1，終態(tài)為6，7，9的NFA經(jīng)過確定化得到的轉(zhuǎn)換矩陣，右側(cè)是將左側(cè)的轉(zhuǎn)換矩陣改名之后的DFA，也就是最后得到的DFA
對于DFA來說，他的初態(tài)就是包含了NFA唯一初態(tài)1的那個狀態(tài)，就是左邊的1，2右邊的1了
終態(tài)則是左邊的2，4，5，6，7和3，8，9和9對應(yīng)的就是右邊的2，4，5
問題問的就有問題.
NFA和DFA不是靠正則的寫法來改變的,是語言的實現(xiàn)者來決定的.
比如,awk就是DFA,JAVA就是NFA
除非是有的語言是DFA和NFA混合體實現(xiàn)才可能出現(xiàn)在寫法上改變讓正則一定使用NFA的情況
重慶分公司
重慶分公司
