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

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

Оригинальный способ построения распознающего эксперимента для класса инициальных автоматов предложен в работе [27]. Автор предлагает находить распознающие последовательности, исходя из регулярных выражений событий, представленных в заданных автоматах некоторым множеством выходных символов.

Применению кратных экспериментов для распознавания автомата Мура посвящена статья [24], в которой решается вопрос, можно ли для данного автомата А найти такой кратный эксперимент, кото­ рый отличал бы А от любого автомата В, если только А и В разли­ чимы. Условимся для автомата А и входной последовательности р обозначать через М (А, р) множество всех последовательностей, которые могут появиться на выходе А при подаче р на вход из все­ возможных состояний в качестве начальных. Автор называет крат­ ный эксперимент (ръ р 2 , р^, где /?!, р 2 , pk — входные по­ следовательности, характеристическим для автомата А, если для вся­ кого автомата В с теми же входными и выходными алфавитами, что

и не имеют его. Основной результат: если автомат А с п состояния­ ми имеет характеристический эксперимент, то эксперимент, состо­

В работе [38] рассмотрена задача распознавания автомата из класса автоматов с заданными множествами S, X и заданной фун­ кцией переходов. Автоматы в этом классе различаются только функциями выходов. Требуется построить эксперимент (названный автором восстанавливающим), распознающий функцию выходов исследуемого автомата. Если известно начальное состояние этого автомата, то построение восстанавливающей последовательности сво­ дится к построению обходного пути по графу автомата, т. е. пути, проходящего через все дуги графа [8] . Найдены необходимое и до­ статочное условие существования обходного пути по графу из фикси­ рованной вершины. Предложен алгоритм построения такого пути и, значит, восстанавливающей последовательности.

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

Пусть известны функции переходов и выходов автомата А, называ­ емого исправным. Пусть задан класс автоматов, которые назовем неисправными. Об исследуемом автомате известно, что он или ис­ правен, или неисправен. Контрольным экспериментом для автома­ та А называется такой эксперимент над исследуемым автоматом, в результате которого можно узнать, является ли исследуемый ав­ томат исправным. Контрольным экспериментам для сильносвязного минимального автомата посвящен ряд работ, начиная с основопо­ лагающей работы [61]. В этих работах рассмотрен случай, когда неисправность не увеличивает числа состояний автомата. В работе [61] показано, что при таких предположениях всегда существует простой контрольный эксперимент длины, не превосходящей вели­ чины та4, (п + 1)!

В случае, когда для автомата А существует диагностическая последовательность длины L , то длина контрольного эксперимента для этого автомата не превосходит

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

В работах [58, 64] предложены процедуры построения контроль­ ных последовательностей в случае, когда для исправного автомата А имеется диагностическая последовательность. При этом верхние оценки длины контрольной последовательности, построенной по предложенным процедурам, ниже оценки (7). Оценка из работы [58] короче оценки из [64] и равна

В работе [66] описана процедура построения контрольных по­ следовательностей для случая, когда автомат А есть определеннодиагностируемый автомат порядка L , т. е. всякая входная после­ довательность длины L является для автомата диагностической. Класс неисправных автоматов тот же. Длина последовательностей, построенных по этой процедуре, не превосходит

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

В работе [65] рассматривается применение безусловных диагно­ стических экспериментов для обнаружения неисправностей сильно­ связных автоматов. Известно, что любой диагностический экспери­ мент инвариантен к начальному состоянию, т. е. при любом началь­ ном состоянии диагностический эксперимент ведет к определению этого состояния. Может оказаться, что перед экспериментом авто-

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

В литературе имеется целый ряд работ, посвященных оценкам длины различных экспериментов «почти для всех» автоматов. В ста­ тье [29] вводится понятие степени различимости автомата. Пусть sat неэквивалентные состояния автомата Л и Ял (s, /) — длина кратчайшего эксперимента, различающего эти состояния. Величи­ на НА = max hA (s, t) (по всем парам неэквивалентных состояний) называется степенью различимости автомата А . Мур [33] показал, что степень различимости любого автомата не больше п— 1. В [29] показано, что «почти все» автоматы обладают степенью разли­ чимости, не превышающей logm log9 п -4- 4, где т — число входных и q — число выходных символов автомата. В статье [29] оценива­ ется также длина характеристического [24] эксперимента, «почти всех» минимальных автоматов. Она не превышает величины logm /i. Характеристические эксперименты для «почти всех» инициальных автоматов рассматриваются также в работе [7]. В статье [30] дается оценка длины кратчайшего простого безусловного установочного эксперимента «почти для всех» приведенных автоматов Мили, ко­ торая равна 5 \ogqn.

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

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

В работе [41] эти эксперименты названы неканоническими. Такие эксперименты рассмотрены в [28], где над автоматом введены следующие операции: установка автомата в заранее известное со­ стояние, проверка того, что автомат находится в заданном состоянии. Подобная операция рассмотрена также в работе [68]. В работе [28] показано, что существует такая последовательность указанных вы-

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

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

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

причем предполагается, что неисправность не увеличивает числа состояний автомата. Предлагается два способа преобразования: первый способ аналогичен предложенному в работе [66]; второй за­ ключается в преобразовании автомата в его реализацию с тем, что­ бы в реализации была компонента типа «счетчик». Эта компонента является определенно-диагностируемым автоматом порядка N. Для каждого способа преобразования дается способ построения контроль­ ного эксперимента.

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

Г л а в а 1

КО Н Т Р О Л Ь Н Ы Е Э К С П Е Р И М Е Н Т Ы

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