Недетерминированные конечные автоматы

Приведённое в конце прошлого раздела доказательство корректности автомата Кнута-Морриса-Пратта было весьма сложным (и, мягко говоря, очень наброскообразным). Оказывается, обобщив понятие детерминированного автомата, можно кардинально упростить подобные доказательства.

Недетерминированные автоматы

Недетерминированным автоматом (далее НДА) называется отображение \(t:S\times A\to PA\), где \(PA\) — множество всех подмножеств множества \(A\). Результатом работы НДА (на начальном множестве \(S_0\) и тексте \(a\)) является последний элемент последовательности

\[ S_{n+1} = \cup \{ t(s)\,|\, s\in S_n \} \]

Результат работы НДА можно вычислить функцией

def run_nda(nda, s0, text):
    s = set(s0)
    for a in text: s = set([y for x in s for y in nda(x,a)])
    return s

Нетрудно заметить, что НДА можно превратить в ДА вида \(PS\times A\to PA\) функцией

def determinize_nda(nda):
    def da(s,a):
        return set([y for x in s for y in nda(x,a)])

    return da

Корректность автомата КМП

Теперь приведём простое (и существенно более формальное) доказательство корректности работы автомата КМП. Нам потребуется лишь одинарная индукция (по длине needle). Пусть \(T\) — ДКА для слова needle[:N-1], а также пусть \(Z\) — последний символ needle.

Рассмотрим НДА, определённый следующим образом:

\[ t(x,a) = \{ T(x,a) \},\; x \lt N-1 \]

\[ t(N-1,x) = \{ T(N-1,x) \},\; x\ne Z \]

\[ t(N-1,Z) = \{ T(N-1,Z), N \} \]

\[ t(N,x) = \{\} \]

Если этот автомат запустить на начальном состоянии \(\{0\}\), то про его результат очевидно, что искомая длина префикса является наибольшим из состояний результата.

При этом единственный результат, содержащий более одного состояния, выглядит как \(R=\{ T(N-1,Z), N \}\). Нетрудно заметить, что по символу x такое состояние переходит в \(t(T(N-1,Z),x)\). Поэтому, если мы назовём состояние R числом \(N\), мы получим детерминированный автомат

\[ t(x,a) = T(x,a),\; x \lt N-1 \]

\[ t(N-1,x) = T(N-1,x),\; x\ne Z \]

\[ t(N-1,Z) = N \]

\[ t(N,x) = t(T(N-1,Z), x) \]

Именно такой автомат и строится функцией kmp_dfa.