В данной работе изучен метод построения полного проверяющего теста относительно модели неисправности <S, (,≁),_m >, предложенный в работе [1]. Область неисправности _m содержит все полностью определенные реализации эталона S с теми же входным и выходным алфавитами, что и у S, и числом состояний не более m, где m – целое положительное число. Такую модель неисправности часто называют моделью "черного ящика".

2. 2. Метод построения полного проверяющего теста относительно модели неисправности <S, (,≁), _m>

Алгоритм 2. Построение полного проверяющего теста относительно модели неисправности <S, (,≁),_m >

Вход: Полностью определенный автомат S и верхняя граница m числа состояний любой реализации S

Выход: Полный проверяющий тест TS относительно модели неисправности <S, (,≁),_m >

Шаг 1. Построим усеченное дерево преемников автомата спецификации S. Корнем дерева на нулевом уровне является начальное состояние s₀ автомата S; вершины дерева помечены подмножествами состояний автомата S . Пусть уже построены j уровней дерева, j 0. Для заданной нетерминальной вершины j^го уровня, помеченной подмножеством состояний К, и для заданного входного символа i, в дереве есть ребра, помеченные символом i, в вершину, помеченную i-преемниками подмножества К. Текущая вершина Current на k^м уровне, k > 0, помеченная подмножеством К состояний из множества S, объявляется листом дерева, если путь из корня в эту вершину содержит 2^|K|m вершин, помеченных подмножествами множества К, и начальное состояние s_{0 не содержится в К. Если начальное состояние принадлежит К, то вершина} Current объявляется листом, если путь из корня в эту вершину покрывает (2^|K|m-1+1) вершин, помеченных подмножествами множества К.

Шаг 2. Включаем в TS каждую входную последовательность, которая помечает путь из корня к листу в усеченном дереве.

В качестве примера рассмотрим спецификацию S, представленную на рисунке 5, и построим полный проверяющий тест относительно модели неисправности <S, (£,≁), Â₂>.

Рисунок 5 - Автомат S

На втором шаге текущая вершина, помеченная состоянием a, объявляется листом, если путь из корня в эту вершину покрывает (2^m−1 + 1) = 3 вершин, помеченных a. Текущая вершина, помеченная состоянием b, объявляется листом, если путь из корня в эту вершину покрывает 2^m = 4 вершин, помеченных b. Наконец, текущая вершина, помеченная подмножеством {a, b}, объявляется листом, если путь из корня в эту вершину покрывает (2^2m−1 + 1) = 9 вершин, помеченных a, b или {a, b}.Полученное по данному алгоритму усеченное дерево преемников представлено на рисунке 6. Суммарная длина полного проверяющего теста составляет 277 символов.

Рисунок 6 – Усеченное дерево преемников, построенное по алгоритму 2

2. 3. Улучшение метода построения полного проверяющего теста относительно модели неисправности <S, (,≁), _m>

4. 3.1 Исследование условий усечения дерева

Алгоритм 2 не доставляет кратчайшего теста. Для иллюстрации этого факта рассмотрим тестовую последовательность xyyyyyyy из предыдущего примера, которой в усеченном дереве преемников (рис. 6) соответствует путь a_xa_yb_y{a,b}_y{a,b}_y{a,b}_y{a,b}_y{a,b}_y{a,b}. Прямым перебором можно убедиться, что если автомат-реализация имеет состояния 1 и 2, тогда соответствующий путь в усеченном дереве Tree_SÇT, построенном по пересечению эталонного автомата и реализации, будет уже усечен после {a1}_x{a2}_y{b1,b2}_y{b1}_y{b2}_y{a,b}, т.к. для подмножества а были перебраны все варианты и из последующих подмножеств его можно исключить. Таким образом, при уточнении условий усечения дерева данную тестовую последовательность можно сократить на 3 символа.

Сократить тестовую последовательность можно также и в более общем случае, когда на рассматриваемом пути дерева перебраны все возможные варианты для состояний некоторого множества P, являющегося подмножеством множества K. Рассмотрим эталонный автомат S, изображенный на рисунке 7, и m=2.

Рисунок 7 - Автомат S

Для подмножества состояний {a, b, c} для усечения дерева по алгоритму 2 необходимо, чтобы путь из корня дерева в листовую вершину покрывал 2^3m-1+1=33 вершины, помеченные подмножествами этого множества. Однако, т.к. на левом пути дерева, представленного на рисунке 8, сначала встречается 8 вершин, помеченных подмножествами {a, b}, а именно такое число вариантов обеспечивает перебор всех подмножеств {a1, a2, b1, b2} в дереве Tree_SÇT, то далее на данном пути подмножество {a, b} из рассмотрения исключается. Таким образом, соответствующий путь в дереве Tree_SÇT будет усечен после {a1}_x{a2,b1,b2}_x{a2,b1}_x{a2,b2}_x{a2}_x{b1}_x{b2}_x{b1,b2}_y{c1,c2}_y{c1}_y{c2}_y{a,b,c}, и длина тестовой последовательности составляет всего 11 символов.

Рисунок 8 – Часть усеченного дерева преемников

2. Естественно, сокращение тестовой последовательности можно также обобщить и для случая, когда на рассматриваемом пути дерева перебираются все подмножества для нескольких подмножеств P_i множества K, в том числе и в случае, когда эти подмножества пересекаются. Данный случай иллюстрирует правый путь дерева, изображенного на рисунке 8. На этом пути дерева сначала перебираются все возможные подмножества для P₁={b}. Для пересекающегося с P₁ множества P₂={a, b} теперь достаточно всего трех вершин, помеченных подмножествами P₂, чтобы были перебраны все возможные подмножества P₂. И соответствующий путь в дереве Tree_SÇT усекается после {a1}_z{b1,b2}_z{b1}_z{b2}_x{a2}_y{c1,c2}_y{c1}_y{c2}_y{a,b,c}, а длина тестовой последовательности составляет 8 символов.

Таким образом, можно модифицировать метод построения полного проверяющего теста относительно модели неисправности <S, (,≁), _m> (алгоритм 2), уточнив условия усечения дерева преемников.

1. 3.2 Модифицированный метод построения полного проверяющего теста относительно модели неисправности <S, (,≁), _m>

Алгоритм 3. Построение полного проверяющего теста относительно модели неисправности <S, (,≁),_m >

Вход: Полностью определенный автомат S и верхняя граница m числа состояний любой реализации S

Выход: Полный проверяющий тест TS относительно модели неисправности <S, (,≁),_m >

Шаг 1. Построим усеченное дерево преемников автомата спецификации S. Корнем дерева на нулевом уровне является начальное состояние s₀ автомата S; вершины дерева помечены подмножествами состояний автомата S . Пусть уже построены j уровней дерева, j 0. Для заданной нетерминальной вершины j^го уровня, помеченной подмножеством состояний К, и для заданного входного символа i, в дереве есть ребра, помеченные символом i, в вершину, помеченную i-преемниками подмножества К. Текущая вершина Current на k^м уровне, k > 0, помеченная подмножеством К состояний из множества S, объявляется листом дерева, если путь из корня в вершину Current содержит:

• 2^(|K|-|P|)m+n вершин, помеченных подмножествами множества К, если s₀ K или s₀ K и s₀ P;

• 2^(|K|-|P|)m-1+n+1 вершин, помеченных подмножествами множества К, если s₀ K и s₀ P;

где P – это такое подмножество состояний из множества K, что до некоторого l^го уровня (l < k) перебраны все возможные подмножества P, а n – это количество вершин на данном пути, помеченных подмножествами К, содержащими подмножества P, которые находятся на уровнях не ниже l^го уровня дерева (если P = , то n = 0). Множество P строится итеративно:

1. P = ;

2. P = P P_i для каждого подмножества P_i множества K, для которого путь из корня в вершину Current содержит (2^|Pi|m-1) вершин, помеченных подмножествами P_i (или (2^|Pi|m-1) вершин в случае s₀ P_i);

3. _{P = P} P_j для всех существующих пар P_i P и P_j P (P_j K) таких, что P_i P_j = Q и путь из корня в вершину Current содержит (2^(|Pj|-|Q|)m-1) вершин, помеченных подмножествами P_j, если s₀ P_j или s₀ Q, либо (2^{(|Pj|-|Q|)m-1}) вершин в случае s₀ P_j.

Шаг 2. Включаем в TS каждую входную последовательность, которая помечает путь из корня к листу в усеченном дереве.

Теорема 2.

Для заданного эталонного автомата S и целого числа m алгоритм 3 доставляет полный проверяющий тест относительно модели неисправности <S, (,≁),_m >.

Доказательство.

1. Рассмотрим самый общий случай – подмножество K состояний из множества S, и начальное состояние s₀ K. Согласно алгоритму 1, вершина усеченного дерева преемников Tree_S, помеченная подмножеством K, объявляется листом дерева, если путь из корня в эту вершину содержит 2^|K|m вершин, помеченных подмножествами множества К. Это соответствует перебору всех возможных подмножеств К в усеченном дереве приемников Tree_ST, построенному по пересечению эталонного автомата S и некоторой реализации T, где К – это подмножество состояний пересечения S  T таких, что первый символ каждой пары из К содержится в К.

Предположим, что существует такое подмножество состояний P из множества K, что до некоторого l^го уровня дерева на пути из корня в вершину Current перебраны все возможные подмножества P. Множество P строится итеративно следующим образом:

Шаг 1. P = .