Модификация метода построения тестов для конечных автоматовотносительно неразделимости
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,s1) называется инициальным, если в множествесостояний S выделено начальное состояние s1.
Говорят, что состояние 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, s1)иB= (T, I,O, g, t1)(обозначение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.