книги из ГПНТБ / Богомолов А.М. Эксперименты с автоматами

П Р Е Д И С Л О В И Е

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

Предлагаемая книга посвящена изложению ряда вопросов теории экспериментов с автоматами.

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

ирядом других исследователей.

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

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

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

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

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

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

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

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

при участии В. А. Твердохлебова). четвертая и пятая — А. С. Барашко.

В в е д е н и е

П Р Е Д В А Р И Т Е Л Ь Н Ы Е С В Е Д Е Н И Я П О Т Е О Р И И Э К С П Е Р И М Е Н Т О В С А В Т О М А Т А М И

1. О с н о в н ы е понятия

Основы теории экспериментов с автоматами сформулированы

вработе Мура [33]. Наиболее полно теория экспериментов изложена

вмонографии Гилла [16]. За время, прошедшее с момента опублико­ вания монографии (1962 г.), появилось большое число новых результатов. Но, несмотря на это, многие важные задачи теории экспериментов еще не решены. Это обусловлено тем, что теория экспериментов с автоматами составляет одну из теоретических основ технической диагностики дискретных систем, в которой постоянно выдвигаются все новые прикладные задачи.

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

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

rfleS, X, Y — конечные множества состояний входных и выходных сигналов соответственно; б — отображение множества S X X во множество S, называемое функцией переходов; к — отображение множества S X X во множество Y, называемой функцией выходов. Значение б (s, х) определяет состояние, в которое перейдет автомат из состояния s под действием входного сигнала х, а значение X (х, s) определяет соответствующий выходной сигнал автомата. Определен­ ный таким образом автомат называют конечным автоматом Мили. В дальнейшем автомат Мили будем называть просто автоматом. Наряду с автоматом Мили определяется автомат Мура, который также представляет собой пятерку объектов (S, X , Y, б, |х), где первые четыре объекта те же, что и у автомата Мили, а \х есть ото­ бражение множества 5 во множество У, называемое функцией от-

меток. Частным случаем автомата Мура при Y = S и \х (s) = s является автомат без выходов (автомат Медведева), который рас­ сматривают как тройку объектов (S, X , б).

Если способ расширения функций специально не определен, то пред­ полагается, что он совпадает с (2).

Часто одно устройство моделирует (реализует) поведение друго­ го устройства. В теории автоматов этому соответствует понятие

подавтомат изоморфен (равен с точностью до обозначения состоя­ ний) автомату Л2 , то автомат Лх называется реализацией поведения состояний автомата А2.

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

Более подробно теория автоматов изложена в монографиях П, 18, 42, 44] и др.

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

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

Эксперименты классифицируются также по числу экземпляров исследуемого автомата, требующихся для их проведения: простые эксперименты, когда нужен единственный экземпляр автомата,

икратные эксперименты, когда требуется более одного экземпляра.

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

Эксперименты по распознаванию состояний автомата разделя­ ются на диагностические и установочные. При проведении диагно­ стического эксперимента решается задача определения начального состояния автомата (перед началом эксперимента). При проведе­ нии установочного эксперимента решается задача определения со­ стояния автомата, в которое он переходит в результате этого экспе­ римента. При этом предполагается, что экспериментатору известны

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

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

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

мальный эквивалентный ему автомат. Автомат называется распозна­ ваемым, если он может быть распознан независимо от своего началь­ ного состояния.

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

2.О с н о в н ы е результаты

Значительная часть монографии [16] посвящена систематизации результатов теории экспериментов с автоматами. Приведем кратко эти результаты.

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

Усеченное дерево называется соответственно установочным и ди­ агностическим. Определены необходимые и достаточные условия (в терминах диагностического дерева) существования простого без­ условного диагностического эксперимента, найдена верхняя оценка длины такого эксперимента (если он существует):

1)л*. (3)

где га — число всех, a k — число допустимых начальных состояний автомата. Показано, что для минимального автомата всегда суще­ ствует кратный как безусловный, так и условный диагностический эксперимент кратности, не превосходящей (k — 1), и длины соответ­ ственно:

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

Для экспериментов по распознаванию автомата, принадлежаще­ го известному конечному классу минимальных автоматов, показа-

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

Существуют автоматы, для которых любая входная последователь­ ность длины N будет установочной. Это значит, что наблюдая вход­ ную и соответствующую ей выходную последовательности длины N, всегда можно определить состояние, в которое переходит автомат по данной входной последовательности. Такие автоматы называются ав­ томатами с конечной памятью порядка N (АКП-ЛО- Рассмотрены эксперименты по распознаванию автомата из класса АКЦ-М, у кото­ рых только входная последовательность (без выходной) длины N пол­ ностью определяет конечное состояние автомата. Показано, что для такого класса всегда существует распознающий простой безуслов­ ный эксперимент длины I < mN + N — 1. Дан метод построения входной последовательности такого эксперимента.

Перейдем к экспериментам по распознаванию входной последо­ вательности. В работе [16] рассматривается класс автоматов без по­ тери информации (АБПИ). АБПИ — это такой автомат, зная на­ чальное состояние которого, реакцию его на неизвестную входнуюпоследовательность и соответствующее конечное состояние его, всегда можно определить неизвестную входную последовательность. Поскольку в экспериментах по распознаванию входной последова­ тельности начальное состояние известно, то для АБПИ установоч­ ный эксперимент является экспериментом по распознаванию неиз­ вестной входной последовательности, поданной на АБПИ.

За время, прошедшее с момента опубликования книги [16],. появилось большое количество результатов, основные из которых приводятся ниже.

Рассмотрим вначале эксперименты по распознаванию состояний автомата. В работе [70] предложен метод нахождения диагности­ ческих и установочных последовательностей, отличный от метода из работы [16]. Этот метод заключается в построении дерева пред­ шественников' состояний автомата и обрыва ветвей этого дерева по специальным правилам. В работе [70] показано, что длина / кратчайшей диагностической последовательности (если она суще­ ствует) удовлетворяет неравенству log m k < / -< п\, где п — чис­ ло состояний, т — число входных сигналов, k — число допустимых начальных состояний^автомата.