为什么DFA等同于延迟输入DFA

Question

我最近读了一篇关于延迟输入Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection的论文。

根据文中引理1，DFA等价于相应的延迟输入DFA。但请考虑下面的反例：

设f(i，s)表示转移函数，其中s是当前状态，i是输入字符。

DFA：

f(a, 1) = 3, f(b,1) = 3, f(c, 1) = 3, f(a, 2) = 3, f(b, 2) = 3

对应的延迟输入DFA：

f(a, 1) = 3, f(b, 1) = 3, f(c, 1) = 3, f(null, 2) = 1 (null means the default transition) 

则原始DFA不能匹配来自状态2的字符c，而延迟的输入DFA可以匹配c，方法是首先使用空字符转到状态1，然后匹配c。

有人能告诉我为什么吗？

Answer 1

可能他们假设原始DFA的转换函数是总的，如果必要的话，通过引入一个显式的错误状态。未为(c, 2)定义您的转换函数f。