Об отличимости состояний конечных автоматов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Пантелеев, Павел Анатольевич

• Пантелеев, Павел Анатольевич
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Пантелеев, Павел Анатольевич

Введение

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] была получена верхняя оценка длины условного установочного эксперимента. Нижнюю оценку для него, совпадающую с верхней, получил А.А. Карацуба[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 ^ т ^ /. Положим си]о = А. Пусть а € £*, тогда полагаем ап = р?а?.<%, пб N. Считаем, что а0 = А.

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

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

7(1).•<?(/ + !) а(1).а(1) Q b(l).b(l)

Рис. 1. q(t+l) = <p(q(t),a(t)), m b(t)=mt)Mt))

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

Введем следующие обозначения: ф(д, а( 1). аЩ) = НО, Ш а(1) • • • о(0) = К1) • • • К1), p(q, а(1). а(/)) = q(l + 1), <p(q, а(1). a(Q) = q( 1) .q(l+ 1).

Положим также ip(q,h) = Л, tp{q,k) = g. Пусть Q' С Q и a € А*, тогда обозначим через ip(Q',a) множество Mq,<x) \ qeQ'}.

Автоматом без выхода назовем объект 21 = (A, Q,<p), который отличается от обычного автомата тем, что у него нет выходного алфавита и функции выходов. Функции <p(q, а) и <p(q, а) определяются как у обычного автомата.

Для задания автомата часто будет использоваться графический язык диаграмм Мура. Диаграмма Мура для автомата 21 = (A,Q,B,<p,ip) это ориентированный граф вершинами которого являются состояния из Q. Для каждой вершины q £ Q и вход

Рис. 2. ного символа а £ А проводится ребро (рис. 2а) из q в q' = <£>(#, а), помеченное парой (а, Ъ), где Ъ = ip(q, а).

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

Назовем состояния q\, 52 автомата 01 = (A,Q,B,(p,i/>) отличимыми, если существует входное слово a G А* такое, что ipi(qi, а) ф (<72, а). Если такого слова не существует, то скажем, что состояния qi, <72 — неотличимы. Автомат приведенный, если все его состояния попарно отличимы. Будем говорить, что слово а склеивает состояния q\, 52, если ip{qi,a) = (p(q2,a).

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

Пусть S — некоторое непустое множество и на нем задана функция сложности I : S —>• No- Определим сложность класса как

L(S) = maxl(s).

Например, возьмем в качестве S — множество /Сп всех автоматов с не более чем п состояниями. Положим

2t)= max /(21,01,02), где /(2l,gi,02) — минимальная длина отличающего слова для 01,02 в автомате 2t = (A,Q, В,(р,ф) и 0, если 01,02 неотличимы. Тогда, согласно теореме Мура об отличимости[9], L(JCn) = п — 1.

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Пантелеев, Павел Анатольевич

Основные результаты диссертации опубликованы в работах [19]-[25].

Диссертация состоит из введения, трех глав и библиографии. Она изложена на 101 страницах, библиография содержит 25 наименований. Нумерация теорем и лемм в каждой главе своя.

Пользуясь случаем, автор хотел бы выразить признательность за помощь во время работы над диссертацией своему научному руководителю профессору Александру Сергеевичу Подколзину и заведующему кафедрой Математической теории интеллектуальных систем академику Валерию Борисовичу Кудрявцеву.

Глава 1

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

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

Лемма 1.1. Если 21 € R — рефлексивное и симметричное отношение на В, qo и qo' — два произвольных R-отличимых состояния автомата 21, то существует слово а, R-отличающее

I I ^ п(п— 1) их и такое, что |о;| ^ v 2 '.

Доказательство. Пусть а = а(1)а(2). а(1) — кратчайшее слово, -R-отличающее состояния qo и qo'. Определим две последовательности qo,qi,., qi-i и qd, qi,., q\-\ следующим образом: q{ — (p(q0, a(l)a(2). а(г)), g/ = (p(q0', a(l)a(2). а(г)), г = 1, Z — 1.

Легко видеть, что минимальная длина входного слова, Rотличающего состояния qi,q'i, есть I — г. Действительно, слово а(г + 1 )а(г + 2).а(1) .R-отличает состояния qi,q[ и, если бы существовало слово (3, \(3\ < I — г, также Л-отличающее эти состояния, то слово а(1)а(2). a(i)(3 Д-отличало бы состояния qo,q'o и имело бы длину меньшую I. Это противоречит выбору слова а. Очевидно, что все пары в последовательности {q0, qo}, {qi, q\),., {qi-i, qi-i} различны, поскольку они имеют различные минимальные длины 72-отличающих слов. Следовательно I не превосходит числа неупорядоченных пар из множества Q, т.е. I ^ nin~1) Лемма доказана.

Теорема 1.1. Имеет место в j п — 1, когда R - транзитивно п(п2 ^, когда R - иетранзитивно

Доказательство. Пусть 21 G и R — произвольное рефлексивное и симметричное отношение на В. Если R — транзитивно, то оно — отношение эквивалентности на В, разбивающее его на классы эквивалентности В\,В2,. ,Bk, k ^ 2. Рассмотрим автомат 21 = (A,Q, B,(p,ip), где Q — множество состояний 01, В = {Bi, В2,., Вк} и Tp{q, а) = В{, когда a) G Д. Очевидно, что состояния q, q' автомата 21 jR-отличимы словом а точно тогда, когда они отличимы этим словом в автомате 21. Тогда согласно теореме Мура[9] минимальная длина отличающего слова в автомате 21 не больше п — 1 и получаем неравенство Lr(JC^) ^ п — 1. Рассмотрим автомат 21 = ({0}, {q1, q2,., qn}, В, ip, яр) с заданным отношением эквивалентности R на множестве его выходных символов, и пусть не верно, что b\Rb2, где bi,b2 6 В. Диаграмма Мура этого автомата изображена на рис. 1.1. Из нее видно, что

Рис. 1.1. для состояний q1 и q2 минимальная длина ^-отличающего слова равна п — 1. Таким образом, мы доказали, что если R — транзи-тивно, то Lr{K,B) = п — 1.

Пусть теперь R — нетранзитивно. Установим, что Lr{K*) = В силу леммы 1.1 получаем LR{K%) ^

Докажем, что можно построить автомат 21 G /С^, у которого существуют два Д-отличимых состояния q\, qi такие, что минимальная длина Д-отличающего их слова равна . Тем самым покажем, что Lr{1C= .

Для этого рассмотрим автомат1 21 = ({0,1 },Q, В,(р,ф), где Q = {q°, q1,., <?п-1}, функция выходов мы определим позднее, а функция переходов определяется следующим образом: = modn; vta"-1^) = q°, ¥>(<?', o) = q\i Ф n- 1. Диаграмма Мура для этого автомата приведена на рис. 1.2.

Упорядочим всевозможные пары состояний автомата 21. Пусть Qrs = Wi qs+k~r mod "}, где n — 2k, в случае четного п, и п = 2к+1 в случае нечетного п, и fc = [|].

1Этот автомат впервые был рассмотрен в работе [4] для получения нижней оценки синхронизирующего слова о

• Если п = 2к, то порядок следующий:

Q°0 = {q°,qkh Q°i = {q\qk+1}, Ql-i = {qk~\ qn~1},

Ql = {q\qk~1}, Q\ = {q\qkh QLi = qk~2h

Q2o = {q°,qk~2}, Q\ = {q\qk~1}, Ql-i = {qn~\ qk~3},

Qt^iq^q1}, Q\~l = {q\q2}, Qkn~-\ = {q^1, q°}■

• Если n = 2k + 1, то порядок следующий:

Q°o = {q°,qk}, Q°i = {q\qk+1h • QU = {«Г1,**"1}, Ql = {q\qk~1}, Q\ = {q\qk}, QU = {q^1, qk~2},

Qo'1 = Q\~l = {q\q2}, Qkn-\ = {qn-\qQ}.

Рассмотрим таблицу 1.1: к п = 2к

Q ¥>№,0)

QI-г = QJ <38

Qkn-\ = {<in-\<?} fa0} QS"1

Qrn-i = {qn-\qk-r~l}\ 0 < г < к - 1 QS

QUr-i = {ik+r-\<f-l}\ 0 < г < п — к ^fc+r-l Qk+r

Qrs,s ^ п— 1,к + г — 1; n~\iQrs Qrs+1 п = 2к + 1

Q i)

Q°k = {q\qn-1} Qk+l

Qt i = {qn~\q°} fa0} Qo~'

Qn-i = {9n"1,9fc~r~1}; 0 < r < A; - 1 05

0<r<n — /г — 1 (y— 1

Ф + n-l£Qrs

Список литературы диссертационного исследования кандидат физико-математических наук Пантелеев, Павел Анатольевич, 2006 год

1. Aho A.V., Dahbura A.T., Lee D., and M. Umit Uyar

2. An Optimization Technique for Protocol Conformance Test Generation Based on UIO Sequences and Rural Chinese Postman Tours. // IEEE Transactions on Communications, 1991, 39(11), p. 1604-1615.

3. Babai L., Seress A. On the diameter of Cayley graphs of the symmetric group. // Journal of Combinatorial Theory Series A, 1988, v. 49 n. 1, p. 175-179.

4. Babai L., Seress A. On the diameter of permutation groups. / / European Journal of Combinatorics, 1992, v. 13 n. 4, p. 231-243.

5. Cerny J. Poznamka к homogenym eksperimentom s konechnymi automatami. // Math.-Fyz. Cas., 1964, v. 14, p. 208-215.

6. Hibbard Т.Н. Least upper bounds on minimal terminal state experiments for two classes of sequential machines. // J. Assoc. Сотр., 1961, №4, p. 601-612русский перевод см. "Кибернити-ческий сборник"(новая серия), 1966, вып. 2), с. 7-23].

7. Holzmann G.J. Design and validation of protocols: a tutorial. // Computer Networks and ISDN Systems, 1993, v. 25, p. 9811017.

8. Landau E. Uber die Maximalordnung der Permutationen gegebenes Grades. // Archiv der Math, und Phys., 1903, p. 92103.

9. Lee D. and Yannakakis M. Principles and Methods of Testing Finite State Machines A Survey. // Proceedings of The IEEE, 1996, v. 84, n. 8, p. 1090-1123.

10. Moore E.F. Gedanken-experiments on sequential machines. // Automata Studies, 1956, p. 129-153русский перевод см. "Автоматы" (сб. статей), 1956, ИЛ, с. 179-210].

11. Shah S. An inequality for the arithmetical function g(x). //J. Ind. Math. Soc. 3, 1938, p. 316-318.

12. Гилл А. Введение в теорию конечных автоматов. // Наука, 1966, 272 с.

13. Карацуба А.А. Решение одной задачи из теории конечных автоматов. // УМН, 1985, т.15, вып. 3, с. 157-159.

14. Кудрявцев В.Б., Подколзин А.С., Ушчумлич Ш.М.

15. Введение в теорию абстрактных автоматов. // Изд-во МГУ, 1985, 174 с.

16. Кудрявцев В.В., Алешин С.В., Подколзин А.С. Элементы теории автоматов. // Изд-во МГУ, 1985, 320 с.

17. Прахар К. Распределение простых чисел. // Изд-во "Мир", 1967, 513 с.

18. Соколовский М.Н. О диагностических экспериментах с автоматами. // Кибернетика, №6, 1971, с. 44-49.

19. Соколовский М.Н. Оценки длины диагностического слова конечного автомата. // Кибернетика, №2, 1976, с. 16-21.

20. Соколовский М.Н. Сложность порождения подстановок и эксперименты с автоматами. // Методы дискретного анализа в теории кодов и схем, вып. 29, 1976, с. 68-86.

21. Работы автора по теме диссертации

22. Пантелеев П.А. Об отличимости состояний автоматов. // Дискретная математика, 2003, т. 15, вып. 3, с. 76-90.

23. Пантелеев П.А. Об отличимости состояний решетчатых автоматов. // Интеллектуальные системы, 2005, т. 8, с. 529542.

24. Panteleev P. A. On distinguishability of states of automata. // Discrete Mathematics and Applications, 2003, vol. 13, num. 4, p. 355-370.

25. Пантелеев П.А. О некоторых обобщениях понятия отличимости состояний автомата. // Тезисы докладов XIII международной конференции "Проблемы теоретической кибернетики", Казань, 27-31 мая 2002, ч. 2, с. 141.

26. Пантелеев П.А. О модификации отличимости состояний автомата. // Тезисы докладов V международного конгресса по математическому моделированию, 2002, с. 203.

27. Пантелеев П.А. Обобщенные эксперименты с автоматами. // Тезисы докладов VIII международного семинара "Дискретная математика и ее приложения", 2004, с. 144.

28. Пантелеев П.А. Об отличимости автоматов при искажениях на входе. // Тезисы докладов XIV международной конференции "Проблемы теоретической кибернетики", Пенза, 23-28 мая 2005, с. 114.