Реферат по предмету "Математика"


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

Модификация метода построения тестов для конечных автоматовотносительно неразделимости
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.


Не сдавайте скачаную работу преподавателю!
Данный реферат Вы можете использовать для подготовки курсовых проектов.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Сейчас смотрят :

Реферат Shakespear To Be Or Not To Be
Реферат Jungle Essay Research Paper English The Jungle
Реферат Инструменты необходимые для тестирования Linux
Реферат Pythagoras Essay Research Paper Pythagoras Pythagoras was
Реферат Конституционное право зарубежных стран 2 Принципы федерализма
Реферат Исследование влияния технологических параметров на процессы низкотемпературной сепарации
Реферат Fidel Castro Essay Research Paper In every
Реферат Товароведение продовольственных товаров 5
Реферат Изучение возможностей народной игры как средства формирования навыков общения детей старшего дошкольного возраста
Реферат Організація і методика аудиту розрахунків з оплати праці (на прикладі діяльності ЗАТ "ДонецькТурист")
Реферат Аналіз маркетингового середовища на базі ВАТ Мотор Січ 2
Реферат Казахстан на рубеже нашей эры - Государство кангюй
Реферат Смирнова, Александра Осиповна
Реферат Роль Ивана Грозного в развитии Российского государства
Реферат Мониторинг окружающей среды Москвы