Тестирование абстрактных автоматов

В основе тестирования (контроля и диагностики) конечных абстрактных автоматов лежит теория экспериментов с автоматами. Эксперимент над автоматами заключается в следующем:

· на вход автомата подается последовательность входных символов,

· фиксируется реакция автомата (последовательность выходных символов),

· в результате анализа поведения автомата делается заключение о том, в каком состоянии находится автомат и каков закон его функционирования.

При этом предполагается, что исследователю известна таблица переходов/выходов исправного автомата и все варианты возможных таблиц, характеризующих неисправности автомата.

Пусть автомат A при любой возможной неисправности i =1,…, k превращается в один из автоматов { A ₁, A ₂,…, A _k}={ A _i| i =1,…, k }. Тогда задача контроля данного автомата X, который должен работать как автомат A, заключается в выяснении соотношения X=A. Если X ¹ A,то X Î{ A _i| i =1,…, k }. Задача диагностики заключается в определении i, при котором X = A _i.

Пример 7. Автомат A задан таблицей:

	s 1 s 2 s 3
v 1 v 2	s 2/ w 1 s 3/ w 2 s 1/ w 2 s 3/ w 2 s 1/ w 1 s 2/ w 1

или если использовать упрощенную запись, содержащую только индексы состояний, входных и выходных символов:

	1 2 3
	2/1 3/2 1/2 3/2 1/1 2/1

Предположим, что возможны две неисправности, порождающие автоматы A ₁ и A ₂ соответственно:

Клетки таблиц для A ₁ и A ₂, отличающиеся от A, подчеркнуты. Рассмотрим объединение D(A, A ₁, A ₂) автоматов A, A ₁ и A ₂:

	1 2 3 11 21 31 12 22 33
	2/1 3/2 1/2 21/1 31/1 11/2 22/1 32/2 12/1 3/2 1/1 2/1 31/2 11/1 21/1 32/2 12/1 22/1

Проведем установочный эксперимент с автоматом D(A, A ₁, A ₂), т.е. такой эксперимент, который позволит по выходной последовательности однозначно определить состояние, в котором оказался автомат, причем неизвестное начальное состояние может быть любым из множества {1, 2, 3, 1₁, 2₁, 3₁, 1₂, 2₂, 3₃}. Для автомата D(A, A ₁, A ₂) одной из возможных входных установочных последовательностей является v ₁ v ₁ v ₁ v ₂ v ₂, или 11122 (табл.9).

Таблица 9

Начальное состояние	Реакция автомата (выходная последовательность)	Конечное состояние
11 21 31 12 22 33		21 31 11 22 32 12

В данном примере реакция автомата D(A, A ₁, A ₂) на входную последовательность 11122 позволяет однозначно установить начальное и конечное состояния автомата, т.е. последовательность 11122 является установочной.

Эта последовательность позволяет установить неисправность автомата A, т.е. осуществить диагностику автомата, т.е. является ли испытуемый автомат X автоматом A, A ₁ или A ₂.

Для контроля автомата, т.е. для определения истинности утверждения, что X = A, можно использовать более короткую входную последовательность v ₁ v ₁ v ₁, или 111. Предполагается, что множество возможных неисправностей то же, что и в вышеприведенном примере (таблица 9).

Таблица 10 (контролирующая)

Начальное состояние	Реакция автомата (выходная последовательность)	Результат
11 21 31 12 22 33	22- 11- 11-	исправен исправен неисправен неисправен неисправен неисправен неисправен неисправен неисправен

Из таблицы 10 видно, что входные последовательности можно в отдельных случаях прерывать, т.к. в данном примере не обязательно подавить 3 входных символа, в отдельных случаях достаточно двух.

Дата добавления: 2015-10-23