龙书中DFA的状态转换表压缩的四个数组是怎么构造出来的?
RTdefault basenextcheck
不明白啊哪位高人赐教~:em14: int nextstate(s, a) {
if(check+a] == s ) return next+a];
else return nextstate(default,a);
}
这个base 和check 数组怎么填？ 有很多状态的转换表很相似, 比如说状态s1, s2,s3,假设区别仅仅在'a' (97) 上的转换,分别转换到 s4, s5, s6
看一下转换表:
tran = {....,s4 ..}; //'a'
tran = {....,s5 ..};
tran = {....,s6 ..};
defualt = s1;
default = s1;
default = s1;
next = {.... s4..., s5, s6}, next(防止越界用的) = -1;
check = {s1, ... s1, s2, s3}; check = -1;
base = 0;
base = 256-'a' = 159;
base = 257-'a' = 160;
base是根据next的空闲位置而计算出来的, 比如当1找到位置0的时候, check都瞒了, 然后对于s2, 只有当pos = 159,才发现 base = -1(空闲) ;然后设置s2的base,并改next,check分别为s5,s2
然后拿这个例子跟一下就知道了
nextstate(s, a) :em09: :em09: 明白了 感谢～～ 我是之前问DFA压缩的，开始以为是看懂了，但回过头来还有些疑问
假设是这样一个DFS end 和 else 是 关键字 假设endls={0,1,2,3,4}
我想问的遇到这样怎么构建：check和base数组
base 和 base是否无所谓其大小？
只要让 check+] 不等于3就行吗？
default是否是设为7
谢谢 希望能收到答复:mrgreen:
state | e n d l s
----------------------------------------
0 | 1 7 7 7 7
1 | 7 2 7 4 7
2 | 7 7 3 7 7
3 | 7 7 7 7 7
4 | 7 7 7 7 5
5 | 6 7 7 7 7
6 | 7 7 7 7 7
7 | 7 7 7 7 7
页:
[1]