怎么动态构造DFA?

Question

比如在vim中搜索用户输入的某一字符串，动态地构造DFA，然后在文本中进行匹配，请问有没有动态地构造DFA的例子程序，谢谢

Answer 1

既然语言可以描述DFA,那么DFA就可以动态构造.
我来造个语言来描述DFA,解释这个语言就是动态构造DFA

2. 其中0,1,2,error都是状态
3. ->代表状态转换
4. 第一个冒号后面那个是触发条件
5. 第二个冒号后面那个是动作
6. default后面那个接->error，表示如果触发条件不对，则转向error状态
7. start:0
8. 0->1:x1:action1
9. 1->1:x2:action2
10. 1->2:x3:action3
11. 2->2:x4:action4
12. 2->1:x5:action5
13. 2->1:x6:action6
14. default:->error

复制代码
[ 本帖最后由 cjaizss 于 2008-6-9 18:20 编辑 ]

Answer 2

建立数据结构和算法:
(当前状态,触发)作为key

Answer 3

谢谢,

我没问清楚

根据正规表达式动态构建DFA

如用户在编辑文件时,突然想查找符串:"abc",则就应该构建这个字符串的DFA

lex用的是 Thompson构造法: 正规表达式 -> NFA -> DFA -> DFA状态最小化

现在好像有从 正规表达式 直接到 DFA 的转化

Answer 4

.......非扩展正则表达式等价于DFA
直接转换
或者说,regex本身就是DFA,不需要转化
不过我还是要说明一下Thompson construction,这只是因为regex看起来表示DFA不够直接
这是一个regex->NFA->DFA->最小DFA
的过程
其实可以直接搭出来.
regex有这几种结构假设A和B都是子regex)
AB
A|B
A*
regex都是用以上三种结构反复组合出来的
其实只有以上三种
我来解释一下,
A+其实就是
AA*
A
A{a,b}其实就是
AAAAA...A(A|AA|...|A...A)
A{a,}其实就是A.....AA*
.....
那么AB
表示
DFA到达可以表达A的状态之后再接收状态直到表达AB的状态
A|B就是状态存在两个分叉,经过A|B之后,是同一个状态
A*就是一个圈,最终回到原来状态
于是一个递归就可以regex->DFA

[ 本帖最后由 cjaizss 于 2008-6-10 19:51 编辑 ]

Answer 5

谢谢

很详细

我试着写个程序看看