将NFA确定化的源程序

具有ε动作的NFA的确定化——子集法由于现在的NFA中具有ε动作，故下面要介绍的构造相应DFA的方法和定理3�1中所给出的方法有所不同。

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名注册、虚拟主机、营销软件、网站建设、竹山网站维护、网站推广。

设已给具有ε动作的非确定的有限自动机

M=(K,Σ,f,S0,Z)

则构造相应的DFA

M′=(K′,Σ,f′,q0,Z′)

的基本思路是： 首先把从S0出发，仅经过任意条ε矢线所能到达的状态所组成的集合作为M′的初态q0，然后分别把从q0出发，经过对输入符号a∈Σ的状态转移所能到达的状态 (包括转移后再经ε矢线所能到达的状态)组成的集合作为M′的状态，如此等等，直到不再有新的状态出现为止。具体地说，构造K′及f′的步骤可递归地描述如下。

1�令K′={εCLOSURE(S0)}(给出M′的初态q0)。

2�对于K′中任一尚未标记的状态qi={Si1,Si2,…,Sim},Sik∈K，做：

(1) 标记qi；

(2) 对于每个a∈Σ，置

T=f({Si1,Si2,…,Sim},a)

qj=εCLOSURE(T)

(3) 若qj不在K′中，则将qj作为一个未加标记的状态添加到K′中，且把状态转移

f′(qi,a)=qj

添加到M′。

3�重复进行步骤2，直到K′中不再含有未标记的状态为止。对于由此构造的K′，我们把那些至少含有一个Z中的元素的qi作为M′的终态。

例3�4再考虑图310所示的NFA，对它应用上述算法进行确定化，我们有：

1�因为εCLOSURE(S0)={S0,S1,S2,S3}，故将q0={S0,S1,S2,S3}作为未标记的状态置于K′中。

2�此时K′中仅有惟一的未标记状态q0，故

(1) 标记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}作为未加标记的状态加入K′中，再作

f′(q0,c)=εCLOSURE(f({S0,S1,S2,S3},c))=

εCLOSURE({S2})={S2,S3}

且把q2={S2,S3}作为未加标记的状态加入K′中。

3�此时，K′={q0,q1,q2}，其中q1,q2均未加标记，故

(1) 标记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尚未标记，故

(1) 标记q2；(2) 类似地可求得f′(q2,a)=f′(q2,b)=� f′(q2,c)=q2；至此，K′中的状态q0,q1,q2已全部标记完毕，故确定化的过程结束。最后，容易看到，Z′={q0,q1,q2}，且所得的DFA M′如图312所示。

例3�5对于图311所示的NFA，利用上述算法所得的DFA如图313所示。其中，圆圈中的数字都是原NFA的状态编号，在图313中，q0={0,1,7,11,14,19,24,26,28,30,33,35,38,40}。标有“#”的状态意指在这些状态之下，当扫视到未在其射出弧上出现过的字母或数字字符时，将转移到状态25。显然，在按图313实现词法分析程序时，同样应采取某种策略，以区别源程序中的关键字和标识符。

图3－13M确定化后的DFA

最后，顺便提及，上面所给出的NFA确定化的算法，同样可应用于不含ε动作的NFA的确定化。

请问JAVA中正则表达式匹配怎么实现的!

Java中正则表达式匹配的语法规则：

以下是整理出来的Java下运用正则表达式实现匹配的程序案例，代码如下：

package org.luosijin.test;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

/**

* 正则表达式

* @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("//d{6}", "200038"));

//验证电话号码

System.out.println(pattern.matches("[0-9]{3,4}//-?[0-9]+", "02178989799"));

getDate("Nov 10,2009");

charReplace();

//验证身份证:判断一个字符串是不是身份证号码，即是否是15或18位数字。

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)。

}

/**

* 字符替换:本实例为将一个字符串中所有包含一个或多个连续的“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转DFA 请问DFA的初始状态如何

NFA确定化的时候，包含NFA初态的那个DFA状态就是确定后的DFA的初态

DFA的终态就是所有包含了NFA终态的DFA的状态

就如下边的例子，是一个初态为1，终态为6，7，9的NFA经过确定化得到的转换矩阵，右侧是将左侧的转换矩阵改名之后的DFA，也就是最后得到的DFA

对于DFA来说，他的初态就是包含了NFA唯一初态1的那个状态，就是左边的1，2右边的1了

终态则是左边的2，4，5，6，7和3，8，9和9对应的就是右边的2，4，5

正则表达式1(1010*|1(010)*1)*0转化为确定有限自动机DFA

问题问的就有问题.

NFA和DFA不是靠正则的写法来改变的,是语言的实现者来决定的.

比如,awk就是DFA,JAVA就是NFA

除非是有的语言是DFA和NFA混合体实现才可能出现在写法上改变让正则一定使用NFA的情况

网站标题：nfa确定化java代码的简单介绍
转载注明：http://scgulin.cn/article/hposjd.html