Решения некоторых задач для геометрических образов конечных автоматов



Скачать 45,65 Kb.
Дата20.10.2016
Размер45,65 Kb.
РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ ДЛЯ ГЕОМЕТРИЧЕСКИХ ОБРАЗОВ КОНЕЧНЫХ АВТОМАТОВ
Д.О. Матов
Саратовский государственный университет, Саратов, Россия
При задании поведения конечных детерминированных автоматов геометрическими образами естественно возникает ряд задач и вопросов, связанных с геометрическими преобразованиями образов. В данной статье формулируются методы решения некоторых задач, опираясь на ранее полученные теоретические результаты.
Пусть автомат ,. С инициальным автоматом связано автоматное отображение . Геометрическое пространство для автомата определяется по следующему алгоритму [1]:

  1. Сопоставим элементам множества натуральные числа от 1 до n, т.е. осуществим взаимно однозначное отображение .

  2. Определим координатную ось абсциссдля пространства как отрезок числовой оси .

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

  4. Каждому такому вектору взаимно однозначно сопоставим точку на оси абсцисс: .

Аналогично определяется нумерация элементов множества , ось ординат пространства и отображение .

Каждой паре в пространстве сопоставляется точка с координатами , где , ,



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

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



, ,

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

Легко показать, что отношение совместимости есть отношение эквивалентности на множестве геометрических образов.

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


Рассмотрим следующие задачи.

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

2. Для заданного геометрического образа автомата найти все образы, совместимые с ним.

3. Построить разбиение заданного класса образов на классы эквивалентности по совместимости.


Каждую из обозначенных задач можно сформулировать для случая, когда автоматы являются автономными.
Приведем необходимые для решения теоретические результаты.

Теорема 1 [3]. Пусть и – два инициальных автомата. Тогда, если такие, что верно

, где , (1)

то (1) верно , т.е. образы автоматов и совместимы.


Теорема 2 [3]. Если , то

, , где , причем

, , , .
Теорема 3. Пусть . Тогда размер класса эквивалентности по совместимости, в котором лежит , не превосходит .
Решение задачи 1.

Пусть заданы автоматы и с их геометрическими образами. Основываясь на теореме 1, можно установить факт совместимости двух образов, перебрав все входные слова длины не более и проверив для них соотношение (1). Учитывая, что вычисление функции занимает шагов, то временную сложность алгоритма можно оценить как .


Решение задачи 2.

Случай 1: автомат автономный. Тогда существует алгоритм, который находит все образы, совместимые с данным, за время, пропорциональное их количеству. Тогда, в соответствии с теоремой 3, его время работы есть , где .

Случай 2: автомат произвольный. Пока неизвестен алгоритм, решающий эту задачу принципиально быстрее, чем решение задачи 3.
Решение задачи 3.

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

Основываясь на этих идеях, можно реализовать алгоритм со сложностью .

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


СПИСОК ЛИТЕРАТУРЫ


  1. Тяпаев Л. Б. Решение некоторых задач для конечных автоматов на основе анализа их поведения // Известия Саратовского университета. Саратов, 2006. Т. 6. Сер. Математика. Механика. Информатика, вып. 2. С. 121-133.

  2. Тяпаев Л. Б., Матов Д. О. Базисы геометрических образов для динамических систем, определяемых некоторыми классами автоматов //Компьютерные науки и информационные технологии: Материалы междунар. науч. конф. – Саратов, 2009. С.201-204.

  3. Матов Д. О. Аффинные преобразования геометрических образов конечных автоматов // Проблемы теоретической кибернетики: Материалы междунар. науч. конф. – Нижний Новгород, 2011. С.303-306.


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница