龙书中DFA的状态转换表压缩的四个数组是怎么构造出来的?

317316abcd

RT
default   base  next  check   



不明白啊  哪位高人赐教~

317316abcd

int nextstate(s, a) {

   if(check[base+a] == s ) return next[base+a];
  else return nextstate(default,a);
}

这个base 和check 数组怎么填？

flw2

有很多状态的转换表很相似, 比如说状态s1, s2,s3,假设区别仅仅在'a' (97) 上的转换,分别转换到 s4, s5, s6
看一下转换表:

tran[s1] = {....,  s4 ..}; //'a'
tran[s2] = {....,  s5 ..};
tran[s3] = {....,  s6 ..};

defualt[s1] = s1;
default[s2] = s1;
default[s3] = s1;


next[0 ... 257] = {.... s4..., s5, s6}, next[258 ..](防止越界用的) = -1;
check[0 ... 255] = {s1, ... s1, s2, s3}; check[258..] = -1;
base[s1] = 0;
base[s2] = 256-'a' = 159;
base[s3] = 257-'a' = 160;

base是根据next的空闲位置而计算出来的, 比如当1找到位置0的时候, check[0-255]都瞒了, 然后对于s2, 只有当pos = 159,才发现 base[159+'a'] = -1(空闲) ;然后设置s2的base,并改next,check分别为s5,s2

然后拿这个例子跟一下就知道了
nextstate(s, a)

317316abcd

明白了 感谢～～

317316abcd

我是之前问DFA压缩的，开始以为是看懂了，但回过头来还有些疑问

假设是这样一个DFS   end 和 else 是 关键字 假设endls={0,1,2,3,4}   
我想问的遇到这样怎么构建：check和base数组
base[3] 和 base[6]是否无所谓其大小？
只要让 check[base[3]+[0-4]] 不等于3就行吗？
default是否是设为7

谢谢 希望能收到答复


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