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

Время сложности этого алгоритма O( ), а размер объявленного дерева O( ).

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

Алгоритм II (Простой Условный Диагностический Эксперимент):

Что нужно: Завершенное дерево ST (из I алгоритма).

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

Метод: I и C начальное и текущее множества, которые согласовываются с наблюдаемым выходом (изначально, I=C равные всему набору состояний S). Пока |I|>1 (и таким образом, |C|>1), найдем низшую вершину u дерева, чье обозначение содержит текущее множество C. Применяем входную последовательность , связанную с u, и изменяем I и C в соответствии с выходом.

Пример: Рассмотрим автомат на рис.6, если мы применим Алгоритм II к дереву ST на рис.8, получим простой условный диагностический эксперимент на рис.7. Сначала, подаем символ a – обозначение корня. Допустим выход 0. Тогда начальное множество I={ , , }, а текущее множество C={ , }. Низшая вершина ST, которая содержит C, это , тогда подаем последовательность из : aba. Пусть последний выход 1. Тогда начальное множество I={ , }, C={ , }. Низшая вершина, которая содержит C, это и подаем последовательность ba, после которой мы узнаем начальное состояние. Другие ветви последовательности строятся аналогично.

Алгоритм II имеет длину не больше n(n-1)/2 и строит простой условный диагностический эксперимент за время O( ), имея готовое дерево.

3.4. Верификация состояния.

Переходим к проблеме III. Нужно проверить, что автомат M с известной диаграммой переходов находится в заданном состоянии. Это возможно тогда и только тогда, когда это состояние имеет уникальную вход-выходную последовательность (УВВ).

Определение 4. Уникальная вход-выходная последовательность x состояния s это входная последовательность x такая, что выход, получаемый автоматом с начальным состоянием s отличается от выходных последовательностей, получившихся автоматом с любым другим начальным состоянием, т.е. для любого .

Последовательность x является УВВ последовательностью состояния s тогда и только тогда, когда неопределенность начального состояния содержит s в дискретном блоке { s }. Например, для конечного автомата на рис.5, b является УВВ последовательность для , потому что он выдает 0, когда и выдают 1; состояние не имеет УВВ последовательности, а для это a.

Если автомат имеет простой безусловный или условным диагностический эксперимент, тогда все состояния имеют УВВ последовательности. Более конкретно, если дерево T это простой условный диагностический эксперимент, тогда УВВ последовательность для образуется из подписанных сигналов на пути от корня к листу, который определяет как начальное состояние. Обратное, строго говоря, неверно. С другой стороны, возможно, что ни одно состояние не имеет УВВ последовательность, что только некоторые последовательности имеют ее или что все состояния имеют УВВ последовательность, но это не гарантирует наличие простого диагностического эксперимента.

Предложенные методы нахождения УВВ последовательностей основаны на построении дерева решений, а это занимает экспоненциальное время. Таким образом эта проблема имеет PSPACE-сложность.

4. Тест На Соответствие.

Теперь обсудим Проблему IV: тест на соответствие. У нас имеется полная информация об автомате-эталоне A, известны функции переходов и выходов в виде диаграммы переходов или таблицы состояний. Также, нам дан автомат B (автомат-исполнитель) для которого известно его вход-выходное поведение. Нужно построить тест, который будет проверять, является ли B корректной реализацией A, подавая на вход B тестовую последовательность, затем рассматривая выход.

Очевидно, без каких либо дополнительных условий эта проблема нерешаема; для любой тестовой последовательности можно построить автомат B, не эквивалентный A, но на выходе ничем не отличается от A для данного теста.

Условие 1. a) Автомат A сильно связный граф, b) автомат A минимизирован,c) автомат B не изменяется во время эксперимента и имеет такой же входной алфавит, как и A, и d) автомат B имеет состояний не больше, чем A.

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

. Условие 1 a) должно выполняться, т.к. если A не будет сильно связным, эксперимент начавшийся в B в состоянии, который не может добраться до некоторых состояний не будет корректным, b) мы всегда можем минимизировать A, все равно, тестируя B, мы можем определить его с точностью до класса эквивалентных автоматов, т.к. они имеют одинаковое вход-выходное поведение, c) очевидно.

После этих объявления этих условий, мы хотим создать эксперимент, который проверяет, эквивалентен ли B с A.

Утверждение 1: Пусть A и B удовлетворяют Условию 1, тогда следующие высказывания эквивалентны:1) A и B изоморфны, 2) A и Bэквивалентны, и 3) хотя бы одно состояние A имеет эквивалентное состояние в B.

Заметим, что в описании автомата-эталона не определено начальное состояние. Если автомат содержит объявленное начальное состояние, которое нужно проверить, тогда тест может не существовать, т.к. это уже проблема верификации состояния.

С другой стороны, положим, что автомат B начинает работу из неизвестного состояния, и мы хотим проверить, изоморфен ли он A. Сначала мы подаем последовательность x, которая должна привести B к известному начальному состоянию для основной части теста, который называется тестовый эксперимент и выполняет следующее. Если B изоморфен A, тогда последовательность x приведет B в начальное состояние , потом тестовый эксперимент узнает, изоморфен ли B A. Если же B не изоморфен A, тогда последовательность x, возможно, привела, а возможно и не привела B в состояние , в обоих случая тестовый эксперимент установит неизоморфность B с A: несоответствующие выходы A и B укажут на это.

С этого момента мы полагаем, что автомат B приведен в заданное начальное состояние s .

Определение 5. Пусть A есть конечный автомат с n состояниями и начальным состоянием . Тестовая последовательность для A это входная последовательность x, которая отличает A от всех других автоматов с n состояниями, т.е. любой автомат B с максимум n состояниями, неизоморфный A, в ответ на x выдает последовательность сигналов несовпадающую с выходом A.

Для всех методов тестового эксперимента имеется основная идея. Мы хотим удостовериться в том, что каждый переход в автомате-эталоне A соответственно корректно выполняется в автомате B. Таким образом, для каждого перехода в A, скажем, из состояния в состояние , под действием сигнала a, мы хотим подать последовательность, переводящую автомат в , затем сигнал a, чтобы проверить, что финальное состояние B это , подавая на вход соответствующие входные сигналы. Методы различаются типами подпоследовательностями, которыми они проверяют нахождение автомата в определенном состоянии. Эту роль могут выполнять статусные сообщения, семейства разделяющих последовательностей, простые диагностические эксперименты, уникальные вход-выходные последовательности, характеризующие последовательности и идентифицирующие последовательности. Рассмотрим некоторые из них. Для начала, опишем основные понятия.

Семейство разделяющих последовательностей для автомата A, это набор n множеств , i=1,….n, последовательностей (одно множество для каждого состояния) таких, что для каждой пары состояний и есть последовательность x, которая разделяет их, т.е. , и 2) x является частью каких то последовательностей в и . Мы называем разделяющим множеством состояния , а элементы разделяющими последовательностями.

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

Каждый минимизированный автомат имеет разделяющее семейство. И мы можем построить его следующим образом. Т.к. A минимизирован, можно найти разделяющую последовательность для любых двух состояний и , используя метод из II-A. Затем разбиваем состояния на блоки, в зависимости от их выходов , k=1,…,n; каждое состояние имеет x в своем множестве . Далее, для каждого блока с более чем одним состоянием, повторяем этот процесс пока каждый блок не будет состоять из одного элемента. В результате получаем семейство разделяющих последовательностей таких, что для каждой пары и соответствующие множества и содержат общую последовательность, которая их разделяет. Таких разбиений не больше, чем n-1, а каждое состоит из не более, чем n-1 последовательностей. В итоге этой процедуры получаются разными, но если мы будем включать разделяющую последовательность в , несмотря на то, чтобы входило в разбиение блока, все получатся одинаковыми и каждый из них будет содержать по n-1 последовательностей. Такое множество последовательностей называется множеством характеризующих последовательностей; любые два состояния различимы последовательностью из этого множества. Заметим, что мы хотим, чтобы состояло из наименьшего количества последовательностей.

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

Для следующих высказываний мы объявляем автомат-эталон A=(I,O, , , ), а проверяемый автомат B=(I,O, , , ), и полагаем, что B уже переведен в начальное состояние, которое соответствует состоянию в A.

4.1. Статусные Сообщения и Сброс.

Статусное сообщение информирует нас, каково текущее состояние автомата. Можно представить, что есть специальный символ, в ответ на который автомат выдает текущее состояние и остается в нем. Мы говорим, что статусное сообщение надежно, если оно гарантированно правильно работает в автомате B, т.е. выдает текущее состояние, не меняя его. Тогда тестовая последовательность может быть получена построением эйлерова пути для автомата A и применим в каждой вершине статусное сообщение. После этого можно узнать, подобен ли B A. Если статусное сообщение недостоверное, тогда тестовая последовательность строится, применяя статусное сообщение дважды, каждый раз как автомат переходит в новое состояние, т.е. каждый раз, когда переходим в новую вершину применяем дважды и один раз в остальных случаях.

Например, рассмотрим автомат A на рис.1 с начальным состоянием . Тогда эйлеров путь получается входной последовательностью x=ababab. Пусть s это статусное сообщение, тогда при надежном статусном сообщении x=sasbsasbsasbs, при ненадежном же x=ssasbssasbssasbs.

Мы говорим, что автомат A имеет возможность сброса, если через входной символ r можно попасть в начальное состояние из любого другого состояния, т.е. , для любого . Говорится, что сброс надежен, если он гарантированно правильно работает в автомате B, т.е. , для любого , иначе ненадежно.

Для автоматов с надежным сбросом существует полиномный алгоритм построения тестовой последовательности. Пусть , i=1,….,n семейство разделяющих последовательностей. Для каждого состояния мы имеем часть тестовой последовательности. Сначала, строим остовное дерево (методом поиска в ширину) диаграммы переходов автомата-эталона A и проверяем подобен ли B A. Мы проверяем состояния по алгоритму поиска в ширину и ребра (переходы) ведущие к вершинам (состояниям). Для каждого состояния есть часть тестовой последовательности, которая действует следующим образом для каждого члена : сначала, она переведет автомат в через r, затем подаст входную последовательность (скажем ) соответствующая пути в дереве от корня до и потом применит разделяющую последовательность из . Если же автомат B пройдет этот тест для всех членов , мы узнаем, что B имеет состояние подобное , а именно состояние, полученное входной последовательностью , которая подается после сброса в . Если B проходит все тесты для всех , тогда B подобен A. Эта часть теста проверяет все переходы остовного дерева. В конце мы проверяем переходы, не входящие в дерево. Для каждого перехода, скажем из в через a, мы делаем тоже самое для каждого члена : сбрасываем автомат, подаем последовательность , переводящая автомат в , подаем на вход a, и затем подаем разделяющую последовательность из . Если автомат-реализация B проходит этот тест для всех , тогда переход состояния, подобное , под действием a выдает корректную последовательность и переходит в состояние подобное . Если B проходит этот тест для всех переходов, тогда мы объявляем его изоморфным A.

Пример 3: Для автомата на рис.1, семейство разделяющих последовательностей представляет собой: ={a,b}, ={a}, и ={a,b}. Остовное дерево показано на рис.9 жирными ребрами. Последовательности ra и rb проверяют состояние . Последовательность rba проверяет и переход (s1,s2): после сброса, вход b проверяет переход по ребру дерева из в и разделяющая последовательность из проверяет конечное состояние . Следующие последовательности проверяют состояние и переход из в : rbba и rbbb, где префикс rbb сбрасывает автомат в и переводит в состояние вдоль проверенных ребер, а два суффикса a и b разделяющие последовательности для . В конце мы тестируем ребра не из дерева таким же образом. Например, петля при проверяется последовательностью rbaa.

Проверка B на подобие занимает время: O( ) – на постройку семейства разделяющих последовательностей, O(pn) – построить остовное дерево, O( )- проверить состояние и ребра дерева, и O( ) – проверить переход и его конечное состояние. Всего переходов pn, таким образом, тестовая последовательность длины O( ) строится за время O( ).

Для автоматов с ненадежным сбросом известны лишь случайные полиномные алгоритмы, они строят тестовые последовательности длины за случайное полиномное время.

4.2. Разделяющие Последовательности.

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

Простой диагностический эксперимент подобна ненадежному статусному сообщению тем, что она выдает разные выходы для каждого состояния, но различается тем, что она меняет состояние. Мы включаем простой диагностический эксперимент в каждый для каждого состояния. Сначала проверяем, подобен ли автомат B автомату-эталону A тестовой последовательностью, наблюдая за поведением каждого состояния под действием простого диагностического эксперимента. Затем подтверждаем каждый переход, проверяя конечное состояние все простой тем же экспериментом.

Переводящая последовательность это последовательность, которая переводит автомат из состояния в . Такая последовательность всегда существует, т.к. автомат сильно связный. Очевидно, она не единственна и выбор кратчайшего пути является предпочтительным. Допустим, автомат находится в состоянии , тогда простой диагностический эксперимент переводит автомат в состояние , т.е. , i=1,….,n. Для автомата в начальном состоянии , следующая тестовая последовательность проводит автомат через каждое состояние и показывает каждую из n реакций на простой диагностический эксперимент.

(1)

Начиная в , переводит автомат в состояние и затем переводит его в и выдает ответ на . В конце автомат отвечает на . Если все работает корректно, автомат будет в состоянии и это проверяется простым диагностическим экспериментом . В течение теста мы увидим n реакций автомата на последовательность из различных n состояний. Таким образом, мы проверяем B на подобность автомату-эталону A.

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