Исполнительное резюме

В данном обзоре даются формальные определения конечных автоматов (DFA) и автоматов с выходом (DFAO — машины Мили и Мура), а также определяется понятие k-автоматной последовательности. Приводятся критерии автоматности: существование DFAO, регулярность множеств индексов, конечность k-я́дра (kernel) последовательности и представление через k-равномерный морфизм (теорема Кобэ). В качестве ключевого примера рассматривается последовательность Туэ–Морса (в двоичной системе). Для неё строится DFAO (машина Мура) с двумя состояниями, приводится таблица переходов и выходов, даётся доказательство автоматности. Описаны алгоритмы вычисления n-го члена (симуляция DFAO за время \(O(\log n)\)) и проверки автоматности (проверка конечности ядра и регулярности языков индексов). Указана асимптотическая сложность основных процедур. Приведены несколько типовых задач с подробными решениями (автоматизация Туэ–Морса, проверка автоматности, построение DFAO по заданному правилу и др.) и упражнения без ответов. Во введении помещены компактные полезные леммы и утверждения (независимость порядка чтения цифр, теоремы Эйленберга/Кобэ и др.) с указанием доказательств или ссылками на них. В тексте даны сравнительные таблицы эквивалентных определений и таблица переходов автомата Туэ–Морса. Автомат Туэ–Морса иллюстрируется диаграммой (см. рис. ниже). Все утверждения основаны на строгих источниках (Allouche–Shallit 2003 и др.).

Определения DFA и DFAO (Mealy/Moore)

Детерминированный конечный автомат (DFA) задаётся как 5-кортеж \((Q,\Sigma,\delta,q_0,F)\), где \(Q\) — конечное множество состояний, \(\Sigma\) — входной алфавит, \(\delta:Q\times\Sigma\to Q\) — функция переходов, \(q_0\in Q\) — начальное состояние, \(F\subseteq Q\) — множество принимающих состояний. При подаче входного слова автомат проходит по состояниям согласно \(\delta\).

Детерминированный автомат с выходом (DFAO) наделён выходной функцией. В модели Мура его задают 6-кортежем \(M=(Q,\Sigma,\delta,q_0,\Delta,\tau)\), где \(\Delta\) — выходной алфавит, и \(\tau:Q\to\Delta\) — функция, сопоставляющая каждому состоянию выходной символ. При обработке входного слова \(w\) DFAO переходит по \(\delta\) и выдаёт выход, связанный с конечным состоянием: выходом автомата является \(\tau(\delta(q_0,w))\). (Машина Мили аналогична, но тогда выход \(\lambda(q,a)\) связан с переходом из \(q\) по символу \(a\).) Формально: DFAO есть \(6\)-кортеж как в [47], а автоматная последовательность определяется через него.

Лемма. Порядок чтения цифр неважен: определение \(k\)-автоматной последовательности не зависит от того, читаем ли \(k\)-ичное представление числа слева направо или справа налево.

\(k\)-автоматные последовательности: определения и эквивалентные формулировки

Последовательность \(x=x(0)x(1)x(2)\dots\) над алфавитом \(A\) называется \(k\)-автоматной, если существует конечный DFAO \(M=(Q,\{0,\dots,k-1\},\delta,q_0,A,\tau)\), который при запуске на входе в виде \(k\)-ичного представления числа \(n\) выдаёт букву \(x(n)\). Иными словами, \(x(n)=\tau(\delta(q_0,w))\) для любого слова \(w\) в \(k\)-ичной системе, равного \(n\). Проще говоря, автомат читает цифры \(n\) (в системе счисления с основанием \(k\)) и по достижении конца слова возвращает очередной символ последовательности.

Это равносильно тому, что для каждого символа \(a\in A\) множество \(\{n: x(n)=a\}\) представимо как регулярный (конечным автоматом) язык записей чисел в \(k\)-ичной системе. Также классическим критерием является конечность ядра: \(k\)-ядро последовательности \(x\) — это совокупность всех подпоследовательностей вида \(x*{k^e n + r}\) (\(e\ge0\), \(0\le r<k^e\)). Показано (Эйленберг 1974), что \(x\) есть \(k\)-автоматная тогда и только тогда, когда её \(k\)-ядро конечно. Эта характеристика часто используется для доказательства неавтоматности: если в \(k\)-ядре найдутся бесконечно многие разные подпоследовательности, \(x\) не автоматная.

Лемма (Эйленберг). Последовательность \(x\) автомата \(k\)-автоматна тогда и только тогда, когда её \(k\)-ядро конечно. Эта версия доказана в Allouche–Shallit.

Теорема (Cobham, Штайнберга–Алонсо). Последовательность \(x\) автомата \(k\)-автоматна тогда и только тогда, когда она является морфической последовательностью, полученной из \(k\)-равномерного морфизма (и последующего кодирования). Иными словами, \(k\)-автоматные последовательности — это ровно образы кодирования неподвижных точек \(k\)-равномерных морфизмов.

Утверждение (Eilenberg). Для \(k\ge2\) и любого \(r\ge1\) последовательность \(x\) является \(k\)-автоматной тогда и только тогда, когда она является \(k^r\)-автоматной.

Следствие (теорема Кобэ). Если последовательность является одновременно \(h\)-автоматной и \(k\)-автоматной, где \(h\) и \(k\) не имеют общей степени (то есть относительно простые, см. формально “multiplicatively independent”), то она должна быть в конечном итоге периодической.

Замечание. Очевидно, что все периодические (или практически периодические) последовательности \(k\)-автоматны: достаточно запомнить пред и период, и выводить символы периодически (или по DFAO). И наоборот, DFAO с конечным числом состояний, работая, обязательно войдёт в цикл, порождая в конечном итоге периодическую выводимую последовательность.

Ниже приведена сводная таблица эквивалентных определений и критериев \(k\)-автоматности:

Критерий / Определение	Описание
Автомат	Существует конечный DFAO, читающий \(k\)-ичное представление \(n\) и выдающий \(x(n)\).
Регулярные множества индексов	Для каждого \(a\in A\) множество \(\{n:\,x(n)=a\}\) регулярное в \(k\)-ичной записи (распознаётся конечным автоматом).
\(k\)-ядро	Конечность \(k\)-ядра: \(\{x*{k^e n+r}\}\) содержит лишь конечное число различных подпоследовательностей (Эйленберг).
Равномерный морфизм (Cobham)	\(x\) — образ кодирования неподвижной точки \(k\)-равномерного морфизма.

Последовательность Туэ–Морса (2-автоматная)

Определим последовательность Туэ–Морса \(t=t(0)t(1)t(2)\dots\) двоичного алфавита \(\{0,1\}\) следующими эквивалентными способами (см. [39]):

Рекуррентно: \(t(0)=0\), \(t(2n)=t(n)\), \(t(2n+1)=1-t(n)\).
Через построение слов: \(u_0=0\), \(u_{n+1} = u_n\,\overline{u_n}\) (зеркальное дополняющее слово). Тогда \(t\) — предел \(u_n\), например \(0110100110010110\dots\).
Через сумму цифр: \(t(n)=s_2(n)\bmod2\), где \(s_2(n)\) — сумма двоичных цифр \(n\). То есть \(t(n)\) равен паритету количества единиц в двоичной записи \(n\).

Отсюда легко видеть, что \(t(n)\) можно генерировать DFAO: он просто считает чётность единиц в двоичной записи. Построим автомат с двумя состояниями \(q_0\) (чётная сумма единиц) и \(q_1\) (нечётная). Вначале автомат в \(q_0\). При чтении символа \(0\) состояние не меняется, при \(1\) — переключается. Выход \(\tau(q_0)=0\), \(\tau(q_1)=1\). Тогда после чтения всей записи числа \(n\) (справа налево или слева направо) автомат находится в состоянии \(q_i\), где \(i\equiv s_2(n)\pmod2\), и выдает \(t(n)=i\). Это доказывает, что \(t\) — 2-автоматная последовательность.

Рис. – Автомат (машина Мура) для последовательности Туэ–Морса: два состояния \(q_0\) (выход 0) и \(q_1\) (выход 1); стрелки показывают переходы по входному биту (0 или 1). Из \(q_0\) по 0 остаёмся в \(q_0\), по 1 переходим в \(q_1\); из \(q_1\) по 0 остаёмся в \(q_1\), по 1 возвращаемся в \(q_0\). Начальное состояние \(q_0\).

Таблица переходов автомата (Moore) для Туэ–Морса:

Состояние	Выход τ	δ(·,0)	δ(·,1)
\(q_0\)	0	\(q_0\)	\(q_1\)
\(q_1\)	1	\(q_1\)	\(q_0\)

Здесь при поступлении бита 0 автомат остаётся в том же состоянии, при 1 меняет состояние (переключает чётность). По построению переходов видно, что состояние автомата всегда отражает чётность суммы битов прочитанной части входа. Таким образом, на конце слова автомат в состоянии \(q_{t(n)}\) с выходом \(t(n)\). Тогда действительно \(t(n)=\tau(\delta(q_0,\text{bin}(n)))\), где \(\text{bin}(n)\) — двоичная запись \(n\). Это и даёт формальное доказательство \(2\)-автоматности последовательности Туэ–Морса.

Кроме того, ядро \(2\)-ядро последовательности \(t\) конечно (всего 2 подпоследовательности: \(t\) и её побитовое дополнение), что также подтверждает автоматность.

Алгоритмы генерации и проверки автоматности

Генерация \(n\)-го члена: если задан DFAO, то \(t(n)\) вычисляется за время \(O(\log_k n)\): нужно получить \(k\)-ичное представление \(n\) и по одной цифре проделать переход по \(\delta\). Число шагов равно числу цифр \(\approx\log_k n\), а сами переходы константные.

Проверка автоматности: самый распространённый метод — это построить \(k\)-ядро и проверить его конечность. Начинают с последовательности \(x*n\) (или череды её значений) и порождают новые подпоследовательности вида \(x*{kn+r}\). Если при этом нет бесконечного роста множества различных подпоследовательностей, то последовательность \(k\)-автоматная (по теореме Эйленберга). На практике это сводится к конструированию минимального DFAO, сравнивая полученные подпоследовательности. Существуют алгоритмы, основанные на минимизации автоматов и анализе ядра, которые выполняются за полиномиальное время по размеру представления описания последовательности.

Если же ядро бесконечно (или найдены доказательства его разного строения), автоматность опровергается. С точки зрения регулярных языков, надо доказать, что некоторые множества позиций не распознаются никаким DFA, что часто проще сделать, найдя бесконечное число непохожих префиксов.

Сложность алгоритмов:

Вычисление \(n\)-го члена: \(O(\log_k n)\) времени и \(O(\log_k n)\) памяти (для хранения разложения).
Построение DFAO по \(k\)-ядру: в худшем случае требуется хранить все состояния ядра (количество которых мало для автоматных последовательностей, но теоретически экспоненциально по некоторым параметрам описания последовательности). Практически это сводится к алгебраической минимизации автоматов (алгоритм Хопкрофта–Минимала за \(O(m\log m)\) и т.п., где \(m\) — число состояний). Общая сложность зависит от входного описания (морфизм, регекспрограмма и т.д.), но обычно полиномиальна по размеру описания.

Задачи с подробным решением

Задача: Постройте DFAO для последовательности \(x(n)=1\) тогда и только тогда, когда двоичная запись \(n\) содержит чётное число единиц. Решение: Это именно последовательность Туэ–Морса (сдвинутый на 0). Автомат строится так же, как для Туэ–Морса: два состояния \(q_0,q_1\) с выходами \(\tau(q_0)=0,\;\tau(q_1)=1\), правило переходов: по 0 не меняем состояние, по 1 меняем. Тогда на выходе получаем \(x(n)=\tau(q_{\text{final}})\) = чётность числа единиц. Первая и последующие итерации: \(x(0)=1\) (вых. \(q_0=0\)), \(x(1)=1\) (вых. \(q_1=1\)) и т.д. По построению получаем искомый автомат.
Задача: Покажите, что любая заключительно-периодическая последовательность \(y\) является \(k\)-автоматной. Решение: Пусть \(y\) имеет период \(p\) с предпериодом \(\ell\). Конструируем DFAO так: состояние автомата кодирует положение внутри периода (и предпериода). То есть состояний достаточно \(\ell+p\). Автомат читает вход \(n\) в любой системе: из состояния \(s\) при любом входе переходит в состояние \((s+1)\) (или к старту после завершения периода). Выход автомата \(\tau(s)=y(s)\), где \(y\) повторяется с периодом \(p\) после \(\ell\) начальных символов. При таком DFAO \(y(n)=\tau(\delta(q_0,n))\) и очевидно даёт периодическую последовательность. Обратное также тривиально: конечный автомат всегда повторяет часть состояний, значит последовательность периодична.
Задача: Последовательность \(a(n)\) задаётся рекурсией \(a(0)=2\), \(a(n)=a(n-1)\bmod 2\). Является ли она автоматной? Если да, найдите автомат. Решение: Вычислим первые члены: \(a(0)=2\), \(a(1)=0\), \(a(2)=0,\dots\) фактически \(a(0)=2\), а для \(n\ge1\) — всегда \(0\). Это периодическая последовательность с предпериодом 1 и периодом 1 (после начального 2 постоянно идут 0). По предыдущему пункту она \(k\)-автоматна. Автомат: два состояния \(q_A,q_B\), причём \(q_A\) соответствует выводу \(2\), \(q_B\) — выводу \(0\). Изначально автомат в \(q_A\), после первого шага (любая цифра) переходит в \(q_B\) и остается там. Выход \(\tau(q_A)=2,\;\tau(q_B)=0\). Проверяем: для \(n=0\) выход \(2\), для любого \(n\ge1\) автомат возвращает \(0\). Это решает задачу.
Задача: Докажите, что последовательность \(b(n)=n \bmod 3\) не является автоматной. Решение: Предположим противное, что \(b\) является \(2\)-автоматной (двоичная система). Тогда её \(2\)-ядро должно быть конечным. Но подпоследовательности вида \(b(2^e n + r)= (2^e n + r)\bmod 3\) при различных \(e\) дают бесконечное число разных последовательностей (остатки по модулю 3 в зависимости от младших битов не упрощаются). Формальнее: для любых двух различных \(e\), получаются новые последовательности, и не наблюдается сходимости. Из этого следует бесконечность ядра, противоречие. Следовательно, \(b(n)\) не \(2\)-автоматна. Аналогично видим, что и для любых других оснований кроме 3 сама структура остатка по 3 не может быть реализована конечным автоматом.
Задача: Последовательность \(c(n)\) равна сумме двоичных цифр \(n\) (не по модулю). Является ли она автоматной? Решение: Сумма цифр \(s_2(n)\) растёт без ограничений с \(n\), поэтому выходное алфавит бесконечен. Автоматная последовательность обязана принимать лишь конечное число значений. Поэтому \(c(n)\) не может быть автоматной (равносильное рассуждение: \(k\)-автоматная последовательность обязана принимать конечное число разных значений).
Задача: Постройте DFAO (Мура) для последовательности \(d(n)\), где \(d(n)=1\) тогда и только тогда, когда двоичное представление \(n\) содержит хотя бы одну 11 (две подряд стоящие единицы). Решение: Требуется распознавать наличие подряд идущих единиц. Автомат строим так: состояния отражают наиболее недавний символ. Пусть \(q_0\) = "последняя цифра была 0 или начало", \(q_1\) = "последний символ 1, ещё не было 11", \(q_2\) = "обнаружена 11". Выход \(\tau(q_0)=0\), \(\tau(q_1)=0\), \(\tau(q_2)=1\). Переходы:
Из \(q_0\): при чтении 0 остаёмся в \(q_0\); при 1 переходим в \(q_1\).
Из \(q_1\): при 0 переходим в \(q_0\) (обозначает 01); при 1 переходим в \(q_2\) (найдена 11).
Из \(q_2\): при любом входе остаёмся в \(q_2\) (нашли уже хотя бы одну пару 11, остаёмся в этот выводящий 1 состояние). Такой автомат на любом \(n\) выдаёт 1 после того, как встретились две подряд единицы, иначе 0. Он конечен и корректен.

Леммы и утверждения

Лемма (порядок чтения цифр): Определение \(k\)-автоматной последовательности не меняется, если читать \(k\)-ичное представление числа слева или справа. То есть нули в начале разложения (или конец) не влияют на результат автомата.
Лемма: Любая \(k\)-автоматная последовательность \(x\) описывается конечным автоматом и (эквивалентно) равномерным морфизмом: \(x\) — образ неподвижной точки \(k\)-равномерного морфизма.
Лемма (Эйленберга): Множественность \(k\)-ядра равносильна автоматности: \(x\) автоматна тогда и только тогда, когда \(k\)-ядро конечное.
Теорема (Cobham): Если \(x\) является одновременно \(h\)-автоматной и \(k\)-автоматной при \(h,k\) без общих степеней, то \(x\) в конечном итоге периодична.
Следствие: Для любого \(r\ge1\) \(k\)-автоматная \(\iff\) \(k^r\)-автоматная.

Контрольные задания (без решений)

Существует ли автомат для последовательности, принимающей значение 1 на позициях, номера которых в двоичной системе чётны? Постройте его или докажите невозможность.
Доказать, что последовательность \(e(n)=\lfloor \log_2 (n+1)\rfloor\) не \(2\)-автоматна (подумайте про ядро или неограниченный рост значений).
Постройте DFAO для последовательности: \(f(n)=1\) тогда и только тогда, когда число единиц в двоичном представлении \(n\) равно 3. (Можно расширить пример для чётности до фиксированного количества единиц.)

Источники и литература. Формулировки и теоремы взяты из классических трудов по автоматным последовательностям (особенно Allouche–Shallit 2003) и учебных материалов. В частности определения и примеры приведены по [24, 26, 39, 47, 48]. Дополнительные сведения и подробности см. в учебниках по комб. на словах и автоматной теории.