6.4. Определение памяти автомата
В этом параграфе мы рассмотрим следующую задачу. Заданы характеристические функции 
автомата (в табличной форме, в виде графа или в матричной форме). Определить, является ли этот автомат автоматом с конечной памятью, и, если является, то, как определить его память?
Рассмотрим автомат М с множеством состояний 
Пусть 
обозначает множество всех последовательностей вход - выход, описываемых путями длины k, которые заканчиваются в состоянии 
По лемме 6.1, если М является автоматом с памятью 
то
По теореме 6.1, если М не является автоматом с конечной памятью, то
Следовательно, для определения памяти автомата можно сформулировать следующий алгоритм.
Алгоритм 6.1. Задан автомат М с множеством состояний 
требуется найти память автомата М. (1) Полагаем 
Составляем последовательность 
(а) Если 
для некоторых 
, то переходим к (4). (б) Если 
для всех 
то k является памятью М. (4) (а) Если 
то увеличиваем k на 
и возвращаемся к (2). (б) Если 
, то М не является автоматом с конечной памятью.
Выполнение алгоритма 6.1 облегчается при использовании матриц переходов высокого порядка, введенных в главе 2. В клетке 
матрицы переходов 
порядка 
записаны все пути длины к, ведущие из состояния 
в состояние 
. Поэтому клетки 
столбца матрицы 
представляют все пути длины k, заканчивающиеся в состоянии 
. Таким образом, последовательности вход - выход, представленные путями, перечисленными в столбце матрицы 
являются элементами множества 
По матрице 
и диаграмме переходов для автомата М может быть построена таблица, в которой 
столбец содержит элементы 
если нет двух столбцов, имеющих общий член, то k должно быть памятью автомата М.
В качестве примера рассмотрим автомат 
показанный на рис. 6.6.
Таблица 6.3. Множества для 
Рис. 6.6. Автомат 
Матрица переходов автомата 
задана выражением (6.23), а матрица переходов первого порядка — выражением (6.24).
По (6.24) и (6.23) можно построить таблицу 6.3, в которой перечислены 
.
Так как последовательности вход - выход (0/1) и (1/1) появляются в двух различных столбцах этой таблицы, память автомата 
будет превышать 1. Выражение (6.25)
представляет собой матрицу переходов второго порядка для автомата 
По (6.25) и (6.23) можно построить таблицу 6.4, в которой перечислены 
.
Таблица 6.4
Множества для 
Автомат 
должен иметь память 2, так как никакая последовательность вход - выход не появляется в двух различных столбцах этой таблицы. Если бы автомат 
не был автоматом с конечной памятью, то этот факт обнаружился бы из таблицы, перечисляющей 
