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

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

Кроме того, даже в тех случаях, когда экспериментатор может подавать на вход автомата произвольные последовательности, иногда он предпочитает воспользоваться для генерирования входных по­ следовательностей источником случайных сигналов с определенными свойствами. Это объясняется тем, что существующие методы по­ строения диагностических и установочных последовательностей [16] слишком громоздки, и поэтому естественным является желание обойти этап построения этих последовательностей при решении за­ дач контроля и диагноза пусть даже ценой увеличения длины экс­ перимента.

Хотя подобные эксперименты уже применяются на практике, их теория не нашла достаточно полного отражения в литературе. В данной главе рассмотрены некоторые вопросы теории таких экс­ периментов.

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

Здесь с применением вероятностных экспериментов решаются следующие задачи. Указанный эксперимент проводится с автома­ том, у которого фиксировано множество допустимых начальных со­ стояний (в терминологии Штарке [70] такой автомат называется слабоинициальным) и задано произвольное разбиение этого множе­ ства. Найдены необходимые и достаточные условия возможности определения класса разбиения, содержащего фактическое началь­ ное состояние автомата, если эксперимент продолжается достаточно долго. Условия возможности нахождения начального состояния автомата и распознавания автомата известного класса вытекают из упомянутых выше условий. Показана возможность эффективной проверки выполнения необходимых и достаточных условий, дана оценка средней длины рассматриваемого эксперимента. Предложен метод построения контролирующего автомата, который при прове­ дении вероятностного эксперимента осуществляет анализ входной и выходной последовательности исследуемого автомата и делает выводы о результате эксперимента. Рассматриваются вопросы конт­ роля исправности автомата вероятностным экспериментом. Мате­ риал этой главы основывается на работах [2, 31.

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

где Р (х/р) — вероятность появления символа х вслед за последо­ вательностью р, є — некоторое положительное число, меньше единицы. Символом d (р) условимся обозначать длину последователь­ ности р. Если принять, что вероятность появления пустой последо­ вательности е вслед за произвольной последовательностью р равна единице, то индукцией по длине последовательности рх можно по­ казать справедливость неравенства

чем и завершается доказательство неравенства (4.2).

Пусть s — произвольное состояние из множества S0 . Определяем

то вероятностный эксперимент по определению класса Кп ($), со­ держащего состояние s, должен продолжаться до тех пор, пока на входе автомата А не появится последовательность, не принадлежа­

на выходе источника случайных сигналов последовательности дли­ ны k, принадлежащей множеству F,' если последовательность р уже появилась. Покажем, что для произвольного натурального числа k справедливо неравенство

Действительно, поскольку множество Qs вместе с любой последо­ вательностью, принадлежащей этому множеству, содержит и все начальные части этой последовательности, то

p

предел монотонной ограниченной последовательности всегда суще­ ствует,™ Р (QJe) = lim Pk (Qs/e) всегда существует.

вать диагностируемым по разбиению П путем вероятностного экспе­ римента, если для произвольного s £ S0 Р (QJe) = 0.

Условимся в дальнейшем под автоматом, диагностируемым по разбиению П, понимать автомат, диагностируемый по разбиению П путем'вероятностного эксперимента.

Пусть слабоинициальный автомат А, диагностируемый по раз­ биению П, находится в начальном состоянии s £ S0. Предположим, что на вход автомата А подаются последовательности от источника случайных сигналов с описанными выше свойствами. Тогда вероят­ ность появления на входе этого автомата последовательности, при­ надлежащей множеству Qs, стремится к нулю по мере того, как последовательности удлиняются. Таким образом, если достаточно долго вести вероятностный эксперимент, то можно утверждать, что с вероятностью, равной единице, на входе автомата появится после­ довательность, которая приведет к определению класса разбиения П, содержащего начальное состояние s.

Формулируемая ниже теорема определяет необходимые и до­ статочные условия диагностируемости слабоинициального автомата по разбиению множества его допустимых начальных состояний.

Докажем, что для произвольного k >- kx вероятность Рк (QJe) больше или равна некоторому положительному числу, не завися­ щему от k. Нетрудно видеть, что

Pa

как p £ Qs и d (p) = kx, то, учитывая (4.2), получаем

Pk(Qs/e)>P(p/e)>e**.

Следовательно, Р (Qs/e) > 0 и автомат А не является диагности­ руемым по разбиению П. Необходимость условия теоремы доказана.

Докажем достаточность. Пусть \S \ = я, |S„| = п0, а р £ X* и s £ S0 — произвольны. Докажем соотношение

os0 = {t£ S0\s Ф t(U) Л X(s, q) = X(t, q)}.