Геометрические образы поведения автоматов

• Автор: Тяпаев, Ливат Борисович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Саратов
• Количество страниц: 129 с.

ОГЛАВЛЕНИЕ
Введение
Основные обозначения и сокращения
ГЛАВА I. ПОСТРОЕНИЕ И АНАЛИЗ ГЕОМЕТРИЧЕСКИХ ОБРАЗОВ ПОВЕДЕНИЯ МАТЕМАТИЧЕСКИХ АВТОМАТОВ

§ 1. Геометрическая модель поведения конечных автоматов 13 §2. Свойства множества я+1|
§3. Геометрический образ поведения конечных детерминированных автоматов
§4. Описание геометрических образов поведения для некоторых классов математических автоматов
ГЛАВА II. НЕКОТОРЫЕ ЗАДАЧИ С АВТОМАТАМИ В ГЕОМЕТРИЧЕСКОЙ ИНТЕРПРЕТАЦИИ
§1. Задача построения геометрических образов поведения конечных детерминированных автоматов
§2. Задача построения конечных автоматов по их геометрическим образам
§3. Преобразования геометрических образов
§4. Распознавание конечных автоматов на основе геометрической модели поведения
§5. Алгоритмы распознавания
Заключение
Литература

ВВЕДЕНИЕ
При изучении отображений вида Y*, где XY* суть множества всех слов конечной длины над алфавитами X и Y, используются различные математические структуры. В их число входит, в частности, аппарат ограниченно детерминированных функций [15, 41], или, например, такое отображение может быть ассоциировано с поведением некоторого преобразователя информации, скажем, конечного детерминированного автомата.
При изучении вероятностных систем, решении задач вероятностными методами возникает проблема моделирования случайности некоторого случайного процесса. В теории вероятностных автоматов рассматривают конечнозначные случайные процессы с дискретным неотрицательным временем (t = 0,1,2

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

Конечные автоматы, а, следовательно, индуцированные ими отображения могут рассматриваться как преобразователи, реализующие числовые функции. Так например, Рябининым A.B. предлагается для этих целей рассматривать автоматы, на вход которых подается случайная последовательность из нулей и единиц, в которой единицы появляются с заданной частотой р. Если различные разряды этой последовательности статистически независимы, то на выходе автомата возникает случайная последовательность из нулей и единиц, в которой единицы появляются с частотой f(p), где / — некоторая функция. Функцию / называют стохастической функцией автомата. Сформулированы необходимые и достаточные условия, при которых / является стохастической функцией сильно связного автомата [23]. Стохастические функции автоматов позволяют аппроксимировать произвольные непрерывные функции /:[0;1]-»[0;1] [15].
Изучение словарных отображений можно ассоциировать с изучением поведения некоторых преобразователей. Лисовик Л.П. предлагает применять конечные преобразователи для задания отображений и фрактальных множеств. Так, любая непрерывная функция /: R’" R" может быть задана посредством R'r‘n -преобразователя , где Ä" -преобразователь представляет собой устройство, имеющее т входных и п выходных лент. Последовательно считывая символы ОТ-КИ входных бесконечных слов в алфавите X, -преобразователь печатает (за бесконечное время) п -ку выходных бесконечных слов в алфавите Y. За один такт считывается по одному символу с каждой входной

После того, как в пространстве Г определен геометрический (точечный) образ автомата, возникает задача интерполирования точечного образа конечного автомата в этом пространстве.
Прежде чем перейти к этой задаче, коротко сформулируем задачу интерполирования. Простейшая задача интерполирования [16] заключается в следующем. На отрезке [<з, б] заданы п +1 точки х0, хи
/МО* f(xi) = yu Ахп) = У„-
Требуется построить функцию Fix) (интерполирующая функция), принадлежащую известному классу и принимающую в узлах интерполирования те же значения, что и f{x), то есть такую, что
Р(х0) = уй, F(x) = yx,
Геометрически это означает, что нужно найти кривую у = F{x) некоторого определенного типа, проходящую через заданную систему точек Ц, (/ = 0,1
Известно, что в такой постановке задача может иметь бесчисленное множество решений или совсем не иметь решений [18]. Так же известно, что эта задача становится однозначной, если вместо произвольной функции F(x) искать полином Рп(х) степени не выше п удовлетворяющий условию
Г„(Хо) = Уо> Ч*|) = >’,> р{хп) = Уп