Язык 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 0 , S 1 , ... S n , обнаруженные при обработке строки a n .S n должно быть принимающим состоянием, поскольку a n находится в L. Но так как в этом DFA меньше чем n + 1 различных состояний,В принципе, должно было быть какое-то государство, которое посещали как минимум дважды.Удаление этого цикла дает другой путь (и другую принятую строку) длиной 0 до S n .Но L не содержит строк короче n, что противоречит нашему предположению.Поэтому ни один DFA с менее чем n + 1 состояниями не распознает L.