НИИ в Mi- Если rai+i<«j. то, по следствию 4.2, выполнение операции (4) требует не более (п--п - 1) (Л/ - 1) операций. Из теоремы 4.13 следует, что порядок эксперимента, описанного алгоритмом, не превышает

2(«,-1)+л/-1 =

/ N \

\/=1

- 1.

(5.3)

Таким образом получаем:

Теорема 5.5. Если заданный автомат М принадлежит исключительному классу автоматов [М, Щ, Ждг), где Ml имеет состояний и то автомат М всегда может быть распознан простым условным экспериментом длины I и порядка d, где

5] «г («i - 1)

( = 1

+ («1 + «2-1)(Л-1), (6.4)

- 1.

(6.5)

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

Когда Ul или верхняя граница И; одинаковы для всех /, то из теоремы 5.5 вытекает

Следствие 5.2. Если заданный автомат М принадлежит исключительному классу автоматов [М, М.....ЛлЬ

в котором каждый автомат имеет, по крайней мере, п состояний, то автомат М может быть распознан простым условным экспериментом длины / и порядка d, где

/<]-Л/(«2+3« -2) -2«+1, d<yVra- 1.

(6.6) (5.7)

5.4. Задача распознавания повреждений

Значительный практический интерес представляет задача распознавания повреждения, которое вызвало неисправность автомата. В связи с этой задачей удобно рассматривать поврежденный автомат как самостоятельный автомат. При этом задача распознавания поврежденного автомата, в котором повреждение предполагается относящимся к известному классу повреждений, сводится к задаче распознавания автомата, относящегося к известному классу автоматов. Из результатов § 5.3 следует, что повреждение всегда может быть определено, если класс, к которому относится поврежденный автомат, является исключительным классом.

Чтобы проиллюстрировать процедуру распознавания автомата вообще и распознавания повреждения в частности, рассмотрим автомат Л24, представленный таблицей 5.1

Известно, что автомат Л24 неисправен и что в результате повреждения при приложении к автомату в одном из его состояний входного символа а на его выходе вместо О появляется 1. Поврежденный автомат Л24 может быть одним

Таблица 5.1 Автомат i424

Таблица 5.2 Автомат i424

из автоматов Л24, Л24" и Л24", представленных таблицами 5.2, 5.3 и 5.4 соответственно. Чтобы определить, составляют ли автоматы Л24, Л24" и Л24" исключительный класс, следует произвести эквивалентное разбиение для автомата Д (Л24, Л24" и Л24"), т. е. для расщепляемого автомата, построенного из автоматов Л24, Л24" и Л24".

5.4]

ЗАДАЧА РАСПОЗНАВАНИЯ ПОВРЕЖДЕНИЙ

Таблица 5.3 Автомат i424"

Таблица 5.4 Автомат AW

Разбиение может быть выполнено с помощью таблицы пар, как показано в таблице 5.5. Из этой таблицы видно, что эквивалентными в автомате Д (Л24, Л24", /124") являются только пары {1", 3") и (2", 4"). Следовательно, автомат Л24"

Таблица 5.5 Таблица пар для автомата Д (/124, А2А", Л24")

не является минимальным, и ни одно состояние одного автомата не является эквивалентным никакому состоянию другого автомата. Таким образом, после того как автомат Л24" будет представлен своей минимальной формой, автомат А(Л24, А1\", А24") становится минимальным и притом таким, что автоматы Л24, А24" и Л24" (все в своих минимальных формах) образуют исключительный класс. Таблица переходов и граф переходов автомата Д (Л24, Л24", Л24") приведены на рис. 5.3 и в таблице 5.6 (автомат Л24" дан в своей Минимальной форме).