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

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

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

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

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

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

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

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

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

Разбиение может быть выполнено с помощью таблицы пар, как показано в таблице 5.5. Из этой таблицы видно, что эквивалентными в автомате являются только пары . Следовательно, автомат

Таблица 5.5 Таблица пар для автомата

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

Теперь задача определения повреждения в автомате сведена к задаче определения конечного состояния поврежденного автомата или к задаче проведения установочного эксперимента над автоматом

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

Эксперимент для распознавания повреждения описан в таблице 5.7, где предполагается, что начальным состоянием

Таблица 5.6. Автомат

автомата является состояние 2 и что в результате повреждения при приложении к автомату входного символа а в состоянии 4 на выходе получается 1. Тогда истинным автоматом является а истинным начальным состоянием — (это, конечно, экспериментатору сначала не известно). Первый столбец таблицы 5.7 содержит в качестве руководства читателю истинное состояние на различных

Таблица 5.7. Эксперимент по распознаванию повреждения в автомате (см. скан)

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

быть Затем проводим регулярный условный установочный эксперимент для автомата с множеством допустимых начальных состояний который устанавливает, что конечное состояние должно быть если испытуемым автоматом является Тогда в конце третьего установочного эксперимента заданным автоматом может быть в состоянии переводит 2 в 1) или в состоянии переводит в или в состоянии . Поэтому далее проводим регулярный условный установочный эксперимент для автомата с множеством допустимых состояний который выявляет, что конечным состоянием является Так как состояние принадлежит подавтомату эксперимент показывает, что испытуемым автоматом является Таким образом, можно сделать заключение, что имеющее место повреждение вызывает появление 1 вместо 0 при приложении входного символа а к автомату в состоянии 4.

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