Конечный автомат: вычисление, которому хватает одного состояния

Если ты построишь таблицу переходов по описанию языка, проведёшь по ней строку и объяснишь, что именно автомат помнит, - листай до «Теперь сам».

Как думаешь, сколько нужно помнить, чтобы проверить делимость на три

По каналу приходит двоичная запись числа, цифра за цифрой, старшие разряды первыми. Число может быть длиной в миллиард цифр. В конце нужно сказать, делится ли оно на три.

Ответь себе до чтения: сколько памяти для этого нужно - пропорционально длине числа, логарифм длины или постоянное количество, не зависящее от длины вовсе? Постоянное, и очень маленькое: одно из трёх значений. Само число помнить не нужно - достаточно его остатка от деления на три, а остаток пересчитывается по одной цифре.

На что это похоже

Турникет в метро. У него два состояния: закрыт и открыт. Событий тоже два: приложили карту и прошёл человек. Закрытый турникет от карты открывается, открытый после прохода закрывается; всё остальное его не меняет. Турникет не помнит, сколько людей прошло за день, кто именно прошёл и в каком порядке, - только то, закрыт он сейчас или открыт.

Вся его «программа» - таблица из четырёх клеток. Конечный автомат - это турникет, у которого состояний может быть больше двух, а событиями служат символы строки.

Механизм: состояния, таблица и принимающие

Алфавит - конечный набор символов, например {0, 1} или {a, b}. Строка - конечная последовательность символов алфавита; пустая строка, в которой символов нет, тоже строка. Язык - любое множество строк: «двоичные записи чисел, кратных трём», «строки, содержащие ab».

Детерминированный конечный автомат, коротко ДКА, состоит из пяти вещей:

состояния              конечный набор, например {0, 1, 2}
алфавит                символы, которые автомат умеет читать
функция переходов      таблица: (состояние, символ) → состояние,
                       заполнена целиком
начальное состояние    одно
принимающие состояния  какие-то из состояний, возможно ни одного

Работа: автомат стоит в начальном состоянии, читает символ, по таблице переходит в новое состояние, читает следующий - и так до конца строки. Если последнее состояние принимающее, строка принята, иначе отвергнута. Слово «детерминированный» значит, что следующий шаг определён однозначно: в каждой клетке таблицы ровно одно состояние.

Язык автомата - множество всех строк, которые он принимает. Язык называется регулярным, если какой-нибудь ДКА принимает все его строки и никаких других.

Таблица для делимости на три получается из одного наблюдения. Пусть прочитанная часть - число x с остатком r. Дописать справа цифру b - значит получить число 2x + b: старое сдвинулось на разряд и удвоилось. Запишем x = 3m + r. Тогда 2x + b = 6m + 2r + b, а 6m делится на три и на остаток не влияет. Значит, остаток нового числа равен (2r + b) mod 3: он зависит только от r и b, а не от самого x. В таблице первое число в скобках - это 2r:

остаток r   пришёл 0: (2r + 0) mod 3     пришла 1: (2r + 1) mod 3
   0        (0 + 0) mod 3 = 0            (0 + 1) mod 3 = 1
   1        (2 + 0) mod 3 = 2            (2 + 1) mod 3 = 0
   2        (4 + 0) mod 3 = 1            (4 + 1) mod 3 = 2

Состояние - это остаток; начальное - 0, потому что прочитанного пока нет; принимающее - тоже 0.

Правило

ДКА задаётся конечным набором состояний, алфавитом, полной таблицей переходов, начальным состоянием и набором принимающих состояний. Он принимает строку, если, прочитав её символ за символом по таблице, оказывается в принимающем состоянии. На строку длины n уходит ровно n переходов. Память самого автомата постоянна: кроме входа, который только читается, он хранит одно число - номер состояния. Язык регулярен, если существует ДКА, который принимает его строки и только их.

Разбор: делимость на три

Таблица записана списком: perehody[q][b] - куда идти из состояния q по цифре b. Для проверки рядом печатается само число: int(stroka, 2) переводит двоичную запись в число.

perehody = [[0, 1], [2, 0], [1, 2]]

def prinimaet(stroka):
    q = 0
    for simvol in stroka:
        q = perehody[q][int(simvol)]
    return q == 0

for stroka in ["0", "11", "110", "111", "1001", "10101", "11111111"]:
    print(stroka, int(stroka, 2), prinimaet(stroka))

0 0 True
11 3 True
110 6 True
111 7 False
1001 9 True
10101 21 True
11111111 255 True

Числа 0, 3, 6, 9, 21 и 255 кратны трём и приняты, 7 отвергнуто. Весь алгоритм - одна строка в цикле, и она не зависит от длины числа: миллиард цифр обрабатывается миллиардом обращений к таблице из шести клеток. Перевод в число здесь стоит только ради печати; сам автомат чисел не складывает и не делит.

Проведём строку 1001 руками: 0 → 1 → 2 → 1 → 0. Сначала остаток 0; пришла единица - стало число 1, остаток 1; пришёл ноль - число 2, остаток 2; ещё ноль - число 4, остаток 1; единица - число 9, остаток 0.

Разбор: поиск подстроки и что автомат не может помнить

Автомат, принимающий строки из букв a и b, в которых встречается ab. Состояния названы по смыслу: zhdu - буквы a перед текущим местом нет; videl_a - только что была a; nashyol - подстрока уже встретилась; оно одно и есть принимающее. Функция печатает весь путь по состояниям, а принята ли строка, видно по последнему состоянию пути.

avtomat = {}
avtomat["zhdu"] = {"a": "videl_a", "b": "zhdu"}
avtomat["videl_a"] = {"a": "videl_a", "b": "nashyol"}
avtomat["nashyol"] = {"a": "nashyol", "b": "nashyol"}

def put(stroka):
    q = "zhdu"
    sled = [q]
    for simvol in stroka:
        q = avtomat[q][simvol]
        sled.append(q)
    return sled

print(put("bbaab"))
print(put("bbba")[-1], put("aaaa")[-1], put("")[-1])

['zhdu', 'zhdu', 'zhdu', 'videl_a', 'videl_a', 'nashyol']
videl_a videl_a zhdu

Строка bbaab принята на последнем символе. Строки bbba, aaaa и пустая заканчиваются не в nashyol и отвергнуты. Состояние nashyol - ловушка: так называют состояние, из которого нет выхода. Эта ловушка принимающая, и это правильно: найденная подстрока никуда не денется. Такой же автомат, только с числом состояний по длине образца, строился в разделе про строки для поиска без возвратов.

Теперь граница модели. Состояние - единственное, что автомат знает о прочитанном. В состоянии videl_a он не знает, сколько букв было до этого, и не может узнать: строки a, ba и bbbbba для него неразличимы. Пока для ответа достаточно различать конечное число ситуаций - «остаток 0, 1 или 2», «видел a или нет», - автомат справляется. Если ситуаций бесконечно много - например, нужно помнить, сколько именно букв a прошло, чтобы потом сравнить с числом букв b, - состояний не хватит ни при каком их количестве. Четвёртый урок главы превращает это наблюдение в доказательство.

Что ломается без этого

Таблица заполнена не целиком. Если для какой-то пары «состояние, символ» перехода нет, автомат на такой строке не определён. В настоящем ДКА каждая клетка заполнена; для «невозможных» продолжений заводят ещё одну ловушку, на этот раз отвергающую: она не принимающая, и все переходы из неё ведут в неё же.

В состояние пытаются положить счётчик. «Состояние - сколько скобок сейчас открыто» перестаёт быть конечным автоматом в тот момент, когда глубина не ограничена. Если ограничена - скажем, не больше 10, - это честный автомат с одиннадцатью состояниями и ловушкой.

Принятие проверяют по ходу, а не в конце. Автомат для «число кратно трём» проходит через состояние 0 много раз; значение имеет только то, где он оказался после последнего символа.

Пустую строку забывают. Если начальное состояние принимающее, пустая строка принята. В разборе с остатками так и есть: пустая запись трактуется как ноль.

Зачем это в работе

Разбор текста на слова. Первый этап любого компилятора и интерпретатора - лексический анализ: поток символов режется на числа, имена, знаки операций. Каждый вид слов описывается небольшим автоматом, и вместе они работают за один проход без возвратов.

Протоколы и интерфейсы. Соединение TCP, заказ в магазине, форма с шагами - всё это объекты с конечным числом состояний и разрешёнными переходами между ними. Записать их таблицей автомата - значит сразу увидеть забытые клетки: что делать, если оплата пришла для уже отменённого заказа.

Проверка формата на лету. Данные идут потоком, памяти мало, а нужно отвергнуть неправильные: номер, дата, строка журнала. Автомат даёт ответ за один проход и постоянную память, как потоковые алгоритмы прошлого раздела, только без всякой случайности.

Теперь сам

1. Проведи строку 1011 по таблице делимости на три. В каком состоянии закончит автомат и чему равно число?
2. Построй ДКА над алфавитом {0, 1} для языка «в строке чётное число единиц». Сколько состояний нужно?
3. Какой будет таблица переходов автомата для делимости двоичного числа на пять? Сколько в ней состояний?
4. Автомат из второго разбора прочитал abab. Выпиши путь по состояниям.
5. Язык - все строки из букв a и b длины не больше двух. Сколько состояний у ДКА для него, считая ловушку?