Курсовая работа: Модификация метода построения тестов для конечных автоматов относительно неразделимости
Вход: Полностью определенный автомат S и верхняя граница m числа состояний любой реализации S
Выход: Полный проверяющий тест TS относительно модели неисправности <S, (£,≁),Âm >
Шаг 1. Построим усеченное дерево преемников автомата спецификации S. Корнем дерева на нулевом уровне является начальное состояние s0 автомата S; вершины дерева помечены подмножествами состояний автомата S . Пусть уже построены j уровней дерева, j ³ 0. Для заданной нетерминальной вершины jго уровня, помеченной подмножеством состояний К, и для заданного входного символа i, в дереве есть ребра, помеченные символом i, в вершину, помеченную i-преемниками подмножества К. Текущая вершина Current на kм уровне, k > 0, помеченная подмножеством К состояний из множества S, объявляется листом дерева, если путь из корня в эту вершину содержит 2|K|×m вершин, помеченных подмножествами множества К, и начальное состояние s0 не содержится в К. Если начальное состояние принадлежит К, то вершина Current объявляется листом, если путь из корня в эту вершину покрывает (2|K|×m-1+1) вершин, помеченных подмножествами множества К.
Шаг 2. Включаем в TS каждую входную последовательность, которая помечает путь из корня к листу в усеченном дереве.
В качестве примера рассмотрим спецификацию S, представленную на рисунке 5, и построим полный проверяющий тест относительно модели неисправности <S, (£,≁), Â2>.
| S | a | b |
| x | a/0,1,2,3 | a/1,2 |
| y | b/1,2 |
a/0 b/3 |
Рисунок 5 - Автомат S
На втором шаге текущая вершина, помеченная состоянием a, объявляется листом, если путь из корня в эту вершину покрывает (2m−1 + 1) = 3 вершин, помеченных a. Текущая вершина, помеченная состоянием b, объявляется листом, если путь из корня в эту вершину покрывает 2m = 4 вершин, помеченных b. Наконец, текущая вершина, помеченная подмножеством {a, b}, объявляется листом, если путь из корня в эту вершину покрывает (22m−1 + 1) = 9 вершин, помеченных a, b или {a, b}.Полученное по данному алгоритму усеченное дерево преемников представлено на рисунке 6. Суммарная длина полного проверяющего теста составляет 277 символов.
Рисунок 6 – Усеченное дерево преемников, построенное по алгоритму 2
3. Улучшение метода построения полного проверяющего теста относительно модели неисправности <S, (£,≁), Âm>
3.1 Исследование условий усечения дерева
Алгоритм 2 не доставляет кратчайшего теста. Для иллюстрации этого факта рассмотрим тестовую последовательность xyyyyyyy из предыдущего примера, которой в усеченном дереве преемников (рис. 6) соответствует путь axayby{a,b}y{a,b}y{a,b}y{a,b}y{a,b}y{a,b}. Прямым перебором можно убедиться, что если автомат-реализация имеет состояния 1 и 2, тогда соответствующий путь в усеченном дереве TreeSÇT, построенном по пересечению эталонного автомата и реализации, будет уже усечен после {a1}x{a2}y{b1,b2}y{b1}y{b2}y{a,b}, т.к. для подмножества а были перебраны все варианты и из последующих подмножеств его можно исключить. Таким образом, при уточнении условий усечения дерева данную тестовую последовательность можно сократить на 3 символа.
Сократить тестовую последовательность можно также и в более общем случае, когда на рассматриваемом пути дерева перебраны все возможные варианты для состояний некоторого множества P, являющегося подмножеством множества K. Рассмотрим эталонный автомат S, изображенный на рисунке 7, и m=2.
| S | a | b | c |
| x |
a/0 b/1 |
a,b/1 | a/1 |
| y | a,b/0 | c/1 |
b/1 c/0 |
| z | b/1 | b/0 | a/0 |
Рисунок 7 - Автомат S
Для подмножества состояний {a, b, c} для усечения дерева по алгоритму 2 необходимо, чтобы путь из корня дерева в листовую вершину покрывал 23m-1+1=33 вершины, помеченные подмножествами этого множества. Однако, т.к. на левом пути дерева, представленного на рисунке 8, сначала встречается 8 вершин, помеченных подмножествами {a, b}, а именно такое число вариантов обеспечивает перебор всех подмножеств {a1, a2, b1, b2} в дереве TreeSÇT, то далее на данном пути подмножество {a, b} из рассмотрения исключается. Таким образом, соответствующий путь в дереве TreeSÇ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 – Часть усеченного дерева преемников
Естественно, сокращение тестовой последовательности можно также обобщить и для случая, когда на рассматриваемом пути дерева перебираются все подмножества для нескольких подмножеств Pi множества K, в том числе и в случае, когда эти подмножества пересекаются. Данный случай иллюстрирует правый путь дерева, изображенного на рисунке 8. На этом пути дерева сначала перебираются все возможные подмножества для P1={b}. Для пересекающегося с P1 множества P2={a, b} теперь достаточно всего трех вершин, помеченных подмножествами P2, чтобы были перебраны все возможные подмножества P2. И соответствующий путь в дереве TreeSÇ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), уточнив условия усечения дерева преемников.
3.2 Модифицированный метод построения полного проверяющего теста относительно модели неисправности <S, (£,≁), Âm>Алгоритм 3. Построение полного проверяющего теста относительно модели неисправности <S, (£,≁),Âm >
Вход: Полностью определенный автомат S и верхняя граница m числа состояний любой реализации S
Выход: Полный проверяющий тест TS относительно модели неисправности <S, (£,≁),Âm >
Шаг 1. Построим усеченное дерево преемников автомата спецификации S. Корнем дерева на нулевом уровне является начальное состояние s0 автомата S; вершины дерева помечены подмножествами состояний автомата S . Пусть уже построены j уровней дерева, j ³ 0. Для заданной нетерминальной вершины jго уровня, помеченной подмножеством состояний К, и для заданного входного символа i, в дереве есть ребра, помеченные символом i, в вершину, помеченную i-преемниками подмножества К. Текущая вершина Current на kм уровне, k > 0, помеченная подмножеством К состояний из множества S, объявляется листом дерева, если путь из корня в вершину Current содержит:
· 2(|K|-|P|)×m+n вершин, помеченных подмножествами множества К, если s0 Ï K или s0 Î K и s0 Î P;
· 2(|K|-|P|)×m-1+n+1 вершин, помеченных подмножествами множества К, если s0 Î K и s0 Ï P;
где P – это такое подмножество состояний из множества K, что до некоторого lго уровня (l < k) перебраны все возможные подмножества P, а n – это количество вершин на данном пути, помеченных подмножествами К, содержащими подмножества P, которые находятся на уровнях не ниже lго уровня дерева (если P = Æ, то n = 0). Множество P строится итеративно:
1. P = Æ;
2. P = P È Pi для каждого подмножества Pi множества K, для которого путь из корня в вершину Current содержит (2|Pi|×m-1) вершин, помеченных подмножествами Pi (или (2|Pi|×m-1) вершин в случае s0 Î Pi);
3. P = P È Pj для всех существующих пар Pi Î P и Pj Ï P (Pj Ì K) таких, что Pi Ç Pj = Q и путь из корня в вершину Current содержит (2(|Pj|-|Q|)×m-1) вершин, помеченных подмножествами Pj, если s0 Ï Pj или s0 Î Q, либо (2(|Pj|-|Q|)×m-1) вершин в случае s0 Î Pj.
Шаг 2. Включаем в TS каждую входную последовательность, которая помечает путь из корня к листу в усеченном дереве.
Теорема 2.
Для заданного эталонного автомата S и целого числа m алгоритм 3 доставляет полный проверяющий тест относительно модели неисправности <S, (£,≁),Âm >.
Доказательство.
1. Рассмотрим самый общий случай – подмножество K состояний из множества S, и начальное состояние s0 Ï K. Согласно алгоритму 1, вершина усеченного дерева преемников TreeS, помеченная подмножеством K, объявляется листом дерева, если путь из корня в эту вершину содержит 2|K|×m вершин, помеченных подмножествами множества К. Это соответствует перебору всех возможных подмножеств К¢ в усеченном дереве приемников TreeST, построенному по пересечению эталонного автомата S и некоторой реализации T, где К¢ – это подмножество состояний пересечения S T таких, что первый символ каждой пары из К¢ содержится в К.
Предположим, что существует такое подмножество состояний P из множества K, что до некоторого lго уровня дерева на пути из корня в вершину Current перебраны все возможные подмножества P. Множество P строится итеративно следующим образом:
Шаг 1. P = Æ.
Шаг 2. P = P È Pi для каждого подмножества Pi множества K, для которого путь из корня в вершину Current содержит (2|Pi|×m-1) вершин, помеченных подмножествами Pi. Добавление каждого такого Pi в множество P справедливо, т.к. если путь содержит указанное количество повторов, то этим перебираются все возможные варианты подмножеств Pi.
Шаг 3. P = P È Pj для всех существующих пар Pi Î P и Pj Ï P (Pj Ì K) таких, что Pi Ç Pj = Q и путь из корня в вершину Current содержит (2(|Pj|-|Q|)×m-1) вершин, помеченных подмножествами Pj. В данном случае Pi уже было добавлено в P на шаге 2, и для него уже встретилось (2|Pi|×m-1) вершин, помеченных подмножествами Pi. Следовательно, для Pj, пересекающегося с Pi, на данном пути дерева уже точно содержится (2|Q|×m-1) вершин, помеченных подмножествами Pj, значит для того, чтобы были перебраны все варианты подмножеств Pj, достаточно встретить еще (2(|Pj|-|Q|)×m-1) вершин.
Для построенного таким образом P (если P ¹ Æ) на соответствующем пути в дереве TreeST будут перебраны все возможные подмножества P¢ (P¢ – это подмножество состояний S T таких, что первый символ каждой пары из P¢ содержится в P). Значит, далее на данном пути в дереве TreeST из рассмотрения можно исключить вершины, помеченные подмножествами К¢, которые содержат подмножества P¢ – поэтому рассматриваемых вершин, помеченных подмножествами K, не содержащих подмножеств P, будет 2(|K|-|P|)×m . Но также необходимо учесть все n вершин, помеченных подмножествами К, содержащими подмножества P, которые встретились на рассматриваемом пути в дереве TreeS выше, чем lй уровень, т.к. из данных вершин подмножества P исключать не можем. Следовательно, количество вершин, помеченных подмножествами K, для усечения дерева в таком случае составляет 2(|K|-|P|)×m+n вершин.
2. Далее рассмотрим случай, когда s0 Î K, но s0 не принадлежит множеству P. По алгоритму 1 для случая s0 Î K вершина, помеченная подмножеством K, объявляется листом, если путь из корня в данную вершину содержит (2|K|×m-1+1) вершин, помеченных подмножествами множества K. Если же на данном пути для каждого Pi Î P встретилось, как и в предыдущем случае, необходимое число вершин, помеченных подмножествами Pi, то листовой будет являться вершина, путь из корня в которую содержит 2(|K|-|P|)×m-1+n+1 вершин, помеченных подмножествами K.
3. Если s0 Î K и s0 Î P, т.е. s0 принадлежит одному из подмножеств Pj Î P, то необходимо, чтобы на рассматриваемом пути дерева встретилось (2|Pj|×m-1) вершин, помеченных подмножествами Pj, если Pj добавляется к P на шаге 2 построения множества P, либо (2(|Pj|-|Q|)×m-1) вершин – если на шаге 3. Для остальных подмножеств Pi из P требуется встретить такое же количество вершин, как и в случае 1. Тогда можно исключить подмножества P из вершин, помеченных подмножествами K начиная с lго уровня, и вершина, помеченная подмножеством K, объявляется листом, если путь из корня в данную вершину содержит 2(|K|-|P|)×m+n вершин, помеченных подмножествами множества K.
4. Если для данного пути дерева P = Æ, то |P| = 0, n = 0 и пользуемся алгоритмом 2.
На рисунке 9 представлено усеченное дерево преемников для спецификации, изображенной на рис. 5, построенное согласно алгоритму 3. Суммарная длина полного проверяющего теста в этом случае составляет 200 символов, что на 77 символов меньше, чем для алгоритма 2.
Рисунок 9 – Усеченное дерево преемников, построенное по алгоритму 3
ЗАКЛЮЧЕНИЕ
В данной работе изучен метод построения тестов для недетерминированных автоматов относительно модели "черного ящика", предложенный в работе [1]. Этот метод, в отличие от других методов синтеза тестов для недетерминированных автоматов, не ориентирован на выполнение предположения "о всех погодных условиях". Исследованы возможные подходы к улучшению рассмотренного метода и предложена модификация данного метода. Показано, что тест, построенный согласно модифицированному методу, будет по-прежнему полным, но при этом менее избыточным.
ЛИТЕРАТУРА
1. Natalia Shabaldina, Khaled El-Fakih, Nina Yevtushenko. Testing Nondeterministic Finite State Machines With Respect to the Separability Relation. Lecture Notes in Computer Science, 2007(4581), pp. 305-318.
2. Шабалдина Н.В., Евтушенко Н.В. Построение тестов для конечных автоматов относительно неразделимости. Вестник ТГУ. Приложение. Серия "Математика. Кибернетика. Информатика". 2007. № 23. С. 287– 290.
3. Евтушенко Н.В., Петренко А.Ф., Ветрова М.В. Недетерминированные автоматы: анализ и синтез. Ч. 1. Отношения и операции. – Томск: Томский государственный университет, 2006. 142 с.
4. Евтушенко Н.В., Спицина Н.В. О верхней оценке длины разделяющей последовательности
