Универсальное тестирование в частных классах автоматов

• Автор: Пономаренко, Александр Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Саратов
• Количество страниц: 118 с. : ил.

ГЛАВА 1. ПОСТАНОВКА ЗАДАЧ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ. ИССЛЕДОВАНИЕ НОВОЙ КЛАССИФИКАЦИИ АВТОМАТОВ. ВЫБОР ПОДКЛАССОВ ДЛЯ ИССЛЕДОВАНИЯ МИНИМИЗАЦИИ УНИВЕРСАЛЬНОГО ТЕСТИРОВАНИЯ

1.1. Постановка задач минимизации универсальных тестов

1.2. Описание используемой классификации конечных детерминированных автоматов

1.3. Выбор подклассов для исследования минимизации универсальных тестов

1.4. Некоторые замечания о выборе классов для исследования

ГЛАВА 2. МИНИМИЗАЦИЯ УНИВЕРСАЛЬНЫХ ТЕСТОВ В ИССЛЕДУЕМЫХ ПОДКЛАССАХ

2.1. Исследование структуры универсальных тестов

2.2. Построение двух вариантов универсальных тестов для исследования

2.3. Сокращение универсальных тестов в выбранных подклассах

2.4. Минимальные универсальные тесты в подклассе линейных (4,2,2) -автоматов

ГЛАВА 3. УНИВЕРСАЛЬНОЕ ТЕСТИРОВАНИЕ КОМПОНЕНТЫ СТРУКТУРНОГО АВТОМАТА

3.1. Общие положения структурной теории автоматов
3.2. Задача тестирования компоненты структурного автомата
3.3. Трансляция универсального теста в последовательной композиции автоматов
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ

Конечные автоматы являются одним из важнейших понятий современной математической кибернетики. Различные типы конечных автоматов являются математическими моделями технических устройств, социально-экономических, биологических и других дискретных динамических систем, а также используются для описания программ, алгоритмов и вычислительных процессов. Значение теории автоматов определяется тем, что применение конечных автоматов как математических моделей не ограничивается какой-либо определенной областью исследований, а может использоваться для решения проблем практически в любой области человеческой деятельности от исследования нервной системы человека до административного управления и от проектирования электронных устройств до лингвистики.
В современных информационных технологиях конечные автоматы являются моделью для многих компонентов аппаратного и программного обеспечения: программное обеспечение, используемое для разработки и проверки цифровых схем; лексические анализаторы стандартных компиляторов; программное обеспечение для сканирования (поиск заданных слов, фраз и других шаблонов) больших текстовых массивов, таких как наборы УеЬ-страниц; программное обеспечение для проверки различного рода систем с конечным числом состояний (протоколы связи или защищенной передачи информации).
При разработке теоретических основ кибернетики многие сложные концепции и понятия были выработаны на базе теории конечных автоматов. Теория автоматов порождает ряд легко формулируемых, но далеко не тривиальных проблем. Универсальность теоретического и практического применения теории конечных автоматов определяет актуальность ее дальнейшего развития. Как показано выше, теория конечных автоматов имеет многочисленные приложения в технической и практической кибернетике и информатике, составляет важную часть дискретной математики и

математической кибернетики.
Впервые, автоматы, как абстрактные модели нейронных сетей, были введены в 1943 году в работе Мак-Калокка и Питтса [1]. В дальнейшее автоматы неоднократно использовались для описания нейронных сетей [2].
Определение конечного детерминированного автомата как совокупности пяти объектов: А = (8,Х,У,8,А), где Б, X и У - конечные непустые множества, а 8 и А. (функции переходов и выходов соответственно) - отображения вида: 8:8 х X -» 8 и А: 8 х X -» У, введено в работе [3]. Такой тип автоматов получил название автоматы типа Мили. Другой основной тип конечных детерминированных автоматов - автоматы типа Мура введены в работе [4]. Конечный автомат типа Мура есть пятерка: объектов: А = (8,Х,У,8, р), где 8, X и У - конечные непустые множества, а 8 и р (функции переходов и отметок состояния соответственно) - отображения вида: 8:8хХ->8 и р:8-»У. Равносильность двух этих типов автоматов показана во многих работах, например в работе [5]. Из работы Э. Мура [4] берет начало теория экспериментов с автоматами. В дальнейшем теория конечных автоматов и экспериментов с автоматами получила развитие во многих работах зарубежных и отечественных авторов (см., например [6 - 18]).
Процесс приложения входной последовательности к автомату, наблюдение реакций и построение заключений называется экспериментом. Если прикладываемая последовательность известна заранее, то такой эксперимент называется безусловным, в противном случае, если выбор последующего входного воздействия зависит от полученных выходных сигналов, эксперимент называется условным.
Эксперимент, требующий только одного экземпляра исследуемого автомата, называется простым. Эксперимент, требующий более одного экземпляра автомата, называется кратным.
Задачи распознавания состояния конечного детерминированного автомата условно разделить на два основных вида.

Таблица
Таблицы переходов и выходов Ж - триггера
I <3 0
0 0 0,0 1,1
0 1 0,0 0,0
1 0 1,1 1,1
1 1 1,1 0,0
По таблице переходов и выходов автомата Аж понятно, что его функции переходов и выходов совпадают и определяются полиномом Жегалкина вида: Ц(2,.Г,К) = С>01@(£[©С)К, при этом А.,8еК0^^, следовательно
Аде е ^о1Е§м'
Описанные выше типы триггеров принадлежат классам (2,2,2) -автоматов и (2, 4, 2) - автоматов. Длина универсального теста по оценке полученной Твердохлебовым В.А. составляет: для класса (2, 2,2) - автоматов -28 символов, а для класса (2, 4, 2) - автоматов 1020 символов. Исследование минимизации универсального теста в этих классах может не дать принципиального понижения длины, так как первоначальная длина универсального теста незначительна. Длина универсального теста в классе (4, 2, 2) - автоматов составляет 524306 символов, поэтому исследование
сокращения этой оценки представляется более наглядным подтверждением возможности понижения оценки длины при универсальном тестировании в частных классах автоматов, обладающих специфическими свойствами.
Для Б - триггера и Т - триггера легко строятся эквивалентные им (4,2,2) -автоматы, которые будут обладать теме же свойствами по используемой классификации. В дальнейшем класс (4, 2, 2) -автоматов будет рассмотрен как базисный класс при построении структурных автоматов.
Вышеизложенными положениями определяется выбор класса (4; 2, 2) -автоматов, как исходного класса для исследования минимизации
универсального тестирования в специфических подклассах.