Question

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?

Was it helpful?

Solution

Probably they're assuming that the transition function of the original DFA is total, by introducing an explicit error state if necessary. Your transition function f is undefined for (c, 2).

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top