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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Иш Щ = 1. п~*оо д[п).

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

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