dfa算法
⑴ 给出描述java表达式的DFA~~~~~~~~~~在线等
这是DFA算法，自己设定好值，看下结果
import java.util.*;
import java.io.*;
class DFA
{
boolean recognizeString(int move[][], int accept_state[], String word)
{
int s=0;
for (int i = 0; i <word.length(); i++)
{
char c = word.charAt(i);
s = move[s][c - 'a'];
}
for (int j = 0; j < accept_state.length; j++)
if (s == accept_state[j]) return true;
return false;
}
public static void main(String args[]) throws IOException
{
int n, m;
BufferedReader in = new BufferedReader(new FileReader("DFA.in"));
StringTokenizer st = new StringTokenizer(in.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
while (n != 0)
{
int[][] move = new int[n][m];
for(int i=0; i<n; i++)
{
st = new StringTokenizer(in.readLine());
for (int j=0; j<m; j++)
move[i][j] = Integer.parseInt(st.nextToken());
}
String[] temp = in.readLine().split("\s");
int[] accept = new int[temp.length];
for (int i=0; i<accept.length; i++) accept[i] = Integer.parseInt(temp[i]);
String word = in.readLine();
while (word.compareTo("#") != 0)
{
DFA dfa = new DFA();
if (dfa.recognizeString(move, accept, word)) System.out.println("YES"); else System.out.println("NO");
word = in.readLine();
}
st = new StringTokenizer(in.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
}
}
}
⑵ 编译原理NFA转DFA ，请问DFA的初始状态如何确定
NFA确定化的时候，包含NFA初态的那个DFA状态就是确定后的DFA的初态。
DFA的终态就是所有包含了NFA终态的DFA的状态。
对于DFA来说，他的初态就是包含了NFA唯一初态1的那个状态，就是左边的1，2右边的1了。
脱氧核糖-磷酸链在螺旋结构的外面，碱基朝向里面。两条多脱氧核苷酸链反向互补，通过碱基间的氢键形成的碱基配对相连，形成相当稳定的组合。
(2)dfa算法扩展阅读：
将DNA或RNA序列以三个核苷酸为一组的密码子转译为蛋白质的氨基酸序列，以用于蛋白质合成。密码子由mRNA上的三个核苷酸（例如ACU，CAG，UUU）的序列组成，每三个核苷酸与特定氨基酸相关。
例如，三个重复的胸腺嘧啶（UUU）编码苯丙氨酸。使用三个字母，可以拥有多达64种不同的组合。由于有64种可能的三联体和仅20种氨基酸，因此认为遗传密码是多余的（或简并的）：一些氨基酸确实可以由几种不同的三联体编码。
但每个三联体将对应于单个氨基酸。最后，有三个三联体不编码任何氨基酸，它们代表停止（或无意义）密码子，分别是UAA，UGA和UAG 。
⑶ 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()
⑷ 用C语言采用模拟DFA算法编写一个扫描器（词法分析器），用来识别：由任意个a或b开始后接aa再自加或自减1的
你是什么意思啊，告诉我才知道啊，是不是漏字了
⑸ 有没有师兄，师姐有关于DFA,BFS的题目，练练算法 别太难
应该是DFS吧？DFA是编译原理里面的
练算法推荐杭电ACM：
DFS：1010 1241 1312
BFS：1026 1242
⑹ nfa如何转换成等价的dfa结果唯一吗
nfa转化成等价的dfa结果是不唯一的
NFA转化成等价的DFA再转化成最简化的DFA结果是唯一的
将NFA转化成等价的DFA有一套固定的算法，这里空间有限我不赘述，你可以去网络“NFA转化成DFA
算法”
⑺ 用C语言采用模拟DFA算法编写一个扫描器（词法分析器）
（1）滤掉源程序中的无用成分，如空格；
这个”源程序“是指？不是只要识别像
bbbbaa+1,
aa-1
这样的字符串么？
⑻ 编译原理中，由NFA转化来的DFA是唯一的吗
根据算法转化来的DFA肯定是唯一的，但是转化得到的DFA并不一定是状态最少的，每一个DFA都可以转化到状态最少的DFA。状态最少的DFA是唯一的（状态名不同的同构情况除外）。可参考龙书（一本编译书籍）。因为每个DFA都可以对应相应的NFA（DFA本身就是），所以NFA转化的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的最小化如何化简的步骤
下面具体介绍DFA的化简算法：
（1） 首先将DFA M的状态划分出终止状态集K1和非终止状态集K2。
K＝K1∪K2
由上述定义知，K1和K2是不等价的。
（2） 对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。
设第i次划分已将状态集划分为k组，即：
K＝K1(i)∪K2(i)∪…∪Kk(i)
对于状态集Kj(i)（j=1,2,…,k）中的各个状态逐个检查，设有两个状态Kj’、 Kj’’∈Kj(i)，且对于输入符号a，有：
F（Kj'，a）＝Km
F（Kj''，a）＝Kn
如果Km和Kn属于同一个状态集合，则将Kj’和Kj’’放到同一集合中，否则将Kj’和Kj’’分为两个集合。
（3） 重复第（2）步，直到每一个集合不能再划分为止，此时每个状态集合中的状态均是等价的。
（4） 合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。
（5） 若有无关状态，则将其删去。
根据以上方法就将确定有限自动机进行了简化，而且简化后的自动机是原自动机的状态最少的自动机。