Московский государственный университет 2 страница

Предположим, что граф G G удовлетворяет условию достижимости. Теперь опишем алгоритм, строящий синхронизирующую последовательность за полиномиальное время. Возьмем два состояния , найдем кратчайший путь из вершины в (путь длины не больше , и обозначим этот путь как . Очевидно, . Также имеет не больше, чем n-1 состояний. Так же мы поступаем с , берем два различных состояния, находим последовательность , которая переводит их в одно состояние и получаем множество текущих состояний , состоящее из не более чем n-2 состояний. Повторяем данный процесс, пока не получим множество текущих состояний , состоящее только из одного элемента. Это всегда возможно, т.к. G удовлетворяет условию достижимости. Объединение x всех входных последовательностей переводит автомат в состояние , и x есть синхронизирующая последовательность. На рис.4 вершина достижима из череp сигнал a, который переводит автомат в состояние (если начинается в ) и в (если начинается в или ). Имеем ={ , }= (S,a). Так как вершина (, ) достижима из (, ), то ba переводит автомат в состояние , если начинается в или и имеем ={ }= ( ,ba). Таким образом, мы получили синхронизирующую последовательность aba: (S,aba)={ } объединив сигналы a и ba.

Количество раз, когда мы объединяем пары состояний максимально равно n-1, а длина каждой объединяющей последовательности .Таким образом, длина синхронизирующей последовательности не больше . Алгоритм может быть реализован за время O( ). Если на каждом шаге брать пары наиболее близкие к вершине (, ), то максимальная длина синхронизирующей последовательности становится n( -1)/6. Наилучшая известная нижняя оценка .

Для данного автомата можно найти кратчайшую синхронизирующую последовательность, используя дерево решений. В этом случае нам нужно только обозначить каждую вершину дерева множеством текущих состояний, т.е. если вершина v отвечает за вход x, тогда мы обозначаем ее через (S,x). Вершина с наименьшей глубиной d, чье множество текущих состояний состоит только из одного элементоа и есть наикратчайшая синхронизирующая последовательность. Это занимает экспоненциальное время, чтобы построить дерево решений глубины d. По факту, нахождение наикратчайшей синхронизирующей последовательности есть проблема сложности-NP.

3. Идентификация и верификация состояния.

Теперь мы пришли к Проблеме II и к Проблеме III: идентификация состояния и верификация состояния. Мы хотим определить начальное состояние автомата перед тестом, вместо определения финального состояния после теста как в Проблеме I. Задачи становятся труднее: во время теста доопределить нужную информацию, при этом, не внося неопределенности и не теряя информацию о начальном состоянии.

Проблема II (Идентификация Состояния): Нам известна диаграмма переходов автомата M, но начальное состояние неизвестно. Цель заключается в том, чтобы определить начальное состояние автомата M. Это не всегда возможно, т.е. существуют автоматы для которых не существует теста, который позволил бы определить начальное состояние. Входная последовательность, которая решает данную проблему, называется простым диагностическим экспериментом.

Проблема III (Верификация Состояния): Опять же нам известна диаграмма переходов автомата M, но начальное состояние неизвестно. Автомат должен быть в определенном начальном состоянии , нужно проверить так ли это. Опять же, это не всегда выполнимо. Тестовая последовательность, которая решают данную проблему, называется уникальная вход-выходная (УВВ) последовательность для состояния .

3.1. Безусловные диагностические эксперименты.

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

Дан автомат M, хотим идентифицировать его начальное состояние. Это возможно тогда и только тогда, когда автомат имеет простой диагностический эксперимент. Сначала, обсудим безусловные тесты.

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

Например, для автомата на рис.1, ab есть простой диагностический эксперимент, т.к.

Очевидно, что не минимизированный автомат не может иметь простой диагностический эксперимент, т.к. эквивалентные состояния не смогут быть отличимы друг от друга. К тому же, не каждый минимизированный автомат имеет простой диагностический эксперимент. Например, автомат на рис.5 минимизирован: сигнал b разделяет от и , сигнал a разделяет и . Однако, нет ни одной последовательности, которая распознает все состояния одновременно: простой диагностический эксперимент не может начинаться с сигнала a, т.к. мы никогда не сможем какое состояние начальное или , т.к. оба эти состояния переходят в и выдают 0. Соответственно, последовательность не может начинаться с сигнала b, т.к. она не сможет распознать, какое состояние было начальным или . Таким образом, этот автомат не имеет простой диагностический эксперимент.

Не всегда возможно сказать, имеет ли данный автомат простой диагностический эксперимент или нет. Для этой цели нам нужно построить дерево решений, где каждую вершину надо подписывать неопределенностью начальных состояний . Заметим, что последовательность x является простым диагностическим экспериментом тогда и только тогда, когда все блоки состоят из одного элемента. Этот алгоритм имеет экспоненциальное время решения.

3.2. Простые условные диагностические эксперименты.

Определение 3. Простой условный диагностический эксперимент это дерево T с корнем и с n листьями. Внутренние вершины подписаны выходными сигналами, а листья обозначены состояниями конечного автомата так, что: 1) ребра, выходящие из общей вершины имеют различные выходные сигналы, и 2) для каждого листа дерева T, если x,y входная и выходная последовательности, образованные вершинами и ребрами, которые пишутся на пути от корня до листа, и если лист обозначен состоянием ,

тогда . Длина последовательности это глубина дерева.

На рис.7 показан простой условный диагностический эксперимент для конечного автомата на рис.6. Эксперимент начинается с подачи сигнала a, затем разделяется на две части исходя из того, какой получится выходной сигнал 0 или 1. В первом случае подается a, a, затем b и разделяется еще на две части. Если последний выход это 0, то утверждаем, что начальным состоянием было , иначе подаем ba и по выходу определяем какое из и является начальным состоянием. Правую ветвь рассматриваем так же.

Не у всех минимальных автоматов есть простой условный диагностический эксперимент. Например, автомат на рис.5 не имеет таковую (по тем же причинам). Конечно, простые безусловные диагностические эксперименты тоже являются условными. Таким образом, автоматы с простым безусловным диагностическим экспериментом имеют простые условные диагностические эксперименты, также условные могут быть гораздо короче. С другой стороны, автомат может не иметь простой безусловный диагностический эксперимент, но иметь условный. Автомат на рис.6 тому пример. Простой безусловный диагностический эксперимент может иметь вначале только сигнал a, т.к. b объединяет , и . После подачи последовательности, состоящей из сигналов a, семейства множеств неопределенности начальной и текущей состояний выглядят одинаково: ={{ , , },{ , , }}, тем не менее, b не может быть подано на вход, т.к. мы бы не смогли различить и .

Опишем алгоритм существования простого условного диагностического эксперимента. Сначала, рассмотрим условный эксперимент, он может быть представлен как дерево решений T, чьи внутренние вершины обозначены входными сигналами, а ребра выходными. С каждой вершиной u дерева T мы рассматриваем два множества состояний: инициальное множество I(u) и текущее множество C(u). Если x и y соответственно входные и выходные последовательности, записанные на пути от корня до вершины u (не включая ее саму), тогда . Инициальное множество I(u), объединенное с листьями, образует разбиение , множества состояний автомата (каждое начальное состояние ведет к определенному листу дерева решений). Эксперимент T есть простой условный диагностический эксперимент тогда и только тогда, когда дискретно.

Говорим, что входной сигнал a допустим для множества состояний C, если он не объединяет два состояния без возможности их различить, т.е. должно выполняться . Если во время теста подается сигнал a такой, что для двух состояний текущего множества и или , мы теряем информацию безвозвратно, т.к. мы не сможем никогда узнать в каком состоянии был автомат в или . Следовательно, на каждом шаге условного эксперимента мы можем подавать только допустимые сигналы.

Сначала берем разбиение , содержащее в себе один блок со всем множеством состояний. Блок B разбиения , под действием допустимого сигнала a такого, что два состояния из B выдадут разные символы или перейдут в разные блоки, разбивается на подблоки, в которых 2 состояния лежат в одном подблоке тогда и только тогда, когда они выдают одинаковый сигнал в ответ на a и переходят в состояния, находящиеся в одном блоке (старого разбиения). Продолжаем до тех пор, пока (x) не будет дискретным.

Рассмотрим автомат на рис.6. Изначально разбиение состоит из одного блока со всеми состояниями. Входной сигнал недопустим, в отличие от a. Таким образом, переходит в = {{ , , },{ , , }}. Теперь b допустим для первого блока, он оставляет в том же блоке, а и переводит во второй блок. Теперь новое разбиение имеет вид = {{ , { , }, { , , }}. Следующий сигнал aразделяет блок { , , } на { , } и { }. Затем b становится допустимым сигналом для { , } и делит его на { } и { }.

В конце a или b разделяет блок { , }. В конце получили множество , состоящее из блоков с одним элементом. Значит, у данного автомата есть простой условный диагностический эксперимент. Этот алгоритм занимает время O .

3.3. Построение простого условного диагностического эксперимента.

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

Дерево T имеет корень. Каждая вершина дерева обозначена набором состояний, корень подписан набором всех состояний, набор внутренних вершин представляет собой объединение обозначений его потомков. Обозначение листьев образует разбиение начальных состояний множества состояний автомата M. Дерево считается завершенным, если разбиение дискретно. Вдобавок, мы связываем входную последовательность p с каждой внутренней вершиной. Каждое ребро дерева обозначено выходным символом. Далее используется обозначение относительно множества Q и последовательности , его мы используем для обозначения множества состояний для которых, .

Допустимый сигнал a для блока Q текущего разбиения принадлежит одному из трех типов: 1) два или более состояний Q выдают разные выходные сигналы на a, 2) все состояния выдают одинаковые выходные сигналы, но они переходят в более, чем один блок , 3) ни одно из выше упомянутых, т.е. все состояния выдают одинаковый выходной сигнал и переходят в один блок . Определим представление графом , это направленный граф с блоками в качестве вершин и переходами между блоками с одинаковым количеством состояний. Переход обозначается входным символом a и выходным символом o, если a допустимый вход типа 3) для и образует биективное соответствие в с выходом o.

Алгоритм I:

Что нужно: Минимизированный автомат M.

Что получим: Готовое дерево ST, если M имеет простой условный диагностический эксперимент.

Метод:

1) Для начала обозначим дерево ST одной вершиной, корнем, обозначенным тривиальным текущим разбиением.

2) Обозначим за R набор блоков с наибольшей мощностью. это граф, реализующий , а это подграф, образованный R. Для каждого блока B множества R, u(B) будет листом текущего дерева ST, обозначенный как B. Расширяем ST тех пор, пока не станет дискретным.

Случай 1: Если есть допустимый входной символ a для B, тогда связываем сигнал aс вершиной u(B). Каждое подмножество состояний B, которые выдают одинаковый выход, соединяется с u(B) как его лист и подписывается как совокупность этих состояний. Ребро подписано выходным сигналом.

Случай 2: Если же есть допустимый входной символ a типа 2) для B. Пусть v будет низшей вершиной ST, чье обозначение содержит в себе множество (v это не лист). Если это последовательность, связанная с v. Тогда последовательность, связанная с вершиной u(B), имеет вид a . Для каждого потомка v, чье обозначение Q пересекается с , присоединяем к u(B) потомка и обозначаем его как . Ребро, инцидентное с u(B), называется также как и смежное ребро к v.

Случай 3: В противном случае, ищем путь в от B к C, который попадает под случаи 1) и 2). Если такой путь не существует, тогда прерываем процесс и объявляем, что конечный автомат не имеет простой условный диагностический эксперимент. Иначе, обозначим за такой путь. К этому моменту u(C) уже было определено и связана с последовательностью , полученной предыдущими шагами. Расширим дерево как в случае 2) свяжем с u(B) последовательность . Для каждого потомка u(С), чье обозначение Q пересекается с , присоединяем к u(B) потомка с обозначением . Ребро инцидентное с u(B) называется так же, как и смежное ребро к u(C).

Пример: Рассмотрим конечный автомат на рис.6. Дерево для него показано на рис.8. Единственный допустимый сигнал для S это a, который разделяет S на два блока по 3 состояния в каждом. Оба блока рассмотрены за следующую итерацию. Блок с названием имеет допустимый сигнал b типа 2), который переводит его в корень, получает последовательность ba и двух потомков. Блок имеет только допустимый сигнал a типа 3), и имеет путь длины один до графа для , таким образом, имеет сигнал aba. В следующей итерации рассматриваем блоки и . Оба входных сигнала типа допустимы для и имеют тип 2), выбираем a. Тогда последовательность для есть aaba. Блок имеет оба допустимых сигнала типа 3), и оба переводят в . Мы выбираем b и получаем сигнал baaba, где b –допустимый сигнал для , а aaba сигнал для .

Дата добавления: 2015-08-29