0

I'm recently reading a paper Algorithms to Accelerate Multiple Regular Expressions Matching for Deep Packet Inspection about Delayed input DFA.
According to Lemma 1 in the paper, DFA is equivalent to the corresponding Delayed input DFA. But consider a counter example below:
Let f(i, s) denote the transition function, where s is the current state and i is the input character.
DFA:

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

The corresponding Delayed input DFA:

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

Then the original DFA can't match the character c from state 2 while the Delayed input DFA can match c by first go to state 1 using the null character and then match c.
Can somebody tell me why?

4

1 回答 1

1

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

于 2013-07-22T12:14:30.850 回答