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

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

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.