Об отличимости состояний конечных автоматов

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

1 Отличимость состояний при искажениях на выходе

1.1 Д-отличимость

р 1.2 /г-отличимость

1.3 ^-отличимость

1.4 Решетчатые автоматы

2 Отличимость состояний при искажениях на входе

2.1 Отличимость множеством слов

2.2 /г-кратная отличимость

2.3 ^-кратная отличимость

2.4 Кратно-приведенные автоматы

3 Сложность безусловных диагностических экспериментов
^ 3.1 Оценка сложности безусловного диагностического
эксперимента

Существенный прогресс в области информационных технологий, наметившийся в последние десятилетия неизбежно ведет к все большему усложнению используемых вычислительных систем. Это делает актуальным проблему тестирования подобных систем, а также создание соответствующего математического аппарата.
Конечные автоматы широко используются при моделировании систем в различных областях, таких, как интегральные микросхемы, некоторые виды программ (лексические анализаторы, поиск по образцу), а в последнее время и в коммуникационных протоколах.
Проблема тестирования конечных автоматов изучалась многими авторами, и в этой области получены математические результаты, имеющие как теоретическое, так и прикладное значение. Самые ранние работы в этой области датируются еще пятидесятыми годами прошлого столетия. В статье Э. Мура "Умозрительные эксперименты с последовательностными машинами" [9] впервые формально определяется понятие эксперимента с автоматами, имеющее центральное значение в области тестирования конечных автоматов. В этой же работе автор получает ряд оценок
сложности некоторых видов экспериментов, а также показывает их достижимость. Более систематическое изучение сложностных характеристик экспериментов с автоматами было проведено А. Гиллом[11]. Им впервые были получены оценки длин различных видов диагностических экспериментов.
Дальнейшее изучение диагностических экспериментов было проведено М.Н. Соколовским[16, 17], который получил асимптотику функции Шеннона длины простого условного диагностического эксперимента для всех состояний автомата, а также достаточно точные оценки для подмножеств состояний. Он также первым обозначил связь между диагностическими экспериментами и сложностью порождения элементов в полугруппах[18].
Еще в работе Мура[9] была получена верхняя оценка длины условного установочного эксперимента. Нижнюю оценку для него, совпадающую с верхней, получил A.A. Карацуба[12], а также, независимо от него, Т. Хиббард[5]. Последний автор также получил точную оценку для безусловного установочного эксперимента.
В последнее время эксперименты с автоматами находят практическое применение в задаче тестирования коммуникационных протоколов, используемых при построении локальных сетей, а также сети Internet[l, 8]. Коммуникационный протокол представляет собой набор правил, регламентирующих процесс обмена информацией в сети. Он описывается некоторым формальным документом, называемым стандартом. У стандарта может быть несколько программных реализаций. Стандарт протокола и его реализации моделируются конечными автоматами. Задача тестирования реализации протокола заключается в проверке того, что
1.4. Решетчатые автоматы
Рис. 1.7.
П-П гш гш
лл _Ш шиш пл гипш
ЛЛ :_Ш ШЛ ШЛ
Рис. 1.8. Примеры графов Серпинского