Модификация метода построения тестов для конечных автоматов относительно неразделимости (стр. 1 из 3)

Модификация метода построения тестов для конечных автоматов относительно неразделимости

2010

ВВЕДЕНИЕ

Поведение многих дискретных систем (таких как цифровые схемы с памятью или телекоммуникационные протоколы) можно описать моделью с конечным числом переходов, например, моделью конечного автомата. Конечный автомат сопоставляет последовательностям во входном алфавите последовательности в выходном алфавите. Для детерминированных автоматов методы построения проверяющих тестов достаточно хорошо развиты. Для недетерминированных автоматов, в которых одной входной последовательности может сопоставляться несколько выходных последовательностей, тесты активно развиваются, но в основном при тестировании используется предположение "о всех погодных условиях", т.е. предполагается, что есть возможность подавать входную последовательность, пока не пронаблюдаем все выходные реакции на нее. В данной работе изучается и улучшается метод построения тестов для недетерминированных автоматов относительно неразделимости для модели "черного ящика", предложенный в работе [1], в котором не используется ограничение "все погодные условия". Показывается, что избыточность тестов снижается, и при этом тест остается полным.

1. Основные определения и обозначения

1.1 Конечные автоматы и отношения между ними

Автоматом называется пятерка A = (S, I, O, h, s1), где S- множество состояний с выделенным начальным состоянием s1, Iи O- соответственно входной и выходной алфавиты, h ÍS ´I´S ´O- отношение переходов‑выходов. Элементами множества h являются четверки вида (s, i, s¢, o), называемые переходами; при этом говорят, что автомат может перейти из состояния s ÎS под действием входного символа iÎI в состояние s¢ÎS с выдачей выходного символа oÎO, если четверка (s, i, s¢, o) содержится в h.

В случае, когда каждой паре вход-состояние соответствует не более одного перехода, автомат называется детерминированным, а в противном случае – недетерминированным (нд-автомат).

Рисунок 1 – Недетерминированный автомат A (а) и детерминированный автомат B (b)

Обозначим out(s, a) = {b:$s¢ÎS[(s, a, s¢, b) Îh]}, т. е. out(s, a) есть множество выходных реакций автомата в состоянии s на входную последовательность a.

Состояние s¢называется i-преемником состояния s, если существует такой выходной символ oÎO, что четверка (s, i, s¢, o) содержится в h. Множество состояний M¢ÍS называется i-преемником множества состояний MÍS, если M¢есть множество всех i-преемников всех состояний множества M.

Если для любых (s, i, o) ÎS ´I´O в нд-автомате A существует не более одного перехода из состояния s под действием входного символа i с выходным символом o, то говорят, что нд-автомат A является наблюдаемым. Если для каждой пары (s, i) ÎS ´I существует хотя бы одна пара (s¢, o) ÎS ´O, такая что (s, i, s¢, o) Îh, то нд-автомат A называется полностью определенным. В противном случае автомат называется частично определенным или частичным.

Автомат A= (S,I,O,h,s₁) называется инициальным, если в множестве состояний S выделено начальное состояние s₁.

Говорят, что состояние s' достижимо из состояния s в автоматеA, если существует входная последовательность, которая переводит автоматA из состоянияsв состояниеs'. Автомат называется связным, если любое его состояние достижимо из начального состояния[3].

Пусть A= (S, I, O, h, s1), B= (T, I, O, g, t1) – полностью определенные автоматы. Автомат B называется подавтоматом автомата A, если TÍS, t1 = s1 и gÍh. Пересечением автоматовA= (S, I, O, h, s₁)иB= (T, I, O, g, t₁)(обозначение AÇB), назовем максимальный связный подавтомат инициального автомата (S´T, I, O, H, s1t1), в котором отношение переходов H определено следующим образом: (st, i, s¢t¢, o) ÎH Û [(s, i, s¢, o) ÎhÙ(t, i, t¢, o) Îg]. Пересечение автоматов описывает общую часть поведения автоматов Aи B и используется для построения входных последовательностей, различающих эти автоматы.

На рисунке 2 представлены автоматы A, B.

A	1	2	3	4
a	2/13/0	2/0	2/04/1	3/1
b	1/0	2/1	3/0	2/1

B	1	2	3	4
a	2/04/1	2/0	2/11/0	1/1
b	1/0	2/1	3/0	2/1

Рисунок 2 – Автоматы A, B

На рисунке 3 представлен автомат A∩B.

AÇB	1,1	3,2	2,2	2,4
a	3,2/0 2,4/1	2,2/0	2,2/0	—
b	1,1/0	—	2,2/1	2,2/1

Рисунок 3 – Автомат AÇB

При тестировании проверяются различные отношения соответствия между эталонным и проверяемым автоматами.

Пусть A и B – полностью определенные автоматы. Говорят, что состояние s автомата A и состояние tавтомата Bэквивалентны (обозначение: s@t), если "aÎI* [ out(s, a) = out(t, a) ]. Иными словами, множество реакций автомата A в состоянии sна любую входную последовательность α совпадает с множеством реакций автомата B в состоянии t на данную входную последовательность α. В противном случае, состояния s и t не эквивалентны [2].

Автоматы A и B называются эквивалентными (обозначение: A@B), если эквивалентны их начальные состояния, т.е. s₁@t₁. В противном случае, автоматы A и B не эквивалентны. Таким образом, по определению, два автомата эквивалентны, если и только если множества их выходных реакций на каждую входную последовательность совпадают.

Состояние t автомата B называется редукцией состояния s автомата A(обозначение: t£s), если "aÎI* [ out(t, a) Íout(s, a) ], т.е. если для любой входной последовательности множество выходных последовательностей автомата B содержится во множестве выходных последовательностей автомата A. Если t₁£s₁, то автомат B называется редукциейавтомата A.

Состояние s автомата A и состояние t автомата Bнеразделимы (обозначение: s~t), если "aÎI* [ out(s, a) Çout(t, a)¹Æ]. Если $aÎI* [ out(s, a)Çout(t, a)= Æ], то состояния s и tразделимы по a(обозначение: s ≁_t), или просто разделимы(обозначение: s ≁t).Автоматы A и Bнеразделимы, если s₁~t₁. Если s₁≁_t₁, то автоматы A и Bразделимы по a(обозначение: A≁_B), или просто разделимы(обозначение: A≁B); последовательность aназывается разделяющей последовательностью автоматов A и B. Таким образом, автоматы разделимы, если существует входная последовательность, для которой множества выходных последовательностей автоматов не пересекаются. Разделяющая последовательность aÎI* называется кратчайшей, если любая другая входная последовательность, разделяющая автоматы A и B,не короче a.Если автоматы неразделимы, то для любой входной последовательности множества выходных последовательностей автоматов пересекаются.

1.2 Построение разделяющей последовательности

Рассмотрим алгоритм построения разделяющей последовательности, предложенный в работе [4].

Алгоритм 1. Построение разделяющей последовательности для автоматов Aи B

Вход: Автоматы Aи B с входным алфавитом I и выходным алфавитом O

Выход: Кратчайшая разделяющая последовательность для автоматов Aи B(если существует)

Шаг 1. Построить A ÇB. Если автомат AÇB полностью определенный, то автоматы Aи B неразделимы. КОНЕЦ.

Шаг 2. Построить усеченное дерево преемников автоматаAÇB. Корень дерева (0-й уровень дерева) – начальное состояние пересечения; вершины дерева помечены подмножествами состояний пересечения. Пусть уже построены k уровней дерева, k³ 0, для заданной промежуточной вершины k-го уровня, которая помечена подмножеством состояний пересечения P и для заданного входного символа i, в дереве есть ребро, помеченное i, в вершину, помеченную подмножеством всех i-преемников состояний подмножества P. Текущая вершина Current на k-м уровне, помеченная подмножеством состояний P, объявляется терминальной вершиной, если выполняется одно из следующих условий:

1) Существует такой входной символ i, что множество i-преемников подмножества P– пустое множество;

2) Существует вершина на j-м уровне, j < k,помеченная подмножеством состояний R со следующим свойством: для всякого состояния (s',t') ÎR найдется такое состояние (s,t) ÎP, что выполняется (s',t')£ (s,t).

Шаг 3. Если ни один путь в усеченном дереве преемников, построенном на Шаге 2, ни усекается согласно условию 1, то автоматы Aи B неразделимы. КОНЕЦ. Если есть терминальная вершина Leaf, помеченная подмножеством состояний P таким, что для некоторого входного символа i всякое состояние подмножества P не имеет i-преемников, то последовательность ai, где a помечает путь от корня к терминальной вершине Leaf, является разделяющей последовательностью для автоматов Aи B.