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

САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н.Г. ЧЕРНЫШЕВСКОГО

На правах рукописи

Тяпаев Ливат Борисович

ГЕОМЕТРИЧЕСКИЕ ОБРАЗЫ ПОВЕДЕНИЯ

АВТОМАТОВ

01.01.09 - математическая кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

НАУЧНЫЕ РУКОВОДИТЕЛИ: —Член-корреспондент РАЕН, доктор технических наук,

профессор Сытник А.А. —Академик РАЕН, доктор технических наук, профессор Твердохлебов В.А.

Саратов-1999

ОГЛАВЛЕНИЕ

Введение 3

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

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

13

§ 1. Геометрическая модель поведения конечных автоматов 13 §2. Свойства множества К^ и+1| 23

§3. Геометрический образ поведения конечных детерминированных автоматов 34 §4. Описание геометрических образов поведения для некоторых классов математических автоматов 48 ГЛАВА II. НЕКОТОРЫЕ ЗАДАЧИ С АВТОМАТАМИ В ГЕОМЕТРИЧЕСКОЙ ИНТЕРПРЕТАЦИИ 82 §1. Задача построения геометрических образов поведения конечных детерминированных автоматов 82 §2. Задача построения конечных автоматов по их геометрическим образам 86 §3. Преобразования геометрических образов 91 §4. Распознавание конечных автоматов на основе геометрической модели поведения 103 §5. Алгоритмы распознавания 107 Заключение 124 Литература 126

ВВЕДЕНИЕ

При изучении отображений вида <p\X*-+Y*, где X*J* суть множества всех слов конечной длины над алфавитами X и 7, используются различные математические структуры. В их число входит, в частности, аппарат ограниченно детерминированных функций [15, 41], или, например, такое отображение может быть ассоциировано с поведением некоторого преобразователя информации, скажем, конечного детерминированного автомата.

При изучении вероятностных систем, решении задач вероятностными методами возникает проблема моделирования случайности некоторого случайного процесса. В теории вероятностных автоматов рассматривают конечнозначные случайные процессы с дискретным неотрицательным временем (/ = 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, У, д\ Л ,.у0), еб", а именно ограниченное подпространство двумерного евклидова пространства

Г = | х е[1,и + 1) & у е[1,ш + 1)|, где п = \Х\, т = |Г|.

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

деляется класс кривых, не задающих ни один конечный детерминированный автомат в пространстве Г (теорема 4.2). В теореме утверждается, что никакой инициальный автомат не задается: 1) прямыми, выходящими из начала координат с коэффициентом наклона, отличным от единицы, и прямыми, смещенными параллельным переносом, а так же 2) прямыми, параллельными оси абсцисс X пространства Г. Также изучается поведение некоторых других классов математических автоматов, в том числе автономных автоматов (теорема 4.4) и машин Тьюринга (теоремы 4.5-4.7).

Вторая глава посвящена решению некоторых задач теории автоматов в геометрической интерпретации. В этой главе рассматриваются и решаются задачи: построения геометрического образа поведения конечного детерминированного автомата и .обратная к ней (§1 и §2), задачи преобразования геометрических образов (§3) и распознавания (.§§4,5). Третий параграф посвящен геометрическим преобразованиям геометрических образов некоторых классов автономных автоматов. В нем рассматриваются аффщные преобразования кривых, а именно: тщщттщт. перенос, поворот и сжатие (растяжедае), Установлено, например, что п^аллельньш перенос кривой, определяющей поведение автономного автомата в геометрии Г, трансформирует автомат в новый, изоморфный исходному, либо в автомат с большим числом состояний, где исходный является подавтоматом, либо в точную модель исходного автомата (теорема 3.1). Четвертый и пятый параграфы освящают некоторые методы распознавания конечных детерминированных автоматов на основе геометрической модели поведения, где фор-

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

Пользуясь случаем, автор выражает глубокую благодарность и признательность своим научным руководителям Действительному члену РАЕН, доктору технических наук, профессору Владимиру Александрович Твердохлебову и Члену-корреспонденту РАЕН, доктору технических наук, профессору Александру Александровичу Сытнику за постоянное внимание, помощь и поддержку в работе.

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

КДА — конечный детерминированный автомат; Т-машина— машина Тьюринга; X'— множество всех слов длины г в алфавите Х\ X* — множество всех слов конечной длины в алфавите

X;

|— мощность множества X; |/>| — длина слова р; е — пустое слово;

р1 — цепочка рр...р, в которой слово р повторяется I

раз;

N,1, Е — множества натуральных (1,2,...), целых и вещественных чисел;

*[1Н — подмножество промежутка [1,я + 1] числовой ве-

00 с

щественной оси Я, состоящее из всех чисел вида У]-—Ч~г, где

¿=1 \п + \)

с, е{о, 1,2,3,...,п], причем ф 0 и с2,с3,... могут обратиться в нуль только одновременно;

1х] — наибольшее целое число, не превосходящее х; Ы — наименьшее целое число, не меньшее х.

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

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

Будем рассматривать словарное отображение вида

(1.1),

где X*, У* — множества всех слов конечной длины над алфавитами X и У соответственно. С этим отображением можно ассоциировать поведение математического автомата, в частности, конечного детерминированного автомата (КДА).

Определение 1.1. КДА называется пятерка А - ), где

— произвольные конечные непустые множества, называемые соответственно множеством состояний, множеством входных и множеством выходных сигналов автомата А, а ¿>: £ х X -» ^ — функция переходов, Д:5х1->7— функция выходов автомата. Автомат будем называть инициальным, если среди его состояний выделено одно 50 €5, называемое начальным. В дальнейшем инициальный автомат

будем обозначать (л, .

Расширим функции 8,Х автомата А на множество последовательностей из X* согласно следующим соотношениям:

3 (х, е) = л', 8 рх) = 6 {б (.V, р), х),

Л е) = е, Л (я, рх) = Л (в, р) Л />), л).

Таким образом, значение функции 5 р) определяет состояние, в которое автомат переходит из состояния 5 под действием входной последовательности (слова) р. Значение функции л($,р) определяет ту последовательность выходных сигналов ц = упуп...у1к, которую выдает автомат, осуществляя переход из состояния * под действием последовательности р = хпхп...х)к.

Под поведением инициального КДА будем понимать множество пар слов вида К\ = {(р, | /> е X* & # = Л />)}, где 5 е 5. Поведение автомата в целом будем характеризовать множеством

КА = {(А д) | (э * е 5) р е Г & Я (,, р) = д}.

Геометрическое пространство Г для автомата А = где 50 еЯ — выделенное начальное состояние, будем строить следующим образом.

Алгоритм 1.1.

1. Перенумеруем все буквы в множестве X следующим образом. Сопоставим символам алфавита X некоторые номера «еК в и + 1-ричной системе счисления, то есть осуществим взаимно однозначное отображение / :К -> X, так что

(V« еК) (з ! (х еX)) : /(«) = *.

2. Определим координатную ось X (ось абсцисс) для пространства Г как ограниченный отрезок числовой оси К длины й = |Х\ +1, (1 е N с началом в нуле.

3. Каждому слову р = хпх12...х1к, (х, еК) посредством взаимно однозначного соответствия g: X* -> , где Ум — пространство конечномерных векторов, элементами которых являются натуральные числа, т.е. Уу >

со = (/'1, г2,..., ¡к). Тогда каждому слову реХ* будет однозначно соответствовать вектор со, координатами которого будут элементы натурального ряда N = {1,2Д..}. Пустому слову е сопоставим нуль-вектор.

4. Каждому такому вектору а = (г,, г2,..., 1к) взаимно однозначно сопоставим точку хеК на оси �