6.8. Распознавание линейного двоичного автомата

Как было отмечено в предшествующем параграфе, по заданной импульсной характеристике линейного двоичного автомата, легко можно определить реакцию автомата, находящегося в начальный момент времени в состоянии покоя, на любое возбуждение. Поэтому знание импульсной характеристики позволяет характеризовать любой неизвестный автомат, находящийся в начальный момент в состоянии покоя. В этом параграфе мы увидим, как можно получить -характеристику по импульсной характеристике. Получив -функцию, можно затем построить характеристические функции заданного автомата так, как описано в § 6.2.

Рассмотрим линейный, находящийся в начальный момент времени в состоянии покоя двоичный автомат М, передаточное отношение которого задано равенством

где коэффициенты равны либо 0, либо 1. Тогда для автомата М, находящегося в начальный момент времени в состоянии покоя,

Предположим теперь, что бесконечная входная последовательность 1000... (т. е. импульс) прикладывается к М в момент При этом мы получим для всех . Из (6.69) тогда имеем: для всех . Поэтому импульсная характеристика автомата, характеризуемого равенством (6.68), определяющим , имеет вид Наоборот,

если автомат имеет импульсную характеристику то он может быть охарактеризован передаточным отношением Т (М), которое задано выражением (6.68).

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

Пусть

Автомат, который реализует имеет передаточное отношение

Автомат, который реализует имеет передаточное отношение:

Принимая во внимание свойство суперпозиции, автомат М, который реализует импульсную характеристику имеет передаточное отношение

Выражение Т (М) может быть записано как отношение двух полиномов от D, у которых может быть сокращен общий делитель, как было объяснено в § 6.6. Таким образом, по импульсной характеристике автомата М всегда может быть определено его передаточное отношение. Построение

-функции по передаточному отношению и характеристических функций по -функции является простой задачей.

В качестве примера предположим, что линейный двоичный автомат выдает импульсную характеристику

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

По (6.72), (6.73) и (6.74) получаем:

    (6.79)

Применение алгоритма Евклида к (6.80) показывает, что полиномы числителя и знаменателя имеют общий делитель и что может быть записано в виде

Автомат находящийся в начальный момент времени в состоянии покоя, поэтому характеризуется равенством

Можно легко проверить, что автомат, определяемый (6.82), действительно обладает импульсной характеристикой (6.75).

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

состояний в автомате, чтобы по теореме 6.1 определить максимальную память. Заметим также, что число состояний в линейном двоичном автомате с памятью не может превышать . Поэтому знание эквивалентно знанию верхней границы для , что можно было предполагать ввиду теоремы 5.2.