私は最近、遅延入力 DFA に関するディープ パケット インスペクションのための複数の正規表現マッチングを高速化するアルゴリズムの論文を読んでいます。
論文の補題 1 によると、DFA は対応する遅延入力 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
対応する遅延入力 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 と一致できます。
誰かが理由を教えてもらえますか?