Файл: Богомолов А.М. Эксперименты с автоматами.pdf

= 3, 4. Функции переходов и отметок минимального контролирую­ щего автомата В (А) приведены в табл. 14.

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

(9> (S))m.

4.5. Распознавание автомата известного нласса

Рассмотрим частный случай задачи диагностирования слабоини­ циального автомата по заданному разбиению множества его началь­ ных состояний, который имеет место при распознавании автомата, принадлежащего конечному классу автоматов. Пусть S0 = 5 и каж­ дый класс Кп заданного разбиения П является стабильным множе­

автомата А стабильны, то автомат А диагностируем по разбиению

жества ее состояний, которое отождествляет состояния, соответ­ ствующие каждому из автоматов А И Л 2 , AN- Поскольку классы разбиения П стабильны, то необходимым и достаточным условием возможности распознавания автомата, принадлежащего конечному классу автоматов, путем вероятностного эксперимента является исключительность этого класса. Точно такое же условие является необходимым и достаточным для возможности распознавания ав­ томата, принадлежащего конечному классу автоматов, путем про­ стого безусловного эксперимента. Таким образом, области приме­ нения детерминированных и вероятностных экспериментов для диаг­ ноза неисправностей дискретных устройств совпадают.

из (4.21) следует верхняя оценка математического ожидания длины вероятностного эксперимента по распознаванию автомата, принад­ лежащего этому классу

В работе [161 показано, что и' < 2пы — 1. Отметим, что практи­ чески средняя длина распознающего вероятностного эксперимента зачастую оказывается значительно меньше оценки, определяемой приведенным неравенством.

4.6. Контроль исправности автомата

Во введении задача контроля исправности автомата сформулиро­ вана следующим образом. Известно, что исследуемый автомат В является либо автоматом А , который интерпретируется как исправ­ ный автомат, либо одним из автоматов некоторого класса 91, кото­ рый интерпретируется как класс неисправных автоматов. Цель контрольного эксперимента с автоматом В заключается в определе­ нии, является ли автомат В автоматом А . Если класс неисправных

виты, равные входному алфавиту автомата А , то можно считать,

роля автомата В равносильна задаче диагностирования автомата М

ти контроля автомата В вероятностным экспериментом является диагностируемость автомата М по разбиению П со стабильными классами.

При проведении вероятностного эксперимента, диагностирую­ щего автомат М по разбиению П, анализ входной и выходной по­ следовательности может проводиться контролирующим автоматом, описанным в разделе 4.4. Отметим, что число состояний контроли­ рующего автомата зависит от числа неисправностей автомата А и при большом ;V этот автомат получается слишком громоздким. Оказывается, что в качестве контролирующего автомата можно взять такой автомат, число состояний которого не зависит от N, но при этом результат эксперимента может носить вероятностный характер.

В дальнейшем нам понадобится понятие автомата Рабина — Скотт

представляет собой множество подмножеств множества 5, X X Y — входной алфавит, А — функция переходов, 5 — начальное состоя­

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

Автомату А соответствует последовательностное отношение [59]

Теперь вернемся к вопросу контроля автомата В вероятностным экспериментом. Как уже упоминалось, можно считать, что экспе­ римент проводится с автоматом М. Предположим, что в качестве автомата, анализирующего пару последовательностей (р, q) исполь­ зуется автомат ТА, который определяет, может ли автомат А на последовательность р прореагировать последовательностью q. Еслине может, то начальное состояние исследуемого автомата М не при­ надлежит 5 и, следовательно, автомат В неисправен. Если же авто­ мат ТА определил, что А может прореагировать на последователь­ ность р последовательностью q, то в случае, когда М диагностируем, по разбиению П, это повышает вероятность того, что начальное со­ стояние автомата М принадлежит S, т. е., что автомат В исправен. При этом упомянутая вероятность оказывается тем больше, чем: длиннее эксперимент, и в пределе стремится к единице. Ниже будет приведено доказательство этого утверждения.

Через т [s] обозначим математическое ожидание длины вероятност­ ного эксперимента, устанавливающего, что начальное состояние s- принадлежит множеству V. В силу того, что автомат М диагности­ руем по разбиению П, математическое ожидание т Ы существует. • Пусть т — наименьшее целое число, удовлетворяющее неравенству

m > max m [s]. Применяя (4.25), легко показать, что для произвольного целого числа k справедливы следующие равенства:

Известно [35], что если случайная величина \ принимает лишь неотрицательные значения, и математическое ожидание т этой величины существует, то, каково бы ни было є > О,

мет значение, равное или превышающее е. Формула (4.27) называется

Предположим, что в результате анализа пары последователь­ ностей длины km контролирующий автомат ТА определил, что эта пара последовательностей принадлежит 0А. Как при этом изменится вероятность того, что начальное состояние автомата М принадлежит множеству S? Пусть Р (S) и Р (V) — априорные вероятности того, что начальное состояние автомата М принадлежит множеству 5 и V соответственно. Пусть, далее, Pkm(S/0A) — апостериорная вероят­ ность того, что начальное состояние принадлежи^, если на входе ТА появилась пара последовательностей длины km, принадлежащая множеству 0А; Pkm (0A/S) (Pkm (0A/V)) — вероятность появления пары последовательностей длины km, принадлежащей 0А, если на­ чальное состояние автомата М принадлежит множеству S (множе­ ству V). Применяя формулу Байеса, получаем

Pkm (Од/10 = 2 Р (S) Pkm (OA/S),

s£V

где Р (s) — вероятность того, что М находится в состоянии s, если