我最近在读一篇论文 Algorithms to Accelerate Multiple Regular Expressions
Matching 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。
谁能告诉我为什么?
最佳答案
他们可能假设原始 DFA 的转换函数是完整的,必要时通过引入显式错误状态。您的转换函数 f
未定义 (c, 2)
。
关于algorithm - 为什么 DFA 等同于延迟输入 DFA,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17786707/