Domanda

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?

È stato utile?

Soluzione

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).

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top