ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.06.2024
Просмотров: 101
Скачиваний: 0
А К А Д Е М И Я Н А У К У К Р А И Н С К О Й С С Р И Н С Т И Т У Т П Р И К Л А Д Н О Й М А Т Е М А Т И К И И М Е Х А Н И К И
А. М. Б О Г О М О Л О В
А. С . Б А Р А Ш К О И. С . Г Р У Н С К И Й
ЭКСПЕРИМЕНТЫ С АВТОМАТАМИ
И З Д А Т Е Л Ь С Т В О « Н А У К О В А Д У М К А » К И Е В — 1 9 7 3
научно - ті
6Ф0.1 |
ЭКЗЗДГЛДО |
і |
Б74 |
Ч И Т А Л Ь Н О Г О <5дЛА |
f |
У Д К 51.621.391
Книга посвящена некоторым вопросам теории эксперимен тов с автоматами и ее применения в технической диагностике. Рассматриваются контрольные эксперименты, эксперименты по распознаванию автомата известного класса, вероятностные эк сперименты с сетями автоматов. Кроме того, исследуется возмож ность улучшения диагностических свойств автомата с помощью выведения контрольных точек.
Книга будет полезной специалистам в области теории авто матов и вычислительной техники, а также студентам и аспиран там соответствующих специальностей.
О т в е т с т в е н н ы й |
р е д а к т о р |
доктор технических наук П. П. П а р х о м е н к о
Р е ц е н з е н т ы :
кандидат физико-математических наук Е. Я- Е л и з а р о в , кандидат технических наук А. И. К у з ь м и ч е в
Редакция физико-математической литературы Зав. редакцией И. В. Евсеенко-Мисюренко
в 0242—067 2-73 Л1221(04)—73
© Издательство «Наукова думка», 1973 г.
П Р Е Д И С Л О В И Е
Теория экспериментов с автоматами является теоретической ос новой технической диагностики дискретных устройств. Задачи технической диагностики приобретают большое научное и прик ладное значение в связи с повсеместным использованием дискрет ных устройств и возрастанием их сложности.
Предлагаемая книга посвящена изложению ряда вопросов теории экспериментов с автоматами.
Впервые основные задачи теории экспериментов с автомата ми были сформулированы Муром. В дальнейшем в этой области было получено значительное число интересных результатов, определенная систематизация которых была выполнена Гиллом
ирядом других исследователей.
Вданной книге изложены результаты, полученные авторами, в последнее время и связанные лишь с некоторыми разделами теории экспериментов с автоматами. Каждая из глав книги может читаться независимо от других глав.
Во введении приведены основные понятия теории экспери ментов с автоматами и дан обзор основных результатов в этой области, позволяющий получить общее представление о совре менном состоянии этой теории.
Первая глава посвящена изучению контрольных экспери ментов, проводимых с целью определения исправности автомата. Выделяется класс процедур построения экспериментов с более короткими оценками длины, чем контрольные эксперименты, исследованные Хенни, Каймом, Гоненцем.
Во второй главе формализованы правила вывода заключений, основанных на результатах безусловного и условного эксперимен тов по распознаванию автоматов известного класса, исследована устойчивость установочных последовательностей.
В третьей главе изучены свойства частичных тестов, исполь зуемых при распознавании автоматов известного класса, и пред ложен метод направленного поиска частичных тестов.
Четвертая глава посвящена изучению возможности использова ния для контроля и диагноза автомата так называемых вероят ностных экспериментов, при проведении которых входная после довательность задается не экспериментатором, а источником случайных сигналов с определенными свойствами.
В пятой главе рассмотрены вопросы контроля и диагноза сетей автоматов и решена задача определения неисправной компонен ты сети путем измерений на входе и выходе сети.
Шестая глава посвящена изучению методов преобразования произвольных автоматов, которое можно интерпретировать как выведение контрольных точек для обеспечения заданного уровня
контроля и диагноза. |
|
Первая и шестая |
главы написаны И. С. Грунским, вторая |
и третья главы — А. |
М. Богомоловым (вторая глава написана |
при участии В. А. Твердохлебова). четвертая и пятая — А. С. Барашко.
В в е д е н и е
П Р Е Д В А Р И Т Е Л Ь Н Ы Е С В Е Д Е Н И Я П О Т Е О Р И И Э К С П Е Р И М Е Н Т О В С А В Т О М А Т А М И
1. О с н о в н ы е понятия
Основы теории экспериментов с автоматами сформулированы
вработе Мура [33]. Наиболее полно теория экспериментов изложена
вмонографии Гилла [16]. За время, прошедшее с момента опублико вания монографии (1962 г.), появилось большое число новых результатов. Но, несмотря на это, многие важные задачи теории экспериментов еще не решены. Это обусловлено тем, что теория экспериментов с автоматами составляет одну из теоретических основ технической диагностики дискретных систем, в которой постоянно выдвигаются все новые прикладные задачи.
Данная монография не претендует на изложение всех основных результатов теории экспериментов с автоматами, и ее содержание составляют результаты, полученные авторами, а также та часть результатов, которая использована авторами как исходная. Во вве дении мы изложим основные понятия теории экспериментов с автома тами и сделаем краткий обзор состояния этой теории в настоящее время.
Рассмотрим устройство, которое имеет входной и выходной ка налы и может находиться в конечном числе внутренних состояний. На входной канал могут подаваться сигналы, имеющие конечное число значений. Под воздействием входного сигнала устройство, в зависимости от внутреннего состояния, переходит в некоторое со стояние и выдает на выходном канале соответствующий выходной сигнал. Математической моделью такого устройства является авто мат, представляющий собой пятерку объектов
А = (S, X, Y, б, X),' |
(1) |
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 , б).
Автомат |
А' |
= (S', |
X ' , У, б', X') называется |
а |
подавтоматом |
ав |
|||||||
томата /1 (1), еслий' |
s S , |
X ' |
е |
X , У ^ Y, |
функции |
б' |
и X' |
||||||
совпадают с |
функциями б и X на подмножестве S' |
х |
X ' множества |
||||||||||
S X X . |
|
|
|
|
|
|
|
|
|
|
|
|
|
Пусть р |
= |
х1х2...хк—последовательность |
|
элементов |
множе |
||||||||
ства X . Число |
d (р) = |
/г называется длиной |
последовательности р. |
||||||||||
Обозначим через X* множество всех последовательностей конечной |
|||||||||||||
длины из элементов множества X, |
пополненное последовательностью |
||||||||||||
е нулевой |
длины — пустой |
последовательностью. |
|
|
|
||||||||
Расширим функции переходов и выходов автомата А на множес |
|||||||||||||
тво X* согласно рекурсивным формулам |
|
|
|
|
|
|
|||||||
6(s, |
e)=s, |
6(s, |
px) |
= |
8(8{s, |
p), |
x), |
|
|
|
|
|
|
X(s, |
e) = e, |
X(s, |
px) |
= |
X(s, |
p)X(8(s, |
p), |
x). |
|
|
|||
Значение функции б (s, p) определяет состояние автомата, в ко |
|||||||||||||
торое он переходит из состояния |
s под действием последовательнос |
||||||||||||
ти р; значение функции X (s, р) |
определяет ту выходную последова |
||||||||||||
тельность, которую выдает автомат, осуществляя переход |
из |
со |
|||||||||||
стояния s под действием последовательности |
р. |
|
|
|
|
|
|||||||
Возможны |
и другие способы |
расширения |
функций автомата. |
Если способ расширения функций специально не определен, то пред полагается, что он совпадает с (2).
Пусть даны автоматы Ах |
= (Slt X , Y, |
б ъ Хх) |
и А2 |
= |
(S2, X , Y, |
||||
б2 , Х2). Состояния s1 автомата Аг |
и s2 автомата А2 |
называются экви |
|||||||
валентными, если для всех входных последовательностей р из X* вы |
|||||||||
полняется |
равенство |
|
|
|
|
|
|
|
|
|
|
M s i > Р) = M S 2> Р)- |
|
|
|
|
|||
Автоматы Аг |
и А2 называются эквивалентными, |
если |
для |
каждо |
|||||
го состояния |
автомата Ах |
найдется эквивалентное ему |
состояние |
||||||
автомата А2, |
и наоборот. Автомат называется минимальным (приве |
||||||||
денным), |
если любые два его различных |
состояния |
не |
являются |
|||||
эквивалентными. Минимальный |
автомат |
имеет |
наименьшее |
число |
|||||
состояний |
среди всех эквивалентных ему |
автоматов. |
|
|
|
Часто одно устройство моделирует (реализует) поведение друго го устройства. В теории автоматов этому соответствует понятие
реализации |
одного автомата другим автоматом. |
|
|
Автомат |
Лх называется |
реализацией автомата Л2 , е |
с л и автомат |
Аг содержит подавтомат, |
эквивалентный автомату А2. |
Если этот |
подавтомат изоморфен (равен с точностью до обозначения состоя ний) автомату Л2 , то автомат Лх называется реализацией поведения состояний автомата А2.
Автомат называется сильносвязным, если для любой пары его
состояний (sx , |
s2) найдется |
входная последовательность, переводя- |
• щая автомат |
из состояния |
sx в состояние s2. |
Более подробно теория автоматов изложена в монографиях П, 18, 42, 44] и др.
Изложим основные понятия теории экспериментов с автоматами. Под экспериментом с автоматом обычно понимается процесс прило жения входных последовательностей к автомату, наблюдения со ответствующих выходных последовательностей и вывода заключе ний, основанных на этих наблюдениях. При этом почти всегда предполагается, что автомат, с которым экспериментируют, явля ется опечатанным «черным ящиком», в котором для эксперимента тора доступны только входной и выходной каналы. Под длиной эксперимента понимают длину входной последовательности, подз ываемой на автомат при проведении эксперимента.
По способу проведения эксперимента с автоматом различают безусловные и условные эксперименты. При безусловном экспери менте входная последовательность определяется заранее до про ведения эксперимента. При условном эксперименте входная после довательность состоит из ряда подпоследовательностей, каждая из которых (кроме первой) определяется на основании реакций, вы зываемых предыдущими подпоследовательностями.
Эксперименты классифицируются также по числу экземпляров исследуемого автомата, требующихся для их проведения: простые эксперименты, когда нужен единственный экземпляр автомата,
икратные эксперименты, когда требуется более одного экземпляра.
Взависимости от цели эксперимента различаются эксперимен ты по распознаванию состояний автомата, распознаванию входной последовательности и распознаванию автомата из известного конеч ного класса автоматов.
Эксперименты по распознаванию состояний автомата разделя ются на диагностические и установочные. При проведении диагно стического эксперимента решается задача определения начального состояния автомата (перед началом эксперимента). При проведе нии установочного эксперимента решается задача определения со стояния автомата, в которое он переходит в результате этого экспе римента. При этом предполагается, что экспериментатору известны
.функция переходов, функция выходов исследуемого автомата и то, что автомат находится в состоянии, принадлежащем множе ству допустимых начальных состояний.
Цель эксперимента по распознаванию неизвестной входной по следовательности состоит в' определении этой последовательности, если экспериментатору известны функции переходов и выходов автомата, его начальное состояние и выходная последовательность, являющаяся реакцией на неизвестную входную последовательность. Этот эксперимент проводится с автоматом после подачи на его вход неизвестной последовательности.
Практическое приложение в технической диагностике имеют эксперименты по распознаванию автомата из известного конечного класса автоматов. Говорят, что автомат распознан путем экспери мента с ним, если в результате этого эксперимента определен мини-
мальный эквивалентный ему автомат. Автомат называется распозна ваемым, если он может быть распознан независимо от своего началь ного состояния.
В заключение отметим, что введение понятий теории автоматов, которые не рассматривались в этом разделе, будет производиться по мере надобности. Кроме того, общепринятые обозначения и по нятия математической логики и теории множеств будут применяться без дополнительных разъяснений.
2.О с н о в н ы е результаты
Значительная часть монографии [16] посвящена систематизации результатов теории экспериментов с автоматами. Приведем кратко эти результаты.
При исследовании экспериментов по распознаванию состояний автомата развит метод построения диагностических (установочных) последовательностей, подаваемых на автомат при проведении без условного диагностического (установочного) эксперимента. Метод состоит в построении дерева преемников допустимых начальных состояний и в усечении этого дерева по определенным правилам, различным для установочного и диагностического экспериментов.
Усеченное дерево называется соответственно установочным и ди агностическим. Определены необходимые и достаточные условия (в терминах диагностического дерева) существования простого без условного диагностического эксперимента, найдена верхняя оценка длины такого эксперимента (если он существует):
1)л*. (3)
где га — число всех, a k — число допустимых начальных состояний автомата. Показано, что для минимального автомата всегда суще ствует кратный как безусловный, так и условный диагностический эксперимент кратности, не превосходящей (k — 1), и длины соответ ственно:
l<{n-\)(k-\), |
(4) |
Для минимального автомата всегда существует простой как безуслов ный, так и условный установочный эксперимент длины /, для кото рой выполняются соотношения (4) и (5) соответственно. Для нахож дения установочных последовательностей в этом случае предложен метод (так называемый регулярный эксперимент) значительно более простой, чем метод установочного дерева. При регулярном экспе рименте строится лишь одна ветвь установочного дерева и в резуль тате находятся установочные последовательности (не обязательно минимальной длины).
Для экспериментов по распознаванию автомата, принадлежаще го известному конечному классу минимальных автоматов, показа-