ставляющему следующие состояния Qi для входа 1и. Сгруппировать эти состояния в соответствии с выходами (как в шаге 2), не объединяя вместе состояния, образованные различными подгруппами Qi. Перейти к шагу 3.

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

Пример 3.8. Диагностическое дерево для таблицы состояний, приведенное на рис. 3.22, показано на рис. 3.23. Правило, по ко-

ЛВСВ I <

БС,АДМ

ВС,А,Д

О I 1

BCD,D I

Г

CD,D,D О I <

ВС,Д,А(Ь) CD,B,B C,A,A,A(d) D,D,D,D(d) Рис. 3.23. Диагностическое дерево.

Г

CC,AD(o)

J L L

АВ(Ж(Ь)

Рис. 3.24. Таблица состояний (а); диагностическое дерево (б).

торому узел является конечным, приведено в скобках. Автомат имеет две диагностические последовательности длиной 3:111 и ПО.

В качестве примера автомата, не имеющего диагностических последовательностей, рассмотрим таблицу состояний и диагностическое дерево, представленные на рис. 3.24. Как и в предыдущем случае, правило, в соответствии с которым узел является конечным, приведено в скобках. Так как все узлы конечны в соответствии с правилами (а) или (б), автомат не имеет диагностической последовательности.

) Определение дано в приложении.

3.2.2. НАВОДЯЩИЕ ПОСЛЕДОВАТЕЛЬНОСТИ

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

Лемма 3.7. Для любого упрощенного последовательностного автомата М, имеющего п состояний, существует тест длиной п{п-1)12, определяющий состояние М в конце эксперимента.

Доказательство. Пусть в начале автомат находится в любом из состояний. Так как автомат упрощен, должен существовать вход, для которого он формирует по меньшей мере две разные выходные реакции, зависящие от начального состояния. Тогда этот вход делит множество следующих состояний по меньшей мере на два блока, ни один из которых не содержит более чем п-1 состояний. Если такой вход прикладывается к автомату, то самое большое число возможных конечных состояний, вырабатывающих тот же выход, равно п-1. Теперь покажем методом индукции, что число возможных конечных состояний может быть уменьшено до п - k с помощью последовательности длиной k{k-\- 1)/2. Это очевидно для ft = 1, так как входная последовательность длиной 1 в соответствии со сказанным выше достаточна для снижения числа возможных конечных состояний максимум до п-\. Предположим, что это справедливо для k-\, т.е. множество конечных состояний равно Qh-\ и содержит максимум п-(к-1) состояний после приложения входной последовательности на k{k -1)/2 входов. Определим Пи как часть') состояний М, такую, что состояния qi и q находятся в одном и том же блоке пи тогда и только тогда, когда отсутствует входная последовательность длиной к, различающая qi и qj. Блоки Пк представляют собой подмножества блоков Яй 1, и делит множество состояний по меньшей мере на к-{-1 блок. Следовательно, ни один из блоков не содержит больше п - к состояний. Поэтому Qh-\ должно иметь два состояния qa и qb, которые находятся в различных блоках я, и как следствие множество возможных состояний может быть уменьшено до и - к с помощью теста длиной к-\-(k-\){k)l2 = k{k-\-\)l2. Q i содержит одно состояние, и, следовательно, существует входная последовательность длиной п{п-1)/2, определяющая конечное состояние.

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

Процедура 3.4. Наводяи{ие последовательности

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

2. Для каждого входа h строится ветвь, направленная от Q к узлу-преемнику, представляющему множество всех следующих состояний, если исходное состояние включено в Q и приложен вход /fe. Сгруппировать эти узлы в соответствии с выходами, связанными с переходами к этим состояниям. Внутри любой группы ни одно состояние не должно повторяться (так как нашей целью является только идентификация конечного состояния).

3. Определить конечные узлы в дереве, пользуясь следующими правилами:

(а) узел, идентичный узлу более раннего уровня, является конечным;

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

4. Если один или несколько узлов являются конечными в соответствии с правилами (б), то последовательность входов от исходного узла до такого конечного узла является наводящей последовательностью. (Все узлы не могут быть конечными по правилу (а), так как наводящая последовательность существует всегда.) Если узел, конечный в соответствии с правилом (б), отсутствует, то перейти к шагу 5.

5. Для каждого неконечного узла Q,- и каждого входа Д построить ветвь от Qi к узлу-преемнику, представляющему следующие состояния Qi для входа h, сгруппировать их в соответствии с выходами, не объединяя вместе состояния, образованные различными подгруппами Qj. Перейти к шагу 3.

Пример 3.9. На рис. 3.25 приведены таблица состояний, изображенная ранее на рис. 3.24, и ее наводящее дерево. Правила, по которым узлы являются конечными, приведены в скобках. Входная последовательность 00 представляет собой наводящую последовательность минимальной длины. Если наблюдается выход 01, то конечное состояние равно А. Выход 10 характеризует конечное состояние С. При приложении входной последовательности 00 состояния В и D получены быть не могут.

Дополнительные (не минимальной длины) наводящие последовательности могут быть найдены путем продолжения наводящего дерева, как это показано пунктирными линиями на

с. Ч ,

*BCD(a)

4, BD

C,D,C(Ь)

6,CD

Рис. 3.25. Таблица состояний (а); наводящее дерево (б).

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

Рис. 3.26. Таблица состояний (a); табличное представление дерева-преемника (б).

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

Таблица состояний и табличное представление дерева-преемника приведены на рис. 3.26. Выходы на таблице состояний не

рис. 3.25,6. Из рисунка следует, что последовательность 010 является наводящей.

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

ABCD

Рис. 3.27. Другая таблица состояний (а); табличное представление дерева

преемника (б).

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

3.2.3. ИДЕНТИФИКАЦИЯ АВТОМАТОВ - ПРОВЕРОЧНЫЕ ТЕСТЫ

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

Проблема построения проверочных тестов очень подробно освещена в [5, 10] и здесь не рассматривается. На примере 3.10 показано, как с помощью проверочного теста можно восстановить таблицу состояния.

Пример 3.10. Предположим, что нижеследующая выходная последовательность z формируется автоматом с тремя или меньшим числом состояний как реакция на входную последовательность X.

t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 X 000001001 О О О О 1 О Z 010010001 0 0 1 0 0 1

) Автомат называется сильно связанным, если для любой пары состояний gt и Qj существует входная последовательность, которая переводит его из в Qj, и входная последовательность, которая переводит его из в qt.

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

Рис. 3.28. Неполная таблица состояний к примеру 3-10.

М

Рис. 3.29. Полная таблица состояний.

имеет только три состояния (4) = А, следовательно, N{C, 0) = = Л, Z(C, 0) =0. На этом этапе можно составить неполную таблицу состояний, представленную на рис. 3.28, и заключить, что q(5) = В и 9(6) = С.

По выходной реакции на входную последовательность 00 можно определить, что q{7) = С. Так как q{6) = С, N{C, 1) - = С, Z{C,l) -0. Из неполной таблицы состояний следует, что q(8) = А, q{Q) = В. По выходной реакции на входную последовательность 00 можно также найти, что 9(10) = С. Следовательно, N{B,l) = С, Z{B, 1) = 1. Из таблицы состояний имеем 9(11) = Л, 9(12) = В, 9(13) = С, 9(14) = Л. По реакции на вход О определим, что 9(15) = В и N{A, 1) = В, Z(Л, 1) = 0. Полная таблица состояний приведена на рис. 3.29.

Приложив входную последовательность х к автомату, имеющему 3 состояния, и получив на его выходе последовательность Z, можно сделать вывод о том, что это автомат М. Однако обратный вывод неверен, так как у автомата М такая выходная последовательность формируется только в том случае, если он начинает работу из состояния Л. Чтобы автомат начинал действовать из состояния Л, на его вход подается синхронизирующая последовательность, переводящая автомат в состояние А перед подачей входной последовательности х, позволяющей различать М среди других автоматов с тремя состояниями.

Обозначим состояние в момент t через q{t), а исходное состояние А через (l). Так как q{2) формирует на выходе 1 при входе, равном О, тогда как А генерирует на выходе О при входе О, q{2) фА. Обозначим (2) через В. Тогда Л^(Л, 0) = В, 2(Л,0) =0 и Z(B, 0) = 1. Из тех же соображений (3) ф В. Далее, так как входная последовательность 00, будучи приложенной к А, генерирует выходную последовательность 01, а приложенная к 9(3), дает на выходе последовательность 00, q{Ъ')ф ф А. Следовательно, (3) = С и N{B,0) - С. Рассуждая аналогично, получим, что q{4)фB, (4) 4 С. Так как автомат

3.3. СПЕЦИАЛЬНЫЕ КЛАССЫ

ПОСЛЕДОВАТЕЛЬНОСТНЫХ АВТОМАТОВ

3.3.1. ПОСЛЕДОВАТЕЛЬНОСТНЫЕ АВТОМАТЫ БЕЗ ПОТЕРИ ИНФОРМАЦИИ

Последовательностиыи автомат можно рассматривать как устройство типа вход-выход, которое осуществляет кодирование входных последовательностей в выходные. Интересным классом являются автоматы, позволяющие путем декодирования выходной информации получить входную информацию, а также некоторые сведения об исходном и/или конечном состоянии автомата. Такие автоматы называются автоматами без потерь информации. Мы рассмотрим четыре типа таких автоматов. К типу I относятся автоматы, позволяющие определить входную последовательность по выходной последовательности и его исходному состоянию. К типу II относятся автоматы, для которых входную последовательность можно определить по выходной последовательности и его конечному состоянию. Автоматы без потерь информации, входная последовательность которых может быть определена по выходной последовательности и его начальному и конечному состояниям, относятся к типу III и называются обоби{енными автоматами без потерь информации. Наконец, автоматы без потерь информации, для которых первый вход последовательности может быть определен по первым (k-\-\) выходам выходной последовательности и исходному состоянию, называются конечными авто.иатами без потери информации степени k и относятся к типу IV. Отметим, что автом^ть}

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

Автомат, изображенный на рис. 3.29, содержит синхронизирующую последовательность. Полный тест для его идентификации состоит из синхронизирующей последовательности, за которой следует последовательность, показанная выше. Однако если автомат не содержит синхронизирующей последовательности, то предварительно настроенная часть теста должна предшествовать наводящей последовательности, следующей за входной последовательностью, выбираемой по реакции, автомата на наводящую последовательность таким образом, чтобы тест был приложен в заданном исходном состоянии.

Рис. 3.30. Последовательностный автомат к примеру З.П.

Предположим, что Z{qi, 1) Ф Z{qi, 1) для всех 1зФ1к и всех qi е Q. Тогда вход может быть однозначно определен для любого исходного состояния и одного выхода. Таким образом, существует возможность последовательно (вход за выходом) декодировать выходную последовательность и, следовательно, автомат является последовательностным автоматом без потерь информации типа I.

Пример 3.11. Автомат Mi, изображенный на рис. 3.30,- последовательностный автомат без потерь информации типа I. Однако автомат Мг не является автоматом этого типа, так как вход не может быть определен, если выход О сформирован при исходном состоянии 1.

Лемма 3.9. Последовательностный автомат М является автоматом без потерь информации типа II, если ни один из элементов следующее состояние - выход (qi, Zj) не появляется в таблице состояний более чем один раз.

Доказательство. Предположим, что элемент (qi, Zj) появляется более чем один раз. Тогда, задав конечное состояние q р выходную последовательность, оканчивающуюся в г/, мы mq-

типа I идентичны автоматам типа IV степени 0. Ниже доказывается ряд лемм, которые могут быть использованы для определения свойств автоматов без потерь информации.

Лемма 3.8. Последовательностный автомат М является автоматом без потерь информации типа I тогда и только тогда, когда Z{qi,Ij) =Z{qi,Iu) для всех ЦФК и всех состояний qiQ.

Доказательство. Предположим, что М является автоматом типа I и Z{qi, Ц) = Z{qi, /ь) = Zu для некоторого входа Ijh и состояния qi. Если автомат первоначально находится в состоянии qi и для некоторого входа формирует выход z, то вход не может быть определен однозначно, и автомат не является автоматом типа I. Это противоречие доказывает необходимое условие.

X х

Рис. 3 31. Последовательностные автоматы к примеру 3.12.

Пример 3.12. Автомат Ми изображенный на рис. 3.31, не является автоматом без потерь информации типа ii, так как по выходной последовательности О и конечному состоянию 1 нельзя

.V г,

Рис. 3.32. Таблица состояний автомата без потерь информации типа II (а);

тестовая таблица (б).

получить входную последовательность. Однако Мз представляет собой автомат типа ii.

Лемма 3.9 дает достаточное условие существования автомата типа ii, однако, как видно из таблицы состояний М^, приведенной на рис. 3.32, которая характеризует автомат типа ii, это условие не является необходимым.

Необходимое условие существования последовательностного автомата без потерь информации типа ii дает лемма 3.10.

жем однозначно определить последний вход и последнее состояние. Двигаясь последовательно (вход за входом) назад методом итераций, можно найти всю входную последовательность.

Лемма 3.10. Если элемент следующее состояние - выход (qi, Zj) появляется в таблице состояний более чем один раз, то автомат относится к типу ii только в том случае, если {qu Zj) не появляется в различных столбцах таблицы состояний.

Доказательство. Если {qu Zj) появляется в двух столбцах h и II, то для выхода Zj и известного конечного состояния qi вход нельзя определить однозначно.

Следующая ниже процедура позволяет определить, является ли автомат, удовлетворяющий лемме 3.10, автоматом типа ii. Процедура 3.5

1. Построить тестовую таблицу, в которой строки соответствуют отдельным состояниям автомата М, а столбцы представляют все возможные выходы. Элемент в строке qi и столбце Zj будет являться множеством состояний, имеющих элемент следующее состояние - выход {qu Zj) для любого входа Iu т. е. Qu {qk\N{qk, h)=qi, z{qu, Ii)=Zj для точно одного входа

Если существуют два входа 1т, такие, что N{qh, Ii) = ~N{qn, Im) ~qi а Z{qu, h) = Z{qn, Im) = Zj, то автомат не относится к типу ii, и процедура заканчивается. Заметим, что если условие леммы 3.10 удовлетворяется, то это не может произойти на первом шаге процедуры.

2. Для каждого множества состояний Qij, входящего в таблицу состояний на шаге 1, добавить строку в таблице состояний. В каждый столбец Zk строки Qij ввести множество состояний, ведущее к состояниям в Qij и образующее выход z для некоторого входа. Если существуют два входа /; ф / , такие, что N {qp, II) е Qij, N{qr, Im) e Qij и Z{qp, /,) = Z{qr, / ) = Zu, TO автомат не относится к типу ii. Заметим, что qp и qr не обязательно должны быть разными.

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

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

Пример 3.13. Рассмотрим автомат, изображенный на рис. 3.32, а, с выходами Zi и Zz. Определим, является ли он автоматом типа ii относительно выхода Zi (т. е. можно ли однозначно определить входную последовательность по выходной последовательности Zi и конечному состоянию). Тестовая таблица приведена на рис. 3.32,6. Элементы (3,0) и (4,1) повторяются в таблице состояний, но удовлетворяют условию леммы 3.10. Верхняя часть тестовой таблицы получена с помощью