ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.06.2024
Просмотров: 103
Скачиваний: 0
но, что необходимым и достаточным условием существования рас познающего эксперимента является условие исключительности класса, когда любые два состояния разных автоматов данного клас са должны быть неэквивалентными. Построение распознающего эксперимента в этом случае сводится к построению некоторого установочного эксперимента, и на основании этого находятся оцен ки его длины. Автомат из класса сильносвязных (п, т, д)-автоматов с п состояниями, т входными и q выходными сигналами всегда мо жет быть распознан простым безусловным экспериментом длины
1 <• |
(2п-\)(дп)тп |
|
я (я - 1) |
(л — 1) І |
Є Х Р |
2 (qn)m |
Существуют автоматы, для которых любая входная последователь ность длины N будет установочной. Это значит, что наблюдая вход ную и соответствующую ей выходную последовательности длины N, всегда можно определить состояние, в которое переходит автомат по данной входной последовательности. Такие автоматы называются ав томатами с конечной памятью порядка N (АКП-ЛО- Рассмотрены эксперименты по распознаванию автомата из класса АКЦ-М, у кото рых только входная последовательность (без выходной) длины N пол ностью определяет конечное состояние автомата. Показано, что для такого класса всегда существует распознающий простой безуслов ный эксперимент длины I < mN + N — 1. Дан метод построения входной последовательности такого эксперимента.
Перейдем к экспериментам по распознаванию входной последо вательности. В работе [16] рассматривается класс автоматов без по тери информации (АБПИ). АБПИ — это такой автомат, зная на чальное состояние которого, реакцию его на неизвестную входнуюпоследовательность и соответствующее конечное состояние его, всегда можно определить неизвестную входную последовательность. Поскольку в экспериментах по распознаванию входной последова тельности начальное состояние известно, то для АБПИ установоч ный эксперимент является экспериментом по распознаванию неиз вестной входной последовательности, поданной на АБПИ.
За время, прошедшее с момента опубликования книги [16],. появилось большое количество результатов, основные из которых приводятся ниже.
Рассмотрим вначале эксперименты по распознаванию состояний автомата. В работе [70] предложен метод нахождения диагности ческих и установочных последовательностей, отличный от метода из работы [16]. Этот метод заключается в построении дерева пред шественников' состояний автомата и обрыва ветвей этого дерева по специальным правилам. В работе [70] показано, что длина / кратчайшей диагностической последовательности (если она суще ствует) удовлетворяет неравенству log m k < / -< п\, где п — чис ло состояний, т — число входных сигналов, k — число допустимых начальных состояний^автомата.
Работа [57] также посвящена проблеме нахождения начального состояния автомата простым экспериментом. При этом предпола гается, что вход и выход автомата подвержены случайным помехам, интерпретируемым как ошибки при считывании входных и выход ных символов. Предлагается некоторый критерий оптимальности входных последовательностей длины I для определения начального состояния. Согласно этому критерию оптимальной считается та вход ная последовательность, у которой (по сравнению с другими вход ными последовательностями такой же длины) больше среднее «рас стояние» между соответствующими выходными последовательнос тями при различных допустимых начальных состояниях. В случае, когда входные последовательности содержат только один ошибоч ный символ, приводится метод, позволяющий сравнительно прос то построить оптимальную входную последовательность.
Задача определения конечного состояния автомата в основном рассматривается для минимальных автоматов. Для простых устано вочных экспериментов наиболее интересный результат получен в работе [46]. Здесь показано, что длина / кратчайшего (как услов ного, так и безусловного) установочного эксперимента с минималь ным автоматом Мили удовлетворяет неравенству (5). Для минималь ного автомата Мура соответствующее неравенство имеет вид
f < ( * » - * - 2 H * - » ) + 1 . |
{ 6 ) |
Оценки в (5) и (6) являются достижимыми. Кроме того, для любых пи k <; п существуют автоматы, для которых длина кратчайшего условного эксперимента равна длине кратчайшего безусловного эксперимента.
При проведении условного диагностического (установочного) эксперимента входная последовательность, подаваемая на автомат, зависит от начального состояния автомата. Поэтому часто условный эксперимент отождествляют с множеством входных последова тельностей, число которых не превышает числа состояний, т. е. каждому состоянию ставится в соответствие входная последова тельность, удовлетворяющая определенным свойствам [46, 52].В ра боте [52] вводится понятие полной длины условного эксперимента, под которой понимается сумма длин последовательностей, из кото рых этот эксперимент состоит. Определяется верхняя оценка полной
длины условного диагностического эксперимента, которая равна k
2 і (п — і + 1)- Показано, что эта оценка достижима. Кроме того,
1=2 доказано, что минимальный эксперимент единственный. Аналогич
ные результаты получены для автоматов Мура.
Задачи диагноза и установки автомата, находящегося в неизвест ном состоянии, допускают естественное обобщение, когда в задаче диагноза требуется узнать начальное состояние с точностью до за данного отношения эквивалентности на множестве допустимых на-
чальных состояний автомата, а в задаче установки требуется опре делить конечное состояние с точностью до заданного отношения эквивалентности на множестве всех состояний автомата. Эти задачи рассматриваются в работах [39, 40]. К обобщенным задачам диагно за и установки сводятся некоторые практически важные задачи, в том числе нахождение неисправностей в автомате, нахождение неис правной компоненты и т. д. Для рассматриваемых задач в работах 139, 40] указываются алгоритмы нахождения простых безусловных
.экспериментов, если они существуют, а также алгоритмы для про верки существования таких экспериментов. Предложенные алго ритмы сводятся к построению и анализу конечных автоматов Раби- на-Скотт [36], которые являются обобщением деревьев из работ [16, 70]. В работе [40] показано, что длина / кратчайшего обобщен
ного |
диагностического эксперимента |
(если |
он существует) удовле |
|
творяет неравенству / < |
п\ — 2п~', |
где п определено выше, at — |
||
число |
классов заданной |
эквивалентности. |
, |
|
Разновидностью установочных последовательностей являются синхронизирующие последовательности, которые переводят автомат из любого состояния в одно и то же состояние. Изучению синхрони зирующих последовательностей посвящена статья [54], где устанав ливаются необходимые и достаточные условия существования таких последовательностей и даются границы их минимальной длины. Если I —• указанная длина, то {п — I ) 2 < / < ; 2" — п — 1.
Рассмотрим эксперименты по распознаванию состояний частич ных автоматов,- функции переходов и выходов которых определены не для всех пар состояние — входной сигнал. В работе [51] пока зано, что если два состояния могут различаться по реакциям на не которую, входную последовательность, то эти состояния могут раз личаться по реакциям на некоторую последовательность длины /.
2л) + 1 |
при |
четном п, |
К |
|
|
2п—1) |
при |
нечетном п. |
Эта оценка достижима при всех п.
В работе [69] приводятся два возможных обобщения понятия синхронизирующей последовательности на случай частичного ав томата. Входная последовательность называется управляемой син хронизирующей (у. с.) последовательностью, если она допустима в каждом состоянии и переводит все состояния в одно и то же состо яние. Входная последовательность называется различимой синхро низирующей (р. с.) последовательностью, если она переводит все состояния, в которых она допустима, в одно и то же состояние. Дана процедура определения: обладает ли данный частичный автомат у. с. и р. с. последовательностями. Приводится пример частичного автомата, для которого существует р. с. последовательность, не
а
являющаяся синхронизирующей ни при каком доопределении ав томата.
В работе [55] рассматривается еще один тип установочных эк спериментов. Автор называет конечный автомат синхронизируе мым порядка N, если N — минимальное число такое, что по любой выходной последовательности длины N можно определить хотя бы одно состояние (включая его место) в соответствующей последо вательности из (N - f 1) состояния. Для проверки синхронизируе мое™ конечного автомата строится ориентированный граф, верши нами которого являются неупорядоченные пары состояний автомата. Доказано, что автомат является синхронизируемым тогда и только тогда, когда построенный граф не содержит циклов, причем макси мальный путь в этом графе с точностью до единицы равен порядку синхронизации.
Ряд работ посвящен оценке величины N для А К П - J V . В работе [16] было показано, что N < - j п (п — 1). В работе [67] показано,
что для всех п существует |
по крайней |
мере два |
А К П - J V |
с /V = |
||
= |
~ п (п — 1) и т — q = 2 |
и существует АКП-Л/ с N = у |
п (п — |
|||
— |
1) — 1 и т = |
q = 2. |
|
|
|
|
|
Значительная часть работы [33] посвящена рассмотрению экс |
|||||
периментов по |
распознаванию автомата |
из класса |
сильносвязных |
|||
(п, яг, (^-автоматов Мура. В этой работе показано, что существует простой безусловный распознающий эксперимент для такого клас са и что длина эксперимента не превосходит величину
га!
В работах [14, 34] эта оценка понижается. Получены оценки, не за висящие от q, равные
2 4 ( ш - 1 ) + 1 ( m + 6)10(я-1)
и
2п- In (rte)m2 "-1 (m —1)
соответственно. Первая оценка несколько хуже другой, однако указанный в [14] способ построения распознающей входной по следовательности не требует перебора всех сильносвязных (п, т, д)-автоматов.
Вкачестве приложений обобщенной установочной задачи в ра боте [39] рассматриваются эксперименты по распознаванию авто мата из заданного конечного класса. В этой работе уточняется ме тод Гилла и показывается, что он не приводит, вообще говоря, к крат чайшему эксперименту.
Вработе [31] рассматривается задача распознавания автомата,, принадлежащего конечному классу автоматов, который получается
врезультате различных неисправностей неповрежденного автома та. Рассматриваемые неисправности соответствуют изменениям
