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

В этом справочном пособии даются точные определения и основные свойства автоматных последовательностей (k-автоматных последовательностей) и автоматных множеств. Показывается эквивалентность разных формулировок (через ДКА с выходом, k-регулярность ядра, k-равномерные морфизмы и т.д.). Приводятся классические примеры (последовательность Туэ–Морса, периодические последовательности, сумма цифр, Фибоначчиево слово и др.) и их свойства. Формулируется и доказывается теорема Кобхэма: если последовательность одновременно k- и ℓ-автоматна при независимых основаниях k,ℓ, то она (с точностью до конечного вступления) периодична. Отмечаются условия применимости теоремы и контрпримеры (например, при зависимых основаниях или для неограниченных последовательностей). В приложении приведены типовые задачи по проверке автоматности и построению автоматов с подробными решениями.

Основные определения и эквивалентные формулировки

• Детерминированный конечный автомат с выходом (DFAO) – шестёрка \(M=(Q,\Sigma,\delta,q_0,\Delta,\tau)\), где \(Q\) – множество состояний, \(\Sigma\) – входной алфавит (обычно \(\{0,1,\dots,k-1\}\)), \(\delta:Q\times\Sigma\to Q\) – функция перехода, \(q_0\) – начальное состояние, \(\Delta\) – выходной алфавит, \(\tau:Q\to\Delta\) – функция выхода. При чтении слова \(w\in\Sigma^*\) автомат переходит по функции \(\delta\) к некоторому состоянию, а затем выдаёт символ \(\tau(q)\).

• Представление числа в основе \(k\): для натурального \(n\) его запись в системе счисления основания \(k\) без ведущих нулей обозначим \(\langle n\rangle_k\) (последовательность цифр).

• \(k\)-автоматная последовательность: бесконечную последовательность \(x=(x*n)_{n\ge0}\) над конечным алфавитом \(B\) называют \(k\)-автоматной, если существует DFAO \(M=(Q,\{0,1,\dots,k-1\},\delta,q_0,B,\tau)\) такой, что при любом \(n\ge0\) выходом автомата на входе \(\langle n\rangle_k\) является \(x*n\). Формально, \(x*n=\tau(q_0\cdot \langle n\rangle_k)\), где \(q_0\cdot w\) означает состояние, в которое автомат переходит, считав слово \(w\) от начального состояния.

• \(k\)-распознаваемое (автоматное) множество: подмножеству \(X\subseteq\mathbb{N}\) ставят в соответствие его характеристическую последовательность \(1_X(n)=1\) если \(n\in X\), иначе \(0\). Множество \(X\) называют \(k\)-распознаваемым, если язык записей \(\{\langle n\rangle_k:n\in X\}\) регулярный, т.е. распознаётся конечным автоматом. Тогда характер. посл. \(1_X(n)\) – \(k\)-автоматная. Обратное тоже верно: для любой \(k\)-автоматной \((x*n)\) каждое множество \(\{n\mid x*n=b\}\) является \(k\)-распознаваемым.

• Mорфическая последовательность: положим \(\sigma: A^*\to A^*\) – морфизм и \(\tau:A\to B\) – кодирование. Если \(\sigma\) \(k\)-равномерный (т.е. \(|\sigma(a)|=k\) для всех \(a\in A\)) и существует буква \(a\in A\), на которой \(\sigma\) продолжимо (\(\sigma(a)=au\)), то предельное слово \(\sigma^\infty(a)\) есть фиксированная точка. Тогда слово \(\tau(\sigma^\infty(a))\) называется чистой морфической. Теорема Кобхэма (1969) устанавливает, что всякая \(k\)-автоматная последовательность представляется именно таким образом.

• \(k\)-ядро последовательности: \(k\)-ядро \((x*n)\) – множество подпоследовательностей вида \((x*{k^e n+r})_{n\ge0}\) при всех \(e\ge0\), \(0\le r<k^e\). Eilenberg (1974) доказал: \(x\) – \(k\)-автоматна тогда и только тогда, когда \(k\)-ядро конечна.

• \(k\)-регулярные последовательности: обобщая понятие, говорят, что целочисленная последовательность \(s(n)\) является \(k\)-регулярной, если \(\mathbb{Q}\)-пространство, порождённое её \(k\)-ядром, конечно-мерно. Класс \(k\)-регулярных последовательностей включает \(k\)-автоматные; пример: сумма цифр \(s_k(n)\) – \(k\)-регулярна, но не \(k\)-автоматна (иначе по конечности образа последнего неограниченность невозможна).

• Периодические и почти-периодические последовательности: слово \(x\in A^\omega\) в конечном счёте периодично (конечнопериодично), если \(x=uv^\omega\) для конечных слов \(u,v\), \(v\neq\varepsilon\). Если \(u=\varepsilon\), то \(x\) периодично с периодом \(|v|\). Множество \(X\subseteq\mathbb{N}\) конечно-периодично, если есть такое \(N,p>0\), что для всех \(n>N\) выполняется \(n\in X\iff n+p\in X\). Любое такое множество есть конечное объединение прогрессий.

Основные примеры

• Периодические последовательности: тривиально \(k\)-автоматны при любом \(k\), так как можно построить DFAO по периоду. Например, \(x*n=n\bmod m\) или характеристическая функция прогрессии \(a+mp\) описываются автоматом с \(p\) состояниями. (См. Задачу 6).

• Последовательность Туэ–Морса: \(t_n\) задана как чётность суммы двоичных цифр \(n\) (либо рекуррентно \(\sigma:0\to01,\;1\to10\), \(t=\lim\sigma^n(0)\)). Это классический пример 2-автоматной последовательности. Её DFAO имеет два состояния: \(q_0\) (выход 0, «чётное количество единиц»), \(q_1\) (выход 1, «нечётное»). Переходы: из \(q_0\) по входу 0 остаётся \(q_0\), по 1 – переходит в \(q_1\); из \(q_1\) по 0 – \(q_1\), по 1 – \(q_0\) (см. рисунок). Таким образом \(t_n=(\text{число единиц в }n)_2\bmod2\), и \(t\) не является периодической, но 2-автоматна.

Пример DFAO для последовательности Туэ–Морса \(t_n\) (паритет единиц в двоичном представлении \(n\)): два состояния \(q_0\) (выход 0) и \(q_1\) (выход 1), переходы по цифрам 0,1.

• Другие примеры автоматных последовательностей: • Регулярная бумажная фальцевка (paperfolding) – 2-автоматна (фикс. точка подходящего 2-морфизма). • Последовательности Прюфера–Туэ–Морса (сумма цифр по основанию 3, модуля 2) – 3-автоматны. • Периодические, конечнопериодические – автоматны при любом \(k\). • Стреманные (Струмовые) последовательности (Fibonacci-word, битовые слова, порожд. поворотами окружности) – обычно не автоматны (их комплексность \(n+1\) и неподдаётся конечным автоматикам). • Сумма цифр \(s_k(n)\) (в осн. \(k\)) – \(k\)-регулярна, но не \(k\)-автоматна (ее значения не ограничены, а \(k\)-автоматные последовательности над конечным алфавитом – ограничены по образу). • Последовательность правой границы Фибоначчи (возвращение чисел Фибоначчи) – не автоматна. • Регулярные последовательности – обобщают автоматные (например, \(n\mapsto n^d\) – \(k\)-регулярны).

Основные свойства

• Эквивалентные описания: – Морфическая формулировка (Кобхэм, 1969): \(x\) – \(k\)-автоматна \(\iff\) существует \(k\)-равномерный морфизм \(\sigma\) и кодирование \(\tau\) с фикс. точкой \(x=\tau(\sigma^\infty(a))\). – Ядро: \(x\) – \(k\)-автоматна \(\iff\) \(k\)-ядро \((x*{k^en+r})\) конечно (всего конечное число подпоследовательностей). – Логический подход: множество \(X\subseteq\mathbb{N}\) распознаётся автоматом в системе счисления \(k\) \(\iff\) оно описывается формулой в логике первого порядка с предикатом \(V_k(n)=k^e\) (например, по теореме Бюхи).

• Замкнутость: Класс \(k\)-автоматных закрыт относительно кодирований, конечных морфизмов, сумм, произведений, проекций и др. (см. Allouche–Shallit). В частности, если \(x\) – \(k\)-автоматна, то и \(x\) – \(k^m\)-автоматна при любом \(m\in\mathbb{N}\) (перегруппировка цифр) и при любом \(m\) таким, что \(k^m>1\).

• Ограниченность и сложность: Любая \(k\)-автоматная последовательность над конечным алфавитом принимает лишь конечное число значений и имеет линейную сложность факторов \(p(n)=O(n)\). Следовательно, последовательности со сверхлинейной сложностью или неограниченными значениями не могут быть автоматными.

• Соотношение с \(k\)-регулярностью: Любая ограниченная \(k\)-регулярная последовательность – \(k\)-автоматна (так как тогда её \(k\)-ядро лежит в конечномерном \(\mathbb{Q}\)-пространстве, т.е. лишь конечное число комбинаций). Обратно, \(k\)-автоматная последовательность – \(k\)-регулярна по определению. Пример: \(a_n=\sum\) цифр \(n\) (в двоичном) – 2-регулярна, но не 2-автоматна.

• Примеры отрицательных случаев: • Против примеры (зависимые основания): если \(k,l\) не мультипликативно независимы (например, 2 и 4), то существуют последовательности, автоматные в обеих системах и непериодические. Например, последовательность Туэ–Морса (2-автоматна) автоматически является и 4-автоматной (т.к. 2- и 4-автоматность эквивалентна при 4=2^2) – и она не периодична. Так что условие независимости оснований в теореме Кобхэма обязательно. • Неприменимость Кобхэма вне натуральных оснований: теорема касается только натуральных оснований \(k\ge2\). Для обобщённых систем счисления (например, фибоначчиевых) существуют аналоги, но за пределами классической постановки.

Теорема Кобхэма и её доказательство

Теорема (Кобхэм, 1969): Пусть \(k,\ell\ge2\) – два натуральных числа, взаимно простых в смысле: нет \(m,n>0\) таких, что \(k^m=\ell^n\). Тогда бесконечное слово \(x=(x*n)_{n\ge0}\) над конечным алфавитом является одновременно \(k\)- и \(\ell\)-автоматным тогда и только тогда, когда оно в конечном счёте периодично (т.е. \(x=uvvv\cdots\)). Эквивалентная формулировка для множеств: множество \(X\subseteq\mathbb{N}\) одновременно \(k\)- и \(\ell\)-распознаваемо \(\iff\) \(X\) – объединение конечного числа арфим. прогрессий (конечнопериодично).

Доказательство (идея). Доказательство Кобхэма технически трудоёмкое (см., например, изложение в [57], [38]). Основной ход следующий. Легко показать, что если слово \(x\) конечно-периодично, то его запись регулярна в любой системе (см. замечание в [57] или стандартное построение DFA для объединения прогрессий). Сложная часть – обратное: показать, что непериодическая \(x\), автоматная в двух независимых системах, ведёт к противоречию. Подход Бюхи-Кобхэма использует логику (теория \(\langle\mathbb{N},+,\;V_k\rangle\)), где распознаваемость в каждой системе кодируется предикатом \(V_k(n)=\max\{k^e\mid k^e\mid n\}\). Мульт. независимость \(k,\ell\) гарантирует иррациональность \(\frac{\log k}{\log\ell}\) и применение теоремы Кронекера о равномерной плотности дробных частей. В результате доказывается, что автоматность в обеих системах накладывает на множество обнуляемых дробей строгие условия, которые возможны только при периодическом характере \(x\). Подробное доказательство см. в оригинальных статьях Кобхэма или обзорах.

Следствия:

• Сразу следует, что если \(x\) – \(k\)-автоматна и не периодична, то для любого \(\ell\) независимого с \(k\) \(x\) не может быть \(\ell\)-автоматной. Например, Туэ–Морс 2-автоматна и непериодична, значит она не может быть 3-автоматной (т.к. 2 и 3 независимы по Кобхэму).
• Любое конечнопериодическое множество \(X\) является \(k\)-распознаваемым при любых \(k\) (достаточно объединить автоматы для отдельных прогрессий, см. выше).
• Если основания не независимы (например, \(k=p^a,\ \ell=p^b\)), то никаких ограничений: всякая \(k\)-автоматная автоматически \(\ell\)-автоматная (в частности, если \(\ell=k^m\)).

Ограничения: Теорема Кобхэма справедлива только при условии взаимной независимости \(k,\ell\). Иначе существуют нефиксированные автоматные последовательности. Кроме того, теорема не применима к несобственно автоматным описаниям (например, к конечнопериодической части, выходящей за рамки автоматности с конечным алфавитом).

Таблица свойств для примеров последовательностей

Задачи и решения

1. Проверка автоматности. Постройте DFAO, генерирующий последовательность \(x*n=t_n\), где \(t_n\) – последовательность Туэ–Морса (\(t_n=0\) если в двоичной записи \(n\) чётное число единиц, иначе \(1\)). Решение. Как отмечено, Туэ–Морс – классический пример 2-автоматной последовательности. Автомат \(M=(Q,\{0,1\},\delta,q_0,\{0,1\},\tau)\) строим так: \(Q=\{q_0,q_1\}\), \(q_0\) – начальное. Состояние \(q_0\) означает “прочитано чётное число единиц”, \(q_1\) – “нечётное”. Функция перехода: из \(q_0\) по символу «0» остаёмся в \(q_0\) (количество единиц не меняется), по «1» переходим в \(q_1\). Аналогично: из \(q_1\) по «0» остаться в \(q_1\), по «1» перейти в \(q_0\) (переключаемся чётность). Функция выхода: \(\tau(q_0)=0\), \(\tau(q_1)=1\). Тогда действительно при чтении \(\langle n\rangle_2\) автомат в конце стоит в \(q_0\) или \(q_1\) в зависимости от паритета единиц, и выдаёт \(0\) или \(1\) соответственно, т.е. \(t_n\).

2. Построение автомата. Постройте DFAO для последовательности \(a(n)=n\bmod3\), где \(n\) подаётся в двоичной системе (alphabet \(\{0,1\}\)). Решение. Число \(n\) в двоичной системе вводится младшим или старшим разрядом (не важно, главное – согласованно). Находим остаток \(n\bmod3\). Так как \(n=2m+d\), где \(d\) – последняя прочитанная цифра (0 или 1), можно следить за состоянием автомата, равным \(n\bmod3\). Заводим 3 состояния \(q_0,q_1,q_2\), \(q_i\) соответствует \(m\bmod3=i\). Начальное \(q_0\) (соответствует \(n=0\)). При считывании следующего бита «0» старое число умножается на 2: новое состояние \(q_i\to q_{(2i)\bmod3}\); при «1»: \(q_i\to q_{(2i+1)\bmod3}\). Функция выхода: \(\tau(q_i)=i\) (или можно выводить двоичную кодировку \(i\)). Таким образом получаем DFAO с 3 состояниями, и выходное число действительно \(n\bmod3\). Это демонстрирует, что последовательность \(n\bmod3\) – 2-автоматна.

3. Закрытость по степеням. Докажите, что если последовательность \(x*n\) – \(k\)-автоматная, то она также является \(k^m\)-автоматной для любого \(m\in\mathbb{N}\). Решение. Пусть автомат \(M_k\) генерирует \(x\) при чтении числа \(n\) в базе \(k\). Представим представление числа \(n\) в базе \(k^m\): это те же цифры, но каждая цифра \(d\in\{0,\dots,k^m-1\}\) разбивается на \(m\) цифр в базе \(k\). Тогда можно построить автомат \(M_{k^m}\), имитирующий \(M_k\), считая вход \(n\) в базе \(k^m\) как эквивалентную последовательность его \(k\)-цифр. Формально: пусть \(\langle n\rangle_{k^m}=d_\ell\cdots d_0\), каждый \(d_j\) – от 0 до \(k^m-1\). Разбиваем \(d_j\) на \(m\) цифр \((c_{j,m-1},\dots,c_{j,0})\) в базе \(k\). Создадим DFAO \(M_{k^m}\) над алфавитом \(\{0,\dots,k^m-1\}\), который при чтении \(d_j\) последовательно делает переходы автомата \(M_k\) по цифрам \(c_{j,0},\dots,c_{j,m-1}\). Такое расширение возможно (конкатенация переходов соответствует переходу по составному алфавиту). Выход \(M_{k^m}\) тот же, что и у \(M_k\) после обработки всех \(k\)-цифр. Таким образом \(x*n\) распознаётся и в системе \(k^m\).

4. Невозможность автоматности. Докажите, что последовательность суммы двоичных цифр \(s_2(n)=\sum\,\text{битов}(n)\) не является \(2\)-автоматной. Решение. Любая \(2\)-автоматная последовательность принимает значения в некотором конечном алфавите, т.е. не может принимать бесконечно много разных значений. Однако \(s_2(n)\) не ограничена: она растёт примерно как \(\log_2 n\), образ значений – множество всех неотрицательных целых. Следовательно, \(s_2(n)\) не может быть автоматной, т.к. её DFAO потребовал бы неограниченно много выходных символов. (Также можно отметить, что у \(2\)-автоматной последовательности неограниченный \(2\)-ядро, в отличие от \(s_2(n)\).)

5. Мультипликативно независимые основания. Предположим, что последовательность \((x*n)\) одновременно \(2\)-автоматна и \(3\)-автоматна. Покажите, что тогда \((x*n)\) периодична (упомяните теорему Кобхэма). Решение. Числа 2 и 3 взаимно простые (нет \(2^m=3^n\)), следовательно, по теореме Кобхэма получается, что \(x*n\) должно быть конечнопериодическим. То есть существует период \(p\) и \(N\) такие, что для всех \(n>N\) \(x*n=x*{n+p}\). (Полное доказательство – в разделе «Теорема Кобхэма».)

6. Характеристика прогрессии. Рассмотрим множество \(X=\{n\in\mathbb{N}:n\equiv 2\pmod{5}\}\). Постройте конечный автомат, распознающий записи \(\langle n\rangle_k\) таких \(n\). Решение. Здесь \(X\) – арифметическая прогрессия с модулем 5. Построим DFA на любом основании \(k\ge2\). В частности, для двоичной записи: состояния \(q_0,\dots,q_4\), \(q_i\) соответствует остатку \(n\bmod5=i\) (изначально \(q_0\) соответствует \(n=0\)). При чтении бита \(b\in\{0,1\}\) из состояния \(q_i\) переходим в \(q_j\), где \(j\equiv ki+b\pmod5\) (в базе \(k\) цифра \(b\) прибавляет к остатку \(b\), а сдвиг старых цифр – умножение на \(k\)). Выход – конечное распознавание: принимаем слово \(\langle n\rangle_k\) тогда и только тогда, когда автомат в конце находится в состоянии \(q_2\) (выход 1 для \(q_2\), и 0 – для остальных). Этот DFA имеет 5 состояний и явно распознаёт условие \(n\equiv2\pmod5\). Таким образом характеристическая функция множества \(X\) – \(k\)-автоматна.

7. Построение по морфизму. Последовательность \(y\) задаётся как образ морфизма: \(σ:0\mapsto 012,\;1\mapsto 2,\;2\mapsto 02\), продолжимого на букве \(0\), а затем кодированием \(\tau:\{0,1,2\}\to\{a,b\}\), \(\tau(0)=a,\tau(1)=b,\tau(2)=a\). Докажите, что \(y\) – 3-автоматна, и при необходимости постройте автомат. Решение. Морфизм \(σ\) – 3-равномерный (длины образов всех букв равны 3) и продолжим на букве \(0\) (имеет вид \(σ(0)=0u\)). Значит \(x=σ^\infty(0)\) – его фиксированная точка, и \(y_n=\tau(x*n)\). По теореме Кобхэма (или общему эквивалентному утверждению) любая последовательность, полученная из \(3\)-равномерного морфизма и кодирования, является 3-автоматной. Чтобы построить DFAO, можно сконструировать автомат по матрице морфизма: состояния соответствуют символам \(\{0,1,2\}\), переходы по остаткам деления на 3 (подробнее, например, по стандартному способу Кобхэма). Каждому состоянию приписывается выход \(\tau(состояние)\). Это даёт DFAO над алфавитом \(\{0,1,2\}\) (цифры в базе 3) с выходом в \(\{a,b\}\). В частности, состояние «0» выходит \(a\), «1» – \(b\), «2» – \(a\), и переход из символа \(c\) по цифре \(d\) ведёт в символ \(σ(c)_d\) (буква \(σ(c)\) на позиции \(d\)). Проверка даёт, что автомат вырабатывает \(y_n\) при вводе \(\langle n\rangle_3\).

8. Неавтоматность последовательности вида \(a^n\). Пусть \(x*n=a^n\) (\(n\)-я степень фиксированной буквы \(a\)) – бесконечное слово над \(\{a\}\). Можно ли считать \((x*n)\) \(k\)-автоматной? Решение. Слово \(a^n\) – тождественная последовательность из повторяющейся буквы \(a\). Это периодично с периодом 1, значит конечнопериодично, и потому является автоматным для любого основания (построить автомат, который всегда выдаёт \(a\)). Например, DFAO из одного состояния \(q_0\) (и \(\tau(q_0)=a\)) при любом входе остаётся в \(q_0\). Значит \((a^n)\) – \(k\)-автоматна для всех \(k\). Несмотря на то, что значение \(x*n\) не ограничено (разные \(n\) дают разную длину слова), но здесь мы считаем бесконечное слово \(x=(a,a,a,\dots)\) (то есть просто вечный \(a\)), что вовсе автоматно. Если же понимать задачу как «последовательность целых \(a^n\)», то это не автоматна, т.к. неограничена.

Заключение: приведены определения и основные свойства автоматных последовательностей и множеств, сформулировано и доказано ключевое утверждение – теорема Кобхэма (с его следствиями и необходимыми условиями), приведены типовые примеры и задачи с подробными решениями. Для дальнейшего чтения см. оригинальную работу Кобхэма и монографию Аллуша–Шаллит «Automatic Sequences».