Минимальное количество состояний необходимо?

Question

Определение языка L с алфавитом { a } дается следующим образом

L = {a^nk | k> 0; и n является положительной целочисленной константой}

Какое количество состояний требуется в DFA для распознавания L?

---

На мой взгляд, это должно быть k+1, но я не уверен.

Answer 1

Язык L может быть распознан DFA с n+1 состояниями.

Заметим, что длина любой строки в L совпадает с 0 mod n.

Пометить n состояний целыми числами 0, 1, 2, ... n-1, представляя каждый возможный остаток. Дополнительное состояние S является начальным состоянием. S имеет один переход в состояние 1. Если машина в данный момент находится в состоянии i, на входе она переходит в состояние (i+1) mod n. Состояние 0 является единственным принимающим состоянием. (Если бы пустая строка была частью L, мы могли бы исключить S и сделать состояние 0 начальным состоянием).

Предположим, что существует DFA с менее чем n+1 состояниями, которые все еще распознают L. Рассмотрим последовательность состояний S₀, S₁,... S_n, обнаруженных при обработке строки aⁿ. S_n должно быть принимающим состоянием, так как aⁿ находится в L. Но так как в этом DFA имеется меньше чем n+1 различных состояний, по принципу голубиного отверстия должно быть какое-то состояние, которое было посещено по крайней мере дважды. Удаление этого цикла дает другой путь (и другую принятую строку), с длиной 0 до S_n. Но L не содержит строк короче n, что противоречит нашему предположению. Поэтому ни один DFA с менее чем n+1 состояниями не распознает L.