Тема: Модификация сайта для Государственного Бюджетного Профессионального Образовательного Учреждения Колледж Ейский. Учебная работа № 430113

Учебная работа № 430113. Тема: Модификация сайта для Государственного Бюджетного Профессионального Образовательного Учреждения Колледж Ейский

Выдержка из похожей работы

…….

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

…..я проверяющих тестов достаточно хорошо развиты. Для
недетерминированных автоматов, в которых одной входной последовательности может
сопоставляться несколько выходных последовательностей, тесты активно
развиваются, но в основном при тестировании используется предположение “о
всех погодных условиях”, т.е. предполагается, что есть возможность
подавать входную последовательность, пока не пронаблюдаем все выходные реакции
на нее. В данной работе изучается и улучшается метод построения тестов для
недетерминированных автоматов относительно неразделимости для модели “черного
ящика”, предложенный в работе [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 и используется для построения
входных последовательностей, разли…