Конечный автомат как дискретная динамическая система

Исследование банка кривых проводилось в предположении, что для представления специфических свойств кривых достаточно их приближения, заданного 30 точками (соответственно извлеченные последовательности состоят из 30 элементов).

Существенным является способ доопределения функции переходов δ автомата. Исследованы циклическое доопределение, доопределение в начальное состояние, генерация состояния псевдослучайным образом (из множества возможных состояний). В случае, когда K/- X — ≠ [K/- X -], гдеX- - мощность входного алфавита автомата, а k — число точек на кривой (по которой строятся законы функционирования автомата), доопределение требуется и для функции выходов λ. В данной работе доопределение функции переходов осуществляется всеми указанными способами, а значение мощности входного алфавита и количество точек выбраны таким образом, что K/- X — ≠ [K/- X -], поэтому доопределение функции λ не требуется. В таблицах 1, 2 приведено табличное задание автомата (приX- = 2), построенного по спирали Фибоначчи при циклическом доопределении функции переходов.

Таблица 1. Таблица переходов автомата, построенного по спирали Фибоначчи

δ S0 S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 X1 S1 S3 S5 S7 S9 S11 S13 S0 S2 S4 S6 S8 S10 S12 S14 X2 S2 S4 S6 S8 S10 S12 S14 S1 S3 S5 S7 S9 S11 S13 S0

Таблица 2. Таблица выходов автомата (имеющего два входных сигнала), построенного по спирали Фибоначчи

λ S0 S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 X1 Y5 y 3 y 6 y 6 y 3 y 1 y 1 y 3 y 8 y 10 Y12 y 14 y 16 y 18 y 18 X2 Y4 Y5 y 7 y 5 y 3 y 0 y 2 y 7 Y9 y 11 y 13 y 15 y 17 y 18 y 17

Построенные по спирали Фибоначчи три автомата (так же как и по любой из анализируемых геометрических кривых) имеют соответственно 15, 6 и 3 состояния. Проведенное выделение классов эквивалентных состояний показало, что у всех 150 автоматов, построенных по 50 геометрическим кривым количество классов эквивалентности совпадает с числом состояний автомата, т. е. автоматы уже являются минимальными по числу состояний. Данное свойство присутствует у всех 150 автоматов, построенных при всех использованных способах доопределения функции переходов автомата: при циклическом доопределении функции переходов, при доопределении в начальное состояние, при доопределении с использованием генератора случайных чисел (состояние выбирается случайным образом из множества возможных состояний). В качестве примера автомата, построенного при доопределении функции переходов в начальное состояние в таблице 3 приведен автомат, имеющий 5 входных сигналов (построенный по лемнискате Бернулли). Все три использованных способа доопределения функции переходов автомата дали одинаковые результаты (по числу состояний автомата после минимизации). В общем случае от способа доопределения существенно зависит число состояний у автомата после минимизации. В результате проведенного исследования определены классы эквивалентных по сложности кривых и стоящих за ними законов функционирования дискретных динамических систем. [4]

Таблица 3. Таблицы переходов и выходов автомата (имеющего 5 входных сигналов), построенного по лемнискате Бернулли

δ S0 S1 S2 S3 S4 S5 X1 S1 S0 S0 S0 S0 S0 X2 S2 S0 S0 S0 S0 S0 X3 S3 S0 S0 S0 S0 S0 X4 S4 S0 S0 S0 S0 S0 X5 S5 S0 S0 S0 S0 S0

λ S0 S1 S2 S3 S4 S5 X1 Y3 y 7 y 2 y 3 y 7 y 2 X2 Y5 y 6 Y1 y 5 y 6 y 1 X3 Y6 y 5 y 0 y 6 y 5 y 0 X4 Y7 y 4 y 1 y 7 y 4 y 1 X5 Y8 y 3 y 2 y 8 y 3 y 2

Проведенное исследование банка EFMR включило также построение и анализ спектров Ω для числовых последовательностей, извлеченных из 50 выбранных для исследования геометрических кривых. Спектр динамических параметров рекуррентного определения числовых последовательностей, предложенный и разработанный в работе, характеризует сложность после довательности с позиции взаиморасположения элементов в последовательности. Спектр Ω (ƺ) для последовательности x имеет 5 уровней: Ω (ƺ)= (Ω0 (ƺ), Ω1 (ƺ), Ω2 (ƺ), Ω3 (ƺ), Ω4 (ƺ)), на которых числовыми значениями представлены порядки рекуррентных форм, длины отрезков последовательности, определяемые отдельными рекуррентными формами и количества смен рекуррентных форм. По определению Ω0 (ƺ) = m0(x), где m0(x) — наименьший порядок рекуррентной формы, определяющей всю последовательность x. На уровне Ω1 (ƺ) спектра Ω (ƺ) расположено m0 чисел (m0 € N+), определяющих для рекуррентных форм порядков от 1 до m0 размеры наибольших определяемых начальных отрезков последовательности x. Уровень Ω2(ƺ) содержит m0 чисел, показывающих, сколько раз для рассматриваемого порядка рекуррентных форм потребовалось заменять рекуррентные формы при определении последовательности x. На уровне Ω3 (ƺ) каждое число смен рекуррентных форм, показанное на уровне Ω2 (ƺ), заменено длинами отрезков последовательности x, определяемых отдельными рекуррентными формами.

Характеристика разбиений P0, P1, P2, P3 множества из 50 анализируемых последовательностей длины 30, полученная в результате построения спектров и разбиений по показателям спектров, представлены в таблице 4. На рис. 3, в качестве примера, изображены кривые, эквивалентные на нулевом уровне Ω0 (ƺ) спектра Ω. В данном классе эквивалентности находится логарифмическая спираль (см. рис. 3.(3)), а также кривые, информация о которых представлена в таблице 4.

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

Характеристика P0 P1 P2 P3 Число подклассов в разбиении 9 44 46 47 Максимальная мощность подкласса 18 3 3 3 Минимальная мощность подкласса 1 1 1 1

Минимальный порядок рекуррентной формы, необходимый для определения последовательности, сопоставляемой кривой, в данном классе эквивалентности равен 3.

Рис. 3. Геометрические кривые, эквивалентные по показателям нулевого уровня Ω0 спектра Ω

Заключение

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

Списоск использованной литературы Епифанов А. С. Анализ фазовых картин дискретныхдинамических систем. — Саратов: Изд-во «Научная книга», 2008. — 156 с.

Епифанов А. С. Интерполяция фазовых картин дискретных детерминированных систем. — 2008. — № 5. — С. 128−132.

Твердохлебов В. А. Геометрические образы конечных детерминированных автоматов // Известия Сарат. ун-та (Новая серия), Саратов. — 2005. — Т.

5. Вып.

1. — C. 141−153.

Твердохлебов В. А. Геометрические образы поведения дискретных детерминированных систем. — 2006. — № 5. — С. 161−165.