6.9. Не зависящие от выхода автоматы

Автомат с конечной памятью, в котором -память равна О, называется не зависящим от выхода автоматом. Такого типа автомат определяется соотношением

где любой из аргументов может быть несущественным. Не зависящие от выхода автоматы, составляющие подкласс класса автоматов с конечной памятью, проявляют все свойства, полученные ранее для класса автоматов с конечной памятью. В частности, из леммы 6.1 имеем:

Теорема 6.4. В минимальном не зависящем от выхода автомате с памятью

Значит, состояние не зависящего от выхода автомата полностью определяется входной последовательностью длины и, следовательно, такой автомат может непосредственно управляться источником входного возбуждения. Если в автомате М

то все, что требуется, чтобы перевести автомат М в состояние — это подать входную последовательность

Так как такая последовательность может быть подана на автомат, находящийся в любом состоянии, то из этого следует, что любое состояние в не зависящем от выхода автомате может быть достигнуто из любого другого состояния, а это значит, что не зависящий от выхода автомат эквивалентен сильносвязному автомату.

Пусть задан не зависящий от выхода автомат М с памятью и входным алфавитом - функция (6.83) автомата М всегда может быть получена подачей

на вход автомата последовательно всех возможных последовательностей После определения -функции может быть построена таблица (или граф, или матрица) переходов автомата М. Таким образом, не зависящий от выхода автомат с определенной памятью и входным алфавитом всегда может быть распознан с помощью простого заранее безусловного эксперимента. Заметим, что выходной алфавит не нужен для задания эксперимента, и, следовательно, до эксперимента распознаваемый автомат принадлежит бесконечному классу автоматов. Однако, так как каждый не зависящий от выхода автомат является сильносвязным, то этот класс является исключительным и удовлетворяет условию различимости по теореме 5.3.

Последовательность, которая содержит все возможные подпоследовательности из символов, называется -последовательностью. Самая короткая -последовательность является последовательностью, в которой каждый символ, за исключением последних символов, начинает различную подпоследовательность длиной . Такая последовательность, длина которой обязательно называется компактной -последовательностью.

Следующий метод, который будет дан без доказательств, может быть использован для построения компактных -последовательностей для каждого заданного

Алгоритм 6.3. Для того чтобы построить компактную -последовательность для не зависящего от выхода автомата с памятью и входным алфавитом нужно произвести следующие операции: (1) Пусть Полагаем Рассматривая входной алфавит как упорядоченное множество — первый символ, -второй символ символ), полагаем, что символ имеет наименьший индекс, так что подпоследовательность нигде не содержится в последовательности (3) (а) Если

то увеличиваем на 1 и возвращаемся к (2). (б) Если является компактной -последовательностью.

В качестве примера (6.86) показывает построение компактной -последовательности для не зависящего от выхода автомата с памятью 3 и входным алфавитом Последовательные строки показывают подпоследовательности длины 3 (имеется 27 таких подпоследовательностей). Последняя строка показывает суммарную последовательность, длина которой

(см. скан)

Последовательности, полученные по алгоритму 6.3, обладают следующим свойством. Если первые символов

разместить по окружности, то каждая последовательность, построенная считыванием последовательных символов, образует компактную -последовательность (независимо от начального символа и независимо от того, считываются символы по часовой стрелке или против). Поскольку последовательности, построенные путем выбора различных начальных символов на окружности (но продолжающиеся в одном и том же направлении), обязательно различны, то каждое применение алгоритма 6.3 может дать различных компактных -последовательностей. Число различных компактных -последовательностей дается выражением

    (6.87)

В заключение приведем следующую теорему.

Теорема 6.5. Не зависящий от выхода автомат с известной памятью и входным алфавитом мощности всегда может быть распознан простым безусловным экспериментом длины l, где

    (6.88)

Таблица 3 6.1