nfa确定化java代码的简单介绍
将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://ybzwz.com/article/hposjd.html
