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

Question

我最近在读一篇论文 Algorithms to Accelerate Multiple Regular ExpressionsMatching for Deep Packet Inspection关于延迟输入 DFA。
根据论文中的引理1，DFA等价于对应的Delayed input 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

对应的Delayed input 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可以通过先使用空字符进入状态1然后匹配c来匹配c。
谁能告诉我为什么？

Answer 1

他们可能假设原始 DFA 的转换函数是完整的，必要时通过引入显式错误状态。您的转换函数 f 未定义 (c, 2)。