6.2. Представление систем с конечной памятью

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

быть записано в форме

где принято, что . Если добавить ряд несущественных переменных и принять то уравнение (6.1) можно записать в виде

Для того чтобы преобразовать приведенное характеристическое уравнение в характеристические стандартные функции конечного автомата, переменную s определим так, чтобы являлась упорядоченным набором значений переменных . Равенство (6.2) тогда примет вид

Из определения s следует, что определяется так:

Следовательно,

Уравнения (6.3) и (6.6) могут рассматриваться как характеристические функции конечного автомата. Следовательно, множество упорядоченных наборов значений переменных адекватно множеству состояний системы, представленной

уравнением (6.2). Если число символов входного и выходного алфавитов для системы соответственно равно и q, то мощность множества состояний будет

В качестве примера рассмотрим устройство На устройство периодически поступают цифры 0 и 1, выход его в момент равен сумме по модулю 2 выхода в момент и входа в момент . Обозначая сложение по модулю 2 знаком может быть охарактеризовано равенством

Добавляя несущественные переменные вместо (6.8) получим:

Входной алфавит в этом случае

а выходной алфавит

Множество состояний является множеством всех упорядоченных наборов значений трех переменных :

Зависимость между может быть представлена в табличной форме, как показано в таблице 6.1. Столбцы таблицы под представляют все упорядоченные наборы значений трех переменных; каждый набор записан дважды (по одному разу для каждого значения ). Столбцы, озаглавленные могут быть заполнены путем воспроизведения ранее заполненных столбцов (таких как ) и

Таблица 6.1 Соотношения между для (см. скан)

путем использования соотношения (6.8) (для столбца ). Показанную таблицу удобно использовать для определения характеристических функций автомата Например,

Таблица 6.2. Автомат (см. скан)

по четвертой строке можно сказать, что если входной символ 1 появляется при состоянии (0, 0, 1), то выходной символ будет 1 и следующее состояние (1, 0, 1). Применяя подобные рассуждения по отношению к другим строкам, построим таблицу переходов А 27 (см. таблицу 6.2).

Рис. 6.2. Автомат

В общем случае автомат, полученный описанным способом, не минимальный. Однако, минимальная форма всегда может быть определена любым из методов минимизации, описанных в главе 3. Минимальная форма автомата показана на рис. 6.2, где состояния 1, 2, 3 и 4 представляют эквивалентные классы соответственно.