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?