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

Содержание к диссертации

Введение 2

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

1. /^-отличимость 23

2. А;-отличимость 37

3. ^-отличимость 41

4. Решетчатые автоматы ' 43

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

5. Отличимость множеством слов 59

6. А;-кратная отличимость 63

7. w-кратная отличимость 77

8. Кратно-приведенные автоматы 80

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

3.1 Оценка сложности безусловного диагностического

эксперимента 88

Введение к работе

Существенный прогресс в области информационных технологий, наметившийся в последние десятилетия неизбежно ведет к все большему усложнению используемых вычислительных систем. Это делает актуальным проблему тестирования подобных систем, а также создание соответствующего математического аппарата.

Конечные автоматы широко используются при моделировании систем в различных областях, таких, как интегральные микросхемы, некоторые виды программ (лексические анализаторы, поиск по образцу), а в последнее время и в коммуникационных протоколах.

Проблема тестирования конечных автоматов изучалась многими авторами, и в этой области получены математические результаты, имеющие как теоретическое, так и прикладное значение. Самые ранние работы в этой области датируются еще пятидесятыми годами прошлого столетия. В статье Э. Мура "Умозрительные эксперименты с последовательностными машинами" [9] впервые формально определяется понятие эксперимента с автоматами, имеющее центральное значение в области тестирования конечных автоматов. В этой же работе автор получает ряд оценок

Введение сложности некоторых видов экспериментов, а также показывает их достижимость. Более систематическое изучение сложностпых характеристик экспериментов с автоматами было проведено А. Гиллом[11]. Им впервые были получены оценки длин различных видов диагностических экспериментов.

Дальнейшее изучение диагностических экспериментов было проведено М.Н. Соколовским[16, 17], который получил асимптотику функции Шеннона длины простого условного диагностического эксперимента для всех состояний автомата, а также достаточно точные оценки для подмножеств состояний. Он также первым обозначил связь между диагностическими экспериментами и сложностью порождения элементов в полугруппах [18].

Еще в работе Мура[9] была получена верхняя оценка длины условного установочного эксперимента. Нижнюю оценку для него, совпадающую с верхней, получил А.А. Карацуба[12], а также, независимо от него, Т. Хиббард[5]. Последний автор также получил точную оценку для безусловного установочного эксперимента.

В последнее время эксперименты с автоматами находят практическое применение в задаче тестирования коммуникационных протоколов, используемых при построении локальных сетей, а также сети Internet [1, 8]. Коммуникационный протокол представляет собой набор правил, регламентирующих процесс обмена информацией в сети. Он описывается некоторым формальным документом, называемым стандартом. У стандарта может быть несколько программных реализаций. Стандарт протокола и его реализации моделируются конечными автоматами. Задача тестирования реализации протокола заключается в проверке того, что

Введение она удовлетворяет данному стандарту, т.е. в построении тестового эксперимента для данного стандарта в классе всех возможных его реализаций.

Задача тестирования конечных автоматов в самой общей постановке заключается в следующем. Имеется экземпляр конечного автомата, о котором известна лишь некоторая априорная информация (например, количество состояний или диаграмма переходов). Необходимо провести эксперимент с данным автоматом, заключающийся в подаче на него некоторых входных последовательностей и наблюдении за выходными, в результате которого мы получим интересующую нас информацию об автомате (например, состояние до эксперимента или диаграмму переходов автомата). Может так случится, что у автомата существует два состояния, находясь в которых он одинаково реагирует на любые входные воздействия. Очевидно, что с точки зрения экспериментатора такие состояния неотличимы и могут рассматриваться как одно состояние. На этом пути возникает понятие отличимости состояний конечного автомата, играющее основополагающую роль в теории экспериментов с автоматами.

Задача нахождения отличающих слов для пар состояний встречается при построении всех основных видов экспериментов. Таким образом, изучение длин отличающих слов является фундаментом при изучении сложности экспериментов с автоматами.

В диссертации исследуются различные обобщения понятия отличимости состояний, возникающие при рассмотрении экспериментов с автоматами, в процессе проведения которых выходная или входная последовательности могут искажаться. Изучается возможность построения отличающих последовательностей, а

Введение также функции Шеннона их сложности. Для всех рассматриваемых видов отличимости получены либо точные значения, либо асимптотические оценки соответствующей функции Шеннона.

Нахождение отличающего слова для пары состояний является частным случаем задачи построения простого безусловного диагностического эксперимента для подмножеств состояний. Поэтому в диссертации также исследуется их сложность. В работе получена асимптотика логарифма функции Шеннона длины простого диагностического эксперимента для подмножества состояний, когда мощность этого подмножества растет с увеличением числа состояний. Заметим, что ранее не было известно даже порядка логарифма этой величины[11, 18].

Модель эксперимента с искажением выходной последовательности вводится с целью учета эффекта снятия выходной информации с заданной погрешностью. Допустим мы проводим эксперимент с реальной физической системой. Тогда мы можем снимать информацию о состоянии системы лишь с некоторой погрешностью, связанной с физической особенностью наблюдаемых величин. Таким образом, на множестве выходных последовательностей одинаковой длины вводится отношение равенства с точностью до погрешности измерений данной физической системы. Два состояния считаются неотличимыми, если их выходные реакции совпадают с точностью до введенного отношения. На этом пути возникает два основных подхода в выборе этого отношения.

Первый подход заключается во введении метрики р на множестве выходных символов и положительного числа є — погрешности измерений. Тогда две выходные последовательности называем равными с точностью до погрешности, если соответствующие

Введение выходные символы у этих последовательностей находятся на расстоянии не более є.

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

Модель эксперимента с искажением информации на входе возникает, если рассмотреть реальную физическую систему, на которую мы не можем непосредственно воздействовать. Мы предполагаем, что подаваемая на автомат последовательность может исказиться не более чем в к позициях. Тогда для того, чтобы гарантированно отличить два состояния мало потребовать отличимости их самой последовательностью. Необходима их отличимость всеми последовательностями, получаемыми из исходной искажением не более чем в к позициях. Перейдем к формальным определениям.

Обозначим через N, No и R — множество натуральных, неотрицательных целых и действительных чисел соответственно. Пусть также [п, т] = {г Є N \п ^ і ^ га}. Запись к \ п обозначает, что к является делителем п. Обозначим через НОД(п, т), НОК(п, т) — наибольший общий делитель и наименьшее общее кратное чисел пит соответственно.

Пусть /(n), д(п) —две положительные вещественные функции от натурального аргумента. Через /(n) ~ д(п) будем обозначать асимптотическое равенство /(п) и д(п), т.е. lim Щ = 1. 6

Введение

Через f(n) < g(n) будем обозначать утверждение п-*оо д(п)

Рассмотрим конечное непустое множество Е, которое мы будем называть алфавитом, а его элементы символами. Словом длины I над назовем Z-элементную последовательность а(1)а(2)... а(1) символов из Е. Обозначим длину слова а через \а\. Определим конкатенацию а(3 двух слов а = а{\)... а(1) и /? = 6(1)... Ь(ш) как слово а(1)... a(l)b(l)... b(m). Легко видеть, что множество всех слов над образует полугруппу относительно операции конкатенации. Доопределим эту полугруппу до моноида, добавив пустое слово Л такое, что аЛ = Ла = а для всех слов а. Положим |Л| = 0. Обозначим через * множество всех слов (включая пустое) над Е. Пусть а = а(1)а(2)... а(1). Обозначим символом а]_т слово а(1)а(2)... а(га), где 1 ^ т ^ /. Положим а]о = Л. Пусть а Є *, тогда полагаем а^п = &а... с\, п Є N. Считаем, что а⁰ = Л.

Под конечным детерминированным автоматом Мили (в дальнейшем автоматом) будем понимать объект 21 = (A,Q,B,ip,^), где A, Q, В — конечные непустые множества, называемые, соответственно, входным алфавитом, алфавитом состояний и выходным алфавитом, а ср : Q х А —* Q иф : Q х А—+ В — функции переходов и выходов.

Автомат можно представлять себе как абстрактное вычислительное устройство (рис. 1) работающее в дискретном времени t = 1,2 — В каждый момент времени t устройство находится в состоянии q(t) Є Q, на его вход подается а(і) Є А, а на выходе появляется b(t) Є В. Функционирование этого устройства задается следующей системой соотношений:

Введение (1)...^(/+1)

Рис. 1.

9(*+l) = >feW,a(t)), b(t) = #z(*M*))-

Если зафиксировать начальное состояние автомата (1) = q, а на его вход подать последовательность a(l)a(2).. . a(/), то из системы 1 однозначно определяется соответствующая выходная последовательность 6(1)6(2).. .6(/) и последовательность состояний q(l)q(2)...g(Z + 1).

Введем следующие обозначения: ф(_д, а(1)... а(0) = 6(0, (, а(1)... а(/)) = 6(1)... 6(/), ф, а(1)... а(0) =

Положим также ^»(д, Л) = Л, (p{q,h) = q. Пусть Q' С Q и а Є А*, тогда обозначим через

Автоматом без выхода назовем объект 21 = (A, Q,

Для задания автомата часто будет использоваться графический язык диаграмм Мура. Диаграмма Мура для автомата 21 = (A,Q,B,

Введение

а) Ь)

Рис. 2. ного символа а Є А проводится ребро (рис. 2а) из q в q' = ip(q, а), помеченное парой (а, Ь), где Ъ = tp^q, а).

Если для некоторого состояния q функция ip(q, а) = Ъ для всех а Є А, то символ Ъ из пометок ребер выходящих из q перемещаем в q (рис. 2Ь).

Назовем состояния q\, 2 автомата 21 = (A,Q,B,(p,ifj) отличимыми, если существует входное слово а Є А* такое, что 0₁(^і,о;) Ф ф₂(02і^а)- Если такого слова не существует, то скажем, что состояния qi, q

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

Пусть S — некоторое непустое множество и на нем задана функция сложности I : S —> No- Определим сложность класса как L(S) = max/(s).

Например, возьмем в качестве S — множество /С_п всех авто-

Введение матов с не более чем п состояниями. Положим /(21) = max:/(21,ді, q₂), где /(21,gi,^) — минимальная длина отличающего слова для <7і,ф2 в автомате 2t = (A,Q,B,(p,ijj) и 0, если qi,Q2 неотличимы. Тогда, согласно теореме Мура об отличимости[9], L(JC_n) = п — 1.

СОДЕРЖАНИЕ РАБОТЫ