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

Ещё раз напомним, что детерминированным конечным автоматом (далее ДКА) называется произвольное отображение \(t:S\times A\to S\), для которого множества \(S\) и \(A\) конечны. Множество \(S\) называется множеством состояний автомата, а \(A\) — алфавитом.

Обработка текста

Пусть \(a=a_0a_1a_2\ldots\) — текст (то есть последовательность элементов множества \(A\)). По тексту и начальному состоянию \(s_0\) можно построить последовательность \(s_0s_1s_2\ldots\) по следующему правилу:

\[ s_{n+1} = t(s_n, a_n) \]

Последний элемент этой последовательности называется результатом работы автомата на тексте \(a\). Функция вычисления результата работы автомата может выглядеть, например, так:

def run_dfa(dfa, s0, text):
    s = s0
    for a in text: s = dfa(s, a)
    return s

Иногда начальное состояние \(s_0\) включают в понятие автомата, но мы это делать не будем.

Примеры автоматов

Поиск символа

При помощи конечного автомата можно тривиально определить, входит ли некоторый символ в текст:

def search_for_char_dfa(x):
    return (lambda s, a: (s or a == x))

У такого автомата два состояния: True и False.

Подсчёт количества символов

Можно подсчитать количество символов по какому-нибудь модулю:

def count_chars_modulo(x, n):
    def dfa(s, a):
        if a == x: return (s+1)%n
        return s

    return dfa

Можно также просто подсчитать количество символов (но такой автомат уже не будет конечным):

def count_chars(x, n):
    def dfa(s, a):
        if a == x: return s+1
        return s

    return dfa

Поиск последовательности

Вот такой автомат определяет, есть ли в тексте последовательность xy:

def find_xy(s, a):
    if s == 2: return s
    if s == 1:
        if a == 'y': return 2
        return 0

    if a == 'x': return 1
    return 0

Если автомат остановился в состоянии 2, это означает, что искомая последовательность присутствует в тексте.

Моделирование автомата словарём

Во всех вышеприведённых примерах автомат моделировался явными условными переходами. Для сколько-нибудь крупных автоматов такой способ, очевидно, неудобен. Существенно удобнее строить автомат по его графику, закодированному словарём:

def dfa_from_dict(d):
    return (lambda s,a: d[s][a])

Кодировка словарём, в частности, позволяет строить автомат из более простых, не жертвуя производительностью (построение автомата из нескольких функций приводит к неприятному эффекту линейной зависимости времени поиска состояния от количества использованных функций).

Автомат Кнута-Морриса-Пратта

В качестве иллюстрации процедуры последовательного построения автомата приведём распространённый алгоритм поиска подтекста внутри текста. А именно, построим автомат, который определяет, какой наидлиннейший префикс искомого текста совпадает с хвостом входного текста. Например, для искомого текста foobar и входного текста barfoo автомат должен выдать foo (ну или 3, если называть состояния длиной найденного префикса).

Интересное свойство такого автомата (в отличие от автоматов со схожими, но немного другими определениями) — его можно построить рекуррентным образом:

def kmp_add_char(kmp_dict, x):
    n = len(kmp_dict) - 1
    kmp_dict[n+1] = {}
    old = kmp_dict[n][x]
    kmp_dict[n][x] = n+1
    
    for a in kmp_dict[old]:
        kmp_dict[n+1][a] = kmp_dict[old][a]

def kmp_dfa(alphabet, needle):
    kmp_dict = {0:{}}
    
    for a in alphabet:
        kmp_dict[0][a] = 0

    for x in needle:
        kmp_add_char(kmp_dict, x)

    return dfa_from_dict(kmp_dict)

Корректность

Докажем, что этот автомат (если его запускать, начиная с состояния 0) удовлетворяет сформулированному нами определению. Точнее, приведём краткий набросок доказательства (аккуратное «лобовое» доказательство довольно сложно).

Будем вести индукцию по длине искомого текста. Предположим, что для всех текстов needle длины, меньшей \(N\), автомат kmp_dfa(alphabet,needle) делает то, что нужно (а именно, выдаёт самое большое k, для которого needle[:k] совпадает с хвостом входного текста).

Если \(N=0\), то наш автомат всегда выдаёт 0, что, очевидно, удовлетворяет его определению. Если \(N\gt0\), проведём индукцию по длине входного текста.

С пустым входным текстом всё хорошо. Если же в тексте есть хотя бы один символ, этот текст можно представить в виде T+x, где x — этот самый последний символ. По индуктивному предположению, обработав текст T, автомат остановится в состоянии, соответствующем наиболее длинному хвосту T, являющемуся префиксом needle. При этом автомат мог остановиться в одном из трёх состояний:

одно из первых \(N-2\) состояний
состояние \(N-1\)
состояние \(N\)

Посмотрим, как среагирует автомат на последний символ x. В первом случае мы находимся в пределах автомата для слова needle[:N-1], который по предположению внешней индукции делает то, что нужно. Во втором случае тоже всё хорошо: если x == needle[N-1], то мы перейдём в состояние \(N\); если же нет, то мы опять в пределах автомата для слова needle[:N-1].

Единственный нетривиальный случай — если мы сейчас в состоянии \(N\). Тут нужно разобрать два подслучая.

Подслучай первый: после обработки символа x длина префикса остаётся N. Но так бывает только тогда, когда needle состоит из одинаковых символов, равных x. Нетрудно проверить, что для такого автомата переход из состояния N по символу x ведёт в N.

Подслучай второй: длина префикса изменяется. Но тогда автомат должен остановиться в том же состоянии, в котором остановился бы автомат для needle[:N-1]. Отмотаем на два шага назад: мы окажемся в состоянии, отличном от N (и в том же, в котором бы остановился автомат для needle[:N-1]). А теперь обратно пройдём на два шага вперёд. По построению мы окажемся там же, где оказался бы автомат для needle[:N-1].

Всё.