Геометрические образы поведения автоматов тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Тяпаев, Ливат Борисович

• Тяпаев, Ливат Борисович
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Тяпаев, Ливат Борисович

Введение

Основные обозначения и сокращения

ГЛАВА I. ПОСТРОЕНИЕ И АНАЛИЗ ГЕОМЕТРИЧЕСКИХ ОБРАЗОВ ПОВЕДЕНИЯ МАТЕМАТИЧЕСКИХ АВТОМАТОВ

§ 1. Геометрическая модель поведения конечных автоматов

§2. Свойства множества К^ и+1|

§3. Геометрический образ поведения конечных детерминированных автоматов

§4. Описание геометрических образов поведения для некоторых классов математических автоматов

ГЛАВА II. НЕКОТОРЫЕ ЗАДАЧИ С АВТОМАТАМИ В ГЕОМЕТРИЧЕСКОЙ ИНТЕРПРЕТАЦИИ

§1. Задача построения геометрических образов поведения конечных детерминированных автоматов

§2. Задача построения конечных автоматов по их геометрическим образам

§3. Преобразования геометрических образов

§4. Распознавание конечных автоматов на основе геометрической модели поведения

§5. Алгоритмы распознавания 107 Заключение 124 Литература

Введение диссертации (часть автореферата) на тему «Геометрические образы поведения автоматов»

При изучении отображений вида

При изучении вероятностных систем, решении задач вероятностными методами возникает проблема моделирования случайности некоторого случайного процесса. В теории вероятностных автоматов рассматривают конечнозначные случайные процессы с дискретным неотрицательным временем (/ = 0,1,2,.), такие процессы называют последовательностями случайных кодов [8, 17]. Последовательности случайных кодов в конечном алфавите X можно отождествить со словарной функцией у/\Х* ->[0;1], где у/{е) = 1, У (/?) = X^ W> Р^Х*. хъХ

Необходимость рассмотрения приближенного моделирования последовательностей случайных кодов возникла и у исследователей свойств детерминированного автомата. Этим, например, можно объяснить появление результатов Строгалова A.C. об е-моделировании поведения конечных автоматов [26] и Муба-ракзянова Р.Г., где изучаются задачи конечного описания и приближения последовательностей случайных кодов, в том числе и с помощью конечных автоматов [17].

Конечные автоматы, а, следовательно, индуцированные ими отображения могут рассматриваться как преобразователи, реализующие числовые функции. Так например, Рябининым A.B. предлагается для этих целей рассматривать автоматы, на вход которых подается случайная последовательность ш нулей и единиц, в которой единицы появляются с заданной частотой р. Если различные разряды этой последовательности статистически независимы, то на выходе автомата возникает случайная последовательность из нулей и единиц, в которой единицы появляются с частотой f(p), где / — некоторая функция. Функцию / называют стохастической функцией автомата. Сформулированы необходимые и достаточные условия, при которых / является стохастической функцией сильно связного автомата [23]. Стохастические функции автоматов позволяют аппроксимировать произвольные непрерывные функции /:[0;1]-»[0;1] [15].

Изучение словарных отображений можно ассоциировать с изучением поведения некоторых преобразователей. Лисовик Л.П. предлагает применять конечные преобразователи для задания отображений и фрактальных множеств. Так, любая непрерывная функция f\ Rm R" может быть задана посредством -преобразователя , где -преобразователь представляет собой устройство, имеющее т входных и п выходных лент. Последовательно считывая символы m-ки входных бесконечных слов в алфавите х, R"m -преобразователь печатает (за бесконечное время) п-ку выходных бесконечных слов в алфавите Y. За один такт считывается по одному символу с каждой входной ленты и печатается конечное число символов на каждую выходную ленту [16].

Б.А. Трахтенброт и Я.М, Барздинь в своей монографии по теории автоматов [32] изучают автоматные операторы и графики конечно-автоматных операторов.

В теории восстановления поведения сложных систем изучаются словарные отображения с точки зрения поведения конечного автомата. Так, Сытником A.A. предложена числовая модель поведения автомата. Основные этапы построения этой модели и критерии принципиальной возможности восстановления поведения автомата степенными многочленами излагаются в работах [27,47].

Изучение словарных отображений, а вместе с ними поведения сложных систем и поведения автоматов в частности, находит свое применение в теории экспериментов с автоматами и построении тестов для решения задач распознавания. Исследования в этом направлении проводились в работах [3,4,5,6,7,9,11,15,18,20,22,24,25,28,29,30,31,32,39,40,44,46,48] и многих других.

Существенно новым, отличным от теории построения тестов в теории распознавания, является геометрический подход к диагностированию поведения математических автоматов. Цель подхода — построение геометрических образов поведения автоматов и построения диагностических процедур [22]. Твердохлебовым В.А. предлагается строить дискретную словарную геометрию Г0, в которой геометрическим образом автомата является реализуемое им автоматное отображение (для инициальных автоматов) или объединение автоматных отображений по всем возможным начальным состояниям (см. [22]).

В той же работе отмечается, что преобразование геометрии Г0 в целочисленную геометрию Г15 в которой геометрический образ автомата представляется множеством точек с целочисленными координатами, а затем изоморфное вложение геометрии Г, в евклидову геометрию Г, в которой геометрический образ поведения автомата доопределяется до множества точек с вещественными координатами, позволяет применять к построению, анализу, преобразованию геометрических образов геометрические идеи и методы, расширить класс математических автоматов включением в него автоматов с бесконечными (возможно континуальными) множествами состояний и сигналов, а также рассматривать функции переходов и выходов как непрерывные функции, расширить классификацию автоматов в результате использования в качестве классифицирующих свойств имеющихся в евклидовой геометрии классификации фигур. Так же отмечается, что при новом геометрическом подходе ожидается возникновение новых методов распознавания автоматов, базирующиеся на идеях и методах построения, анализа и преобразования геометрических фигур евклидовой геометрии.

Таким образом, привлечение в теорию автоматов и в теорию распознавания в частности средств шпрерывной математики обещает новые нетривиальные результаты. Исследования в этом направлении осуществлялось рядом отечественных и зарубежных авторов. Например, в работе [45] построены функции, вычисляющиеся с помощью конечных автоматов. Исследование геометрической модели стохастических автоматов проводились в [42]. Класс автоматов, функционирующих в непрерывном времени, рассматривался в [2].

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

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

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

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

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

Результаты работы докладывались и обсуждались на конференции "Проблемы технической кибернетики" (Ульяновск, 1996), конференции "Интеллектуальные системы и компьютерные науки" (Москва, 1996), международной конференции "Проблемы и перспективы прецизионной механики и управления в машиностроении" (Саратов, 1997), первой всероссийской научной конференции молодых ученых и аспирантов "Новые информационные технологии, разработка и аспекты применения" (Таганрог, 1998), на семинарах кафедры теоретических основ информатики и информационных технологий Саратовского государственного университета.

По результатам работы опубликовано 6 работ.

Диссертация содержит 129 страниц, состоит из введения, двух глав, заключения и списка литературы.

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

ЗАКЛЮЧЕНИЕ

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

А*л = реХ* & X («,/?) = д} (для конечных детерминированных инициальных автоматов), и каждой паре [ч?,™') етеорема 3.1 из первой главы). Изучены некоторые классы конечных автоматов и машин Тьюринга с точки зрения их поведения в построенном пространстве (теоремы 4.1-4.7). Поставлены и решены следующие задачи с автоматами в геометрической интерпретации: задача построения геометрического образа поведения конечного детерминированного автомата (для автомата Л = ), заданного семейством кривых построить кривую /, определяющую поведение автомата), задача построения автомата по его геометрическому образу (теорема 2.1 из второй главы), задачи преобразования геометрических образов: преобразование параллельного переноса (теорема 3.1 второй главы), преобразование сжатия (растяжения) (теорема 3.2 из второй главы), преобразование поворота (теорема 3.3 из второй главы); сформулирована задача распознавания конечного автомата в конечном семействе в терминах автоматных кривых и приведено несколько алгоритмов распознавания (алгоритмы 5.1-5.5).

Список литературы диссертационного исследования кандидат физико-математических наук Тяпаев, Ливат Борисович, 1999 год

1. Александров П.С., Колмогоров А.Н. Введение в теорию функций действительного переменного — ГТТИ — M.-J1. — 1938. —268 с.

2. Алексеев А.Е. Области линейной зависимости периода непрерывного автомата от параметров. // Методы и системы технической диагностики. — Вып. 18.— Саратов — Издательство Саратовского университета. — 1993. — С.9-11.

3. Барздинь Я.М. О расшифровке автоматов. // В кн. Проблемы кибернетики. М.: Наука. — 1969. — Вып. 21.—С. 103-114.

4. Богомолов A.M., Грунский И.С., Сперанский Д.В. Контроль и преобразования дискретных автоматов. — Киев. — 1975. — 176 с.

5. Богомолов A.M., Твердохлебов В.А. Диагностика сложных систем. — Киев. — 1974. — 128 с.

6. Богомолов A.M., Твердохлебов В.А. Целенаправленное поведение автоматов. — Киев. —1975. —124 с.

7. Брауэр В. Введение в теорию конечных автоматов. — М.: Радио связь. — 1987. — 392 с.

8. Бухараев Р.Г. Вероятностные автоматы. — 2-е изд. — Казань: Изд-во КГУ. — 1977. — 248 с.

9. Василевский М П. О распознавании неисправностей автоматов // Кибернетика. — 1973. — №4. — С.93-108.

10. Василевский М.П. О расшифровке автоматов // Кибернетика— 1974. —№2. — С. 19-23.

11. П.Гилл А. Введение в теорию конечных автоматов. — М.: Наука, —1966. —272 с.

12. Делоне Б.Н., Райков Д.А. Аналитическая геометрия —Том 1. — ОГИЗ — Гостехиздат — 1948. — 456 с.

13. Демидович Б.П., Марон И.А. Основы вычислительной математики. — М.: Государственное изд-во физ.-мат. Лит. — 1963,—660 с.

14. Корнейчук Н.П. Сплайны в теории приближения — М: Наука—1984—352 с.

15. Кудрявцев В.Б., Алешин С.В., Подколзин A.C. Введение в теорию автоматов. — М.: Наука. — 1985 — 320 с.

16. Лисовик Л.П. Применение конечных преобразователей для задания отображений и фрактальных множеств // ДАН — 1998 — Том 358 — N1 — С. 19-21.

17. Мубаракзянов Р.Г. Автомат, оставляющий инвариантным класс случайных последовательностей с конечным множеством состояний. // Изв. вузов. Математика. — 1985. — №7. — С. 21-25.

18. Мур Э.Ф. Умозрительные эксперименты с последовательно-стными машинами. // В кн. Автоматы. — М.: ИЛ. 1956. — С. 179-212.

19. Никулин В.В., Шафаревич И.Р. Геометрии и группы. — М.: Наука. — 1983 — 240 с.

20. Основы технической диагностики. Кн. 1., под ред. Пархоменко П.П. — М.: Энергия. — 1976. 464 с.

21. Рвачев В.А. 06 аналитическом описании некоторых геометрических объектов. — ДАН СССР — 1963. — том 153. — №4 — С. 765-767.

22. Резчиков А.Ф., Твердохлебов В.А. Управление и диагностирование в сложных системах. — Саратов. — Изд-во Саратовского университета. — 1997. — 130 с.

23. Рябинин A.B. Стохастические функции конечных автоматов. // Тезисы VI Всесоюзной конференции по математической кибернетике. — Саратов. —1983.

24. Соловьев H.A. Тесты. Теория. Построение. Применение. — Новосибирск. — Изд-во Наука. — 1978.— 189 с.

25. Спивак М.А. Некоторые свойства множества экспериментов автомата. //Кибернетика. — 1966., №6.— С. 1-7.

26. Строгалов A.C. Об s-моделировании конечных автоматов Мили. // Материалы Всесоюзного семинара по дискретной математике и ее приложениям. / Под ред. О.Б. Лупанова. / М.: Изд-во Московского ун.-та. — 1986. — С.42-56.

27. Сытник А.А, Посохина Н.И, Шульга Т.Э. Об одном подходе к решению задачи синтеза автоматов-перечислителей. // Теоретические проблемы информатики и ее приложений. — Вып. 2. — Саратов. — ГосУНЦ "Колледж". — 1998. — С. 103-116.

28. Твердохлебов В.А. Контроль и диагноз сложных систем методами теории бинарных отношений. — Саратов. — 1967,— 30 с.

29. Твердохлебов В.А. Аксиоматический подход к диагностированию систем в целом. // Методы и системы технической диагностики. — Саратов. — Изд-во Саратовского Университета. — 1980. — Вып.1. — С.40-51.

30. Твердохлебов В.А. Тестирование машин Тьюринга. // Методы и системы технической диагностики. — Саратов. — Издво Саратовского университета. — 1988. — Вып. 9. — С. 4146.

31. Твердохлебов В.А. Логические эксперименты с автоматами. — Саратов. — Изд-во Саратовского университета. — 1988. — 184 с.

32. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы (поведение и синтез). — М.: Наука. — 1970. — 400 с.

33. Тяпаев Л.Б. Построение и анализ геометрических образов конечно-детерминированных автоматов. // Теоретические проблемы информатики и ее приложений. — Вып. 1. — Саратов. — ГосУНЦ "Колледж". — 1997. — С. 146.-151.

34. Тяпаев Л.Б. Распознавание математических автоматов на основе геометрической модели поведения. — Саратов, гос. унт,— Саратов. — 1998. — Деп. в ВИНИТИ 24.04.98 №1327В98. — 46 с.

35. Тяпаев Л.Б. Описание геометрических образов некоторых классов математических автоматов// Теоретические проблемы информатики и ее приложений. — Вып. 2. — Саратов. — ГосУНЦ "Колледж". — 1998. — С. 139-148.

36. Тяпаев Л.Б. Анализ поведения информационных систем // Первая всероссийская научная конференция молодых ученых и аспирантов "Новые информационные технологии, разработка и аспекты применения". Тезисы докладов. — Таганрог — 1998. —С. 137-138.

37. Яблонский C.B. О построении тупиковых кратных экспериментов для автоматов. — М.: Тр. МИАН им. Стеклова, т. СХХХШ. — С. 263-272.

38. Яблонский C.B. Введение в дискретную математику. — М.: Наука, —1979, —384 с.

39. Bancilhon Т.A. Geometric Model for Stochastic Automata. // IEEE Transaction on Computers. — 1974. № 12., V. С -23. — p. 1290-1299.

40. Booth T.L. Sequential Machines and Automata Theory. — John Wiley & Sons, N.Y., London, Sydney, 1968. — 592 p.

41. Gill A. State Identification Experiments in Finite Automata // Inf. And control 4,1961, p. 132-154.

42. Derencourt D., Karhumaki J., Latteux M., Terlutte A. On Continuous Functions computed by Finite Automata. // Inf. Theor. Et. Appl. —1994. — 28., №3-4. — p. 387-403.

43. Starke P.H. Uber Experimente an Automaten, Zeitschriff f. Mathem. 13. — 1967. — p. 67-80.

44. Thristle J.G., Wonham W.M. Control of Infinite Behavior of Finite Automata. // SIAM Journal on Control and Optimization. — Philadelphia. — 1994. — 32. — №4. — p. 1075-1097.