6.81 РАСПОЗНАВАНИЕ ЛИНЕЙНОГО ДВОИЧНОГО АВТОМАТА 239

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

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

111011101001110100111 ... (6.75)

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

<р = 010011101001110100111 (6.76)

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

Tj. = f-\-D\ (6.78)

7p = (D©D4@D5@D«)-g, (6.79)

7(Л31)/©В2©®У®° =

Р ® /

Применение алгоритма Евклида к (6.80) показывает, что полиномы числителя и знаменателя имеют общий делитель (D@D2@D.@/) и что 7(Л31) может быть записано в виде

ГГ-1ЯП- (.D® ® D ® ® РФ/ ~ (Р © Р2 ® Р ® /) (Рз ® Р ® /) ~ рз ® Р ® / •

(6.81)

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

2 = xex-5©2v-i©2v-3- (6-82)

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

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

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

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

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

•2v = /(-v. -v-l. -v-fi) (6-83)

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

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

s = g{Xy i, лг 2, .... лг ). (6.84)

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

с=ць, Ч.....У (-

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

и h •ц

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

Пусть задан не зависящий от выхода автомат М с памятью и входным алфавитом (j, 1.....Ip): x-z-функ-

ция (6.83) автомата М всегда может быть получена подачей

6.9] НЕ ЗАВИСЯЩИЕ ОТ ВЫХОДА АВТОМАТЫ 241

на вход автомата последовательно всех возможных последовательностей 1,1- .. . L- . После определения x-z-функ-

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

Последовательность, которая содержит все возможные

подпоследовательности \, • • \, из р. символов, назы-

h •2 •ц

вается {р, \х)-последовательностью. Самая короткая {р, р,)-последовательность является последовательностью, в которой каждый символ, за исключением последних р-1 символов, начинает различную подпоследовательность длиной р. Такая последовательность, длина которой обязательно p>-\-\i-1, называется компактной {р, цупоследовательностью.

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

Алгоритм 6.3. Для того чтобы построить компактную (р, р)-последовательность для не зависящего от выхода автомата с памятью р и входным алфавитом (j, 1р)> нужно произвести следующие операции: (1) Пусть , =£ =

•1 2

= ...=1 =1 . Полагаем /г = р,+ 1. (2) Рассматривая •и

входной алфавит как упорядоченное множество (i - первый символ, 2 - второй символ.....1р - /7-й СИМВОЛ), полагаем, что СИМВОЛ . имеет наименьший индекс, так что под-последовательность!, , ••I, нигде не содержится в последовательности , , ... 1, . (3) (а) Если k С p-{-

•1 •2 k-l

) Метод предложен Липпелом и Эпштейном (В. Lippel and 1. J. Epstein, A Method for Obtaining Complete Digital Coding Chains, IRE Trans., vol. EC-6, p. 121, 1957).