dfa编程实现
① 有多个初始状态的 DFA
对于多正则表达式匹配（Multiple Regular Expression Matching）的 DFA
在创建多正则表达式匹配的 DFA 的过程中，就有一个 DFA 的 Union 操作，在这个过程中，如果状态膨胀失去控制，需要使用某种方式对正则表达式集合进行分组，以便抑制这种状态膨胀。分组后会生成多个 DFA ，但是为了应用程序接口方便统一，将这多个 DFA 揉进一个 DFA 对象，每个分组的 DFA 就需要一个不同的初始状态(根)。
改善 DFA Union 的性能
有相同 Tail 的多个 DFA
如果用 adfa_build 分别创建了多个不同的 ADFA(Acyclic DFA, 无环自动机)，在随后的某个时间点，想将这多个 ADFA 进行合并，仍然是 DFA 的 Union 操作，这种情况下 NFA 转 DFA 过程中的状态膨胀总是线性的，虽然如此，NFA 转 DFA 的过程中仍然需要大量内存。
虽然之前我也曾想过 DFA 包含多个初始状态(根)的可能性，但一直没有深入思考，这次经过仔细思考，发现：对于(所有的) DFA 最小化算法，从理论上讲，完全没有必要限制为单根 DFA，不管有多少个根，算法都能正常工作！唯一需要注意的是，最小化前后的根，在某些应用中需要一一对应起来。
最小化之前的多根 DFA 可以完全是独立的，唯一的要求是所有 DFA 的状态 ID 属于同一个 ID 空间，这很简单，工程上用同一个 DFA 对象来表达即可，对于 分离的多个 DFA 对象，只需要实现一个 DFA 包装器，将多个分离的 DFA 的状态 ID 重新映射即可。
如此，就完成了执行多根 DFA 最小化的所有准备。最小化完成之后，这些多个 DFA 会共享一些相同的尾部，一般情况下，头部不会共享；不过极端情况下，例如 DFA1 是 DFA2 的子集，那么，从 DFA2 的根就能到达 DFA1 的根，此时整个 DFA1 就被完全共享了。
执行 DFA Union
所有的尾部都被最小化了，然后再用 NFA 转化 DFA 的方式执行最小化，这样，大大减小了 NFA 转 DFA 的时间和内存消耗。
动态 DFA 匹配多个正则表达式
细节可参考：多正则表达式匹配 (Multiple Regular Expression Matching) 中的动态 DFA 算法
主要有两点：
多个子 DFA 在 regex_build 时使用最小化算法得到一个包含多个根，一个尾的 DFA
动态 DFA 是多个子 DFA 的并集，因为并集的完全 DFA 无法构造出来（状态的指数爆炸），动态地从DFA并集的NFA构造并集的部分DFA
用正则表达式集合的并集的动态DFA搜索到具体匹配的正则表表达式ID之后，从该ID的根出发，去抽取括号部分
实现
在实现这个概念的过程中，对我的 adfa_minimize 做了一些重构，同时也进行了一些优化。
② < DFA M状态最少化的程序实现>编译课程设计啊！！！还要求MFC的界面！！！ 求大神啊！搞定给财富值~
DFA状态数的最小化
package chapter3;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* 算法 3.39 最小化一个DFA的状态数
* @author Administrator
*
*/
publicclass Arithmetic_3_39
{
/**
* 输入一个DFA D
* @param d DFA状态转换表
* @param S 状态集合
* @param E 输入字符表
* @param s 开始状态
* @param F 接受状态集
* @return 一个DFA D', 它和D接受相同的语言, 且输入状态数最少
*/
publicint[][] convert(int[][] d, Set<Integer> S, char[] E, int s, Set<Integer> F)
{
// 首先用接受状态组和非接受状态组划分 PI
Set<Set<Integer>> PI = new HashSet<Set<Integer>>();
// 计算 S - F
S.removeAll(F);
PI.add(F);
PI.add(S);
// 最初, 令PInew = PI
Set<Set<Integer>> PInew = new HashSet<Set<Integer>>();
// TODO 解决浅复制带来的问题
PInew.addAll(PI);
while (true)
{
// 对PI中的每个组G
for (Iterator<Set<Integer>> it = PI.iterator(); it.hasNext(); )
{
List<Object> groupList = new ArrayList<Object>();
Set<Integer> G = it.next();
// 使用字符表测试G的元素
// 对于字符表的每个输入a
for (int i = 0; i < E.length; i++)
{
Map<Integer, Set<Integer>> groupMap = new HashMap<Integer, Set<Integer>>();
char a = E[i];
for (Iterator<Integer> sIt = G.iterator(); sIt.hasNext(); )
{
int stat = sIt.next();
// 从状态S出发 沿着a能够到达的状态
int tar = d[stat][a];
// 获取目标状态在PI中的位置
int idx = getElelementIdx(PI, tar);
Set<Integer> group = groupMap.get(idx);
if (group == null)
{
group = new HashSet<Integer>();
groupMap.put(idx, group);
}
group.add(stat);
}
groupList.add(groupMap);
}
// 在PInew中将G替换为对G进行分组得到的那些小组
PInew.remove(G);
PInew.addAll(setListPoly(groupList));
}
// 判断2个集合组是否相等
if (!isTwoSetGrpEqual(PI, PInew))
{
PI.clear();
PI.addAll(PInew);
} else
{
break;
}
}
// TODO 步骤4
for (Iterator<Set<Integer>> it = PI.iterator(); it.hasNext(); )
{
Set<Integer> set = it.next();
// 令S1是PI组中某个G的代表
for (Iterator<Integer> sIt = set.iterator(); sIt.hasNext(); )
{
int s1 = sIt.next();
while (sIt.hasNext())
{
// 用S1替换SWP
int swp = sIt.next();
for (int i = 0; i < d.length; i++)
{
for (int j = 0; j < d[i].length; j++)
{
if (d[i][j] == swp)
{
d[i][j] = s1;
}
}
}
// 删除SWP的转换函数
d[swp] = newint[]{};
}
}
}
return d;
}
/**
* 获取某个元素在集合组中的索引
* @param set
* @param element
* @return
*/
privateint getElelementIdx(Set<Set<Integer>> set, int element)
{
int idx = 0;
for (Iterator<Set<Integer>> it = set.iterator(); it.hasNext(); )
{
Set<Integer> g = it.next();
if (g.contains(element))
{
// TODO 检查HASHCODE 是否代表了集合的位置
return idx;
}
idx++;
}
return -1;
}
// 计算集合组聚合的结果
@SuppressWarnings("unchecked")
private Set<Set<Integer>> setListPoly(List<Object> oriSetList)
{
Set<Set<Integer>> result = new HashSet<Set<Integer>>();
if (oriSetList.size() > 0)
{
// 读取第一个集合组
Map<Integer, Set<Integer>> groupMap = (Map<Integer, Set<Integer>>)oriSetList.get(0);
for (Iterator<Integer> it = groupMap.keySet().iterator(); it.hasNext(); )
{
result.add(groupMap.get(it.next()));
}
for (int i = 1; i < oriSetList.size(); i++)
{
// 获取中间集合
Map<Integer, Set<Integer>> midMap = (Map<Integer, Set<Integer>>)oriSetList.get(i);
List<Set<Integer>> midSetList = new ArrayList<Set<Integer>>();
for (Iterator<Integer> it = midMap.keySet().iterator(); it.hasNext(); )
{
midSetList.add(midMap.get(it.next()));
}
// 开始计算
// 运算结果
List<Set<Integer>> calcResult = new ArrayList<Set<Integer>>();
for (Iterator<Set<Integer>> it = result.iterator(); it.hasNext(); )
{
Set<Integer> srcSet = it.next();
for (int k = 0; k < midSetList.size(); k++)
{
// 计算2个集合的交集
Set<Integer> mixed = getSetMixed(srcSet, midSetList.get(k));
// 如果结果不为空
if (!mixed.isEmpty())
{
// 保存运算结果
calcResult.add(mixed);
}
}
}
// 将计算结果替换result
result.clear();
result.addAll(calcResult);
}
}
return result;
}
// 计算二个集合的交集
private Set<Integer> getSetMixed(Set<Integer> set1, Set<Integer> set2)
{
Set<Integer> mixed = new HashSet<Integer>();
for (Iterator<Integer> it = set1.iterator(); it.hasNext(); )
{
int emu = it.next();
if (set2.contains(emu))
{
mixed.add(emu);
}
}
return mixed;
}
/**
* 判断2个集合组是否相等
* @param setGrp1
* @param setGrp2
* @return
*/
privateboolean isTwoSetGrpEqual(Set<Set<Integer>> setGrp1, Set<Set<Integer>> setGrp2)
{
boolean same = false;
int matchCounts = 0;
if (setGrp1.size() == setGrp2.size())
{
for (Iterator<Set<Integer>> it = setGrp1.iterator(); it.hasNext(); )
{
Set<Integer> set1 = it.next();
for (Iterator<Set<Integer>> it2 = setGrp2.iterator(); it2.hasNext(); )
{
Set<Integer> set2 = it2.next();
if (set2.equals(set1))
{
matchCounts++;
}
}
}
if (matchCounts == setGrp1.size())
{
same = true;
}
}
return same;
}
}
// 测试:
package test;
import java.util.HashSet;
import java.util.Set;
import chapter3.Arithmetic_3_39;
publicclass TestCase
{
publicstaticvoid main(String[] args)
{
new TestCase().test_339();
}
publicvoid test_339()
{
// DFA的转换表
int[][] d = {{}, {2, 3}, {2, 4}, {2, 3}, {2, 5}, {2, 3}};
// 输入状态集合
Set<Integer> S = new HashSet<Integer>();
S.add(1);
S.add(2);
S.add(3);
S.add(4);
S.add(5);
// 输入字符
char[] E = {0, 1};
int s = 1;
Set<Integer> F = new HashSet<Integer>();
F.add(5);
Arithmetic_3_39 a339 = new Arithmetic_3_39();
a339.convert(d, S, E, s, F);
}
}
对于一个NFA，当把它确定化之后，得到的DFA所具有的状态数可能并不是最小的。其原因之一，就在于上面所给出的确定化算法没有考虑到DFA中具有某种“同一性”的一些状态可加以合并的问题。所谓一个DFA M状态数的最小化，是指构造一个等价的DFA M′，而后者有最小的状态数。为了说明状态数最小化算法的思想，我们先引入可区分状态的概念。设M=(K,Σ,f,S0,Z)为一DFA，并设s和t是M的两个不同状态，我们说状态s,t为某一输入串w所区分，是指从s,t中之一出发，当扫视完w之后到达M的终态，但从其中的另一个状态出发，当扫视完同一个w后而进入非终态。如果两个状态s和t不可区分 (即对任何输入串w，当且仅当f(s,w)∈Z,f(t,w)∈Z)，则称s和t等价。显然，在一个DFA中，就识别符号串的作用而言，相互等价的状态处于同等的地位，故可设法将它们合并，以减少DFA的状态个数。下面给出一个将DFA M状态数最小化的算法。此算法的基本思想，就是将M的状态集K逐步进行划分，以期最后按上述状态的等价关系将K分裂为r个 (r≤|K|)互不相交的子集，使得属于同一子集中的任何两个状态都是等价的，而属于不同子集的任意两个状态都是可区分的。此算法的执行步骤如下：(1) 首先，将M的状态集K按终态与非终态划分为两个子集Z及K-Z，以构成初始分划，记为π={Z,K-Z}。(2) 设当前的分划π中已含有m个子集，即π={I1, I2, …, Im}其中，属于不同子集的状态是可区分的，而属于同一子集中的诸状态则是待区分的。即需对每一子集Ii={Si1,Si2,…,Sin}中各状态Sir (Sir∈K,1≤r≤n)进行考察，看是否还能对它们再进行区分。例如，Sip和Siq是Ii中的两个状态，若有某个a∈Σ，使f(Sip,a)=Sju及f(Siq,a)=Skv，而状态Sju及Skv分别属于π中两个不同的子集Ij和Ik，故Sju与Skv为某一w所区分，从而Sip和Siq必为w所区分，故应将子集Ii进一步细分，使Sip和Siq分别属于Ii的不同的子集。也就是说，对于每一子集Ii及每一a∈Σ，我们需考察Iai=f(Ii,a)=∪n[]r=1f(Sir,a)若Iai中的状态分别落于π中的p个不同的子集，则将Ii分为p个更小的状态子集I(1)i,I(2)i,…，I(p)i，使得对于每一个I(j)i,f(I(j)i,a)中的全部状态都落于π的同一子集之中。注意，若对某状态Sir,f(Sir,a)无意义，则Sir与任何Sit(f(Sit,a)有定义)都是可区分的。这样，每细分一次，就得一个新的分划πnew，且分划中的子集数也由原来的m个变为m+p-1个。(3) 若πnew≠π，则将πnew作为π再重复第2步中的过程，如此等等，直到最后得到一个分划π，使πnew=π，即π中的各个子集不能再细分为止。(4) 对于所得的最后分划π，我们从它的每一子集Ij={Sj1,Sj2,…,Sjr}中任选一个状态，如Sj1，作为Ij中所含各状态的代表，这些所选出的状态便组成了M′的状态集K′。而且，若Ij中含有M的初态，则Sj1为M′的初态；若Ij中含有M的终态，则Sj1为M′的一个终态。此外，为构成DFA M′，还应将各子集中落选的状态从原DFA M中删去，并将原来进入这些状态的所有矢线都改为进入它们的代表状态。例36设已给DFAM=({S0,S1,…,S4}, {a,b},f,S0,{S4})相应的状态转换图和状态转移矩阵如图314(a)及(b)所示。现用上述算法将M最小化。(1) 初始分划由两个子集组成，即π:{S0,S1,S2,S3}, {S4}(2) 为得到下一分划，考察子集{S0,S1,S2,S3}。为叙述方便起见，下面我们用记号{}a表示：当M分别处于该子集各状态之下，对输入符号a转移到的下一状态所组成的集合。因为{S0,S1,S2,S3}a={S1}{S0,S1,S2,S3}但{S0,S1,S2}b={S2,S3}{S3}b={S4}即{S0,S1,S2,S3}b不包含在π的同一子集之中，故应将{S0,S1,S2,S3}分为两个子集{S0,S1,S2}及{S3}，于是便得到下一分划πnew:{S0,S1,S2}, {S3}, {S4}又因πnew≠π，现以πnew作为π，即π:{S0,S1,S2}, {S3}, {S4}再考虑{S0,S1,S2}，因为{S0,S1,S2}a={S1}{S0,S1,S2}而{S0,S2}b={S2}{S1}b={S3}故应将{S0,S1,S2}再分为{S0,S2}及{S1}，从而又得到πnew:{S0,S2}, {S1}, {S3}, {S4}由于此时仍有πnew≠π，故再以πnew作为π，即π:{S0,S2}, {S1}, {S3}, {S4}现考察{S0,S2}，由于{S0,S2}a={S1}而{S0,S2}b={S2}{S0,S2}即{S0,S2}a与{S0,S2}b已分别包含在π的同一子集{S1}及{S0,S2}之中，故子集{S0,S2}已不能再分裂。此时πnew=π，子集分裂的过程宣告结束。(3) 现选择状态S0作为{S0,S2}的代表，将状态S2从状态转换图中删去，并将原来引向S2的矢线都引至S0，这样，我们就得到了化简后的DFA M′，如图315(a)及(b)所示。最后，再考察图314(a)及图315(b)所示的FA。容易看出，它们所接受的语言均是以abb为后缀的任意a,b符号串所组成的集合，也就说，这两个FA是相互等价的。实际上，我们还可以进一步证明如下的定理。定理32对于有同一接受集的FA，与之等价且具有最小状态数的DFA在同构意义下 (即不顾状态的命名)是惟一的。
③ 实现将NFA转化为DFA（代码）
由于代码过长,所以转到记事本,希望能帮你解决问题,存QQ网盘共你下载:
http://202.102.64.11/cgi-bin/dl?1//NFAtoDFA.txt
④ C语言实现NFA转DFA
ε只能出现在NFA中，当然不是为了方便直观，而是连通NFA和DFA的桥梁。编译原理讲授的不是如何绘制NFA或者DFA，二是告诉读者怎样能够自动实现NFA或DFA的构造。在实际应用中ε可以帮助计算机转换NFA为DFA，而在属性文法和语法制导阶段，它也是沟通综合属性与继承属性、执行语义动作不可或缺的一部分。另外ε的使用可以大大简化文法产生式的构造难度。我记得最初使用ε是为了使得文法体系（字母表）更加完善，但是在实际应用中却变得应用广泛(此观点不一定正确)。
最后想说的是，在编译中，ε也带来了不小的麻烦，否则也就不会有诸如“去空产生式”这样的算法了:)
⑤ ！！编译原理DFA和NFA
DFA或NFA是对计算机程序的行为的抽象模型。你编写的程序其实就对应了一个自动机。简单举例来说，如果a,b可以取值0或1; 程序： if(a==1) b=1; 这个程序对应了一个自动机。
对应的自动机就有状态 (0,0), (0,1), (1,1), (1, 0)
比如你自动机的初始状态是 (1,0)即a=1,b=0时，运行程序的下一个状态就是(1,1)。
画图出来就是 这4个状态作为顶点，并且有下面几条边
(0,0) --> (0,0)（自环）, (1,0)-->(1,1), (1,1)-->(1,1)（自环）, (0,1)-->(0,1)自环
存在的意义就是一种理论模型，也可以认为是一种编程思想。 词法分析系也离不开 if else， 这一系列的if else和条件也就组成自动机。。。
最经典体现自动机思想的算法就是KMP算法，你肯定学过，字符串子串匹配的算法。 回忆这个算法的过程：算法第一步构造的next表（数据结构教材的说法）其实就是根据子串的内容构造了一个自动机！ 算法第二步将原串作为自动机输入，自动机的输出就是匹配到的子串位置或者无匹配。
⑥ 编译原理这个DFA怎么画
这个是能画的最简单的，左边是开始状态。原则是：1）先连接运算，2）再选择3）再闭包
⑦ dfa算法的关键点是什么
起因: 从网页中爬去的页面，需要判断是否跟预设的关键词匹配(是否包含预设的关键词)，并返回所有匹配到的关键词 。
目前pypi 上两个实现
但是其实包都是基于DFA 实现的
这里提供源码如下:
#!/usr/bin/python2.6
# -*- coding: utf-8 -*-
import time
class Node(object):
def __init__(self):
self.children = None
# 标记匹配到了关键词
self.flag = False
# The encode of word is UTF-8
def add_word(root,word):
if len(word) <= 0:
return
node = root
for i in range(len(word)):
if node.children == None:
node.children = {}
node.children[word[i]] = Node()
elif word[i] not in node.children:
node.children[word[i]] = Node()
node = node.children[word[i]]
node.flag = True
def init(word_list):
root = Node()
for line in word_list:
add_word(root,line)
return root
# The encode of word is UTF-8
# The encode of message is UTF-8
def key_contain(message, root):
res = set()
for i in range(len(message)):
p = root
j = i
while (j<len(message) and p.children!=None and message[j] in p.children):
if p.flag == True:
res.add(message[i:j])
p = p.children[message[j]]
j = j + 1
if p.children==None:
res.add(message[i:j])
#print '---word---',message[i:j]
return res
def dfa():
print '----------------dfa-----------'
word_list = ['hello', '民警', '朋友','女儿','派出所', '派出所民警']
root = init(word_list)
message = '四处乱咬乱吠，吓得家中11岁的女儿躲在屋里不敢出来，直到辖区派出所民警赶到后，才将孩子从屋中救出。最后在征得主人同意后，民警和村民合力将这只发疯的狗打死'
x = key_contain(message, root)
for item in x:
print item
if __name__ == '__main__':
dfa()
⑧ KF，怎样执行dfa文件 NX二次开发
UG的二次开发定义很广泛， 你简单记录一些宏Macro，然后添加到图标里面也算二次开发。 或者使用UG的Grip语言来根据自己需要实现的功能来编写一个小程序，加到自己的UG图标里面，也是二次开发。或者使用C++语言，使用UG的KF模块来编写一些程序。