Рекурсивно-управляемые автоматы

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

В работе предлагается новая математическая абстракция, названная «Рекурсивно-управляемый автомат», которая сочетает в себе простоту конечных автоматов, но лишена недостатков, присущих математическим аппаратам, использующим отдельную память, таким как машина Тьюринга или автоматы с магазинной памятью и показана возможность  построения  для любой заданной машины Тьюринга эквивалентного ей рекурсивно-управляемого автомата. 

Понятие рекурсивно-управляемый автомат тесно связано с понятием управляющий автомат. Поэтому прежде, чем перейти непосредственно к рассмотрению рекурсивно-управляемых автоматов важно вспомнить, что такое управляющий автомат. Управляющий автомат - это конечный автомат, выходные сигналы которого являются входными для другого (операционного) конечного автомата [1]. Основная идея, лежащая в основе рекурсивно-управляемых автоматов, заключается в построении бесконечно длинной цепочки взаимно управляющих конечных автоматов, способных оказывать управляющие воздействия на соседние автоматы в цепочке. При этом только первый автомат в цепочке способен получать управляющие сигналы из внешней среды и выдавать выходные сигналы во  внешнюю среду. Схематично работа рекурсивно-управляемого автомата может быть представлена следующим образом (рисунок 1):

Рисунок 1 - Схема работы рекурсивно-управляемого автомата 

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

Такт работы рекурсивно-управляемого автомата заканчивается, когда первый конечный автомат выдаст выходной сигнал левому соседу (рисунок 1), то есть во внешнюю среду. Очевидно, что число срабатываний конечных автоматов, составляющих рекурсивно-управляемый автомат, не является постоянной величиной. Более того, такт рекурсивно-управляемого автомата может вообще никогда не закончиться. Можно выделить два случая такого поведения:

1. Бесконечный цикл. Этот случай возникает, когда можно выделить подмножество конечных автоматов, входящих в рекурсивно-управляемый автомат, которые вызывают друг друга циклически, циклически бесконечное число раз, тем самым лишая возможности рекурсивно-управляемый автомат когда-либо выйти из данного цикла. Из этого следует необходимое условие завершения такта работы рекурсивно-управляемого автомата: совокупность всех подмножеств конечных автоматов, составляющих рекурсивно- управляемый автомат не должна содержать такое подмножество конечных автоматов, которые вызывают друг друга циклически бесконечное число раз.
2. Правостороннее движение. Этот случай возникает, когда передача управляющих сигналов идет преимущественно в правом направлении (рисунок 1), в то время как для корректного завершения такта рекурсивно- управляемого автомата общее количество сигналов в обоих направлениях должно совпасть. В противном случае рекурсивно-управляемый автомат будет задействовать в такте своей работы бесконечное число конечных автоматов, составляющих его, что приведет к невозможности завершения такта работы рекурсивно-управляемого автомата. Из этого следует достаточное условие завершения такта работы рекурсивно-управляемого автомата: общее количество управляющих сигналов конечных автоматов, составляющих рекурсивно-управляемый автомат, включая сигналы внешней среды, в обоих направлениях должно совпадать.

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

Рассмотрим возможный способ задания рекурсивно-управляемого автомата. Как было сказано ранее, рекурсивный автомат представляет собой множество одинаковых конечных детерминированных автоматов, у которых совпадают входной и выходной алфавиты. Благодаря тому, что все автоматы одинаковы, они могут быть заданы одним конечным автоматом [2]. Кроме того для такого конечного автомата должно быть определено направление выдачи выходного сигнала (левому или правому соседу) [3]. В зависимости от типа автомата (Мили или Мура) направление выходного сигнала определяет предикат от состояния автомата (для автомата Мура) или предикат от состояния и входного сигнала (для автомата Мили). Истинное значение предиката указывает на правостороннюю передачу выходного сигнала, а ложное значение - на левостороннюю соответственно. Начальное состояние рекурсивно-управляемого автомата, представляет собой бесконечное нумерованное мультимножество состояний каждого конечного автомата, составляющего рекурсивно-управляемый автомат, которое удобней всего задать функцией, возвращающей начальное состояние каждого конечного автомата от его номера.

С учетом вышесказанного формально рекурсивно-управляемый автомат Мура может быть представлен следующим кортежем(S, A, F,Y, P, N) , где

• S - конечное непустое множество состояний конечного автомата, составляющих рекурсивно-управляемый автомат.
• A - конечное непустое множество входных и выходных символов
• F(si, aj) - функция перехода, конечного автомата, составляющая рекурсивно-управляемый автомат, возвращающая следующее состояние конечного автомата в зависимости от текущего   состояния

Первые четыре элемента кортежа не вызывают вопросов, так как они задают обычный конечный детерминированный автомат Мура, у которого входной и выходной алфавиты совпадают. Пятый элемент картежа  - предикат P(si) похож на функцию выходов Y(si). В то время как данная функция фактически связывает с каждым состоянием конечного автомата выходной символ, предикат P(si) определяет направление выдачи этого выходного символа. Графически конечный автомат рекурсивно- управляемого автомата Мура задается графом схожим с графом обычного конечного автомата Мура, с тем дополнением, что каждое состояние помечается не только присущим ему выходным сигналом, но и направлением этого сигнала (0 и 1 - соответственно значения предиката P(si)).

На    рисунке  2  представлен  пример  конечного  автомата   рекурсивно- управляемого автомата, который моделирует работу счетчика. Вместе с функцией начального состояния N(k) представленный граф задает соответствующий рекурсивно-управляемый автомат.

При входом сигнале a1 счетчик инкрементирует свое значение, а при входом сигнале a2 обнуляет его. Значение счетчика равно числу на единицу меньшему, чем номер первого конечного автомата, составляющего рекурсивно-управляемый автомат, находящегося в состоянии s1, а не s2. То есть начальное значение счетчика равное, к примеру, пяти может быть задано следующей  функцией

Рисунок 2 - Пример конечного автомата рекурсивно-управляемого автомата 

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

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

Любая машина Тьюринга включает два основных компонента: бесконечную ленту и управляющее устройство (головка чтения-записи) [4]. Управляющее устройство представляет собой конечный автомат, поэтому проблем с его реализацией с помощью рекурсивно-управляемых  автоматов не возникает. Бесконечная лента состоит из ячеек, каждая из которых может хранить один символ конечного алфавита [5]. Таким образом, каждая ячейка может быть представлена конечным автоматом, число возможных состояний которого определяется числом символов данного конечного алфавита [6]. Текущее состояние такого автомата будет определять символ, который записан в ячейку в данный момент, а также факт наличия головки чтения- записи над данной ячейкой [7]. Начальное состояние рекурсивно- управляемого автомата определяет символы, записанные на ленте, а также начальное состояние управляющего устройства и положение головки чтения- записи. На вход рекурсивно-управляемый автомат принимает сигнал start, а по завершению работы выдает сигнал stop. Конечное состояние рекурсивно- управляемого автомата определяет результат работы машины Тьюринга. Таким образом, произвольная программа машины Тьюринга отрабатывает за один такт рекурсивно-управляемого автомата. С учетом сказанного, схематично машина Тьюринга может быть представлена следующим рекурсивно-управляемым автоматом (рисунок 3):

Рисунок 3 - Cхема рекурсивно-управляемого автомата, реализующего машину Тьюринга 

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

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

Модифицированная  схема    рекурсивно-управляемого  автомата  будет иметь следующий вид (рисунок 4): 

Рисунок 4 - Модифицированная схема рекурсивно-управляемого автомата, реализующего машину Тьюринга 

Серым цветом (рисунок 4) выделены части,  фактически неиспользуемые, но необходимые для сохранения регулярности структуры конечных автоматов, составляющих рекурсивно-управляемый автомат.

Опишем процесс работы данного рекурсивно-управляемого автомата. Для этого рассмотрим конечные автоматы, реализующие управляющее устройство и двойную ячейку. В самом начале работы конечный автомат, реализующий управляющее устройство принимает на вход сигнал start, в результате он вправо выдает сигнал get, который поступает на вход двойной ячейки. Двойная ячейка, принимая сигнал get, проверяет не находится ли головка чтения-записи над ней (одной из двух ее ячеек) и если это не так передает его далее вправо. В противном случае двойная ячейка передает в левом направлении сигнал ai, который является символом, записанным в той ячейке, над которой находится головка чтения-записи. Двойная ячейка, принимая сигнал ai, передает его в левом направлении. Управляющее устройство, принимая сигнал ai, переходит в новое состояние в соответствии с таблицей переходов машины Тьюринга и выдает влево сигнал stop, если состояние является терминальным или же вправо сигнал akX, который указывает, какой новый символ нужно записать в ячейку и каким образом переместить головку чтения-записи. При этом X может принимать одно из трех значений:

• L - переместить головку чтения-записи влево;
• R - переместить головку чтения-записи вправо;
• N - оставить головку чтения-записи не месте.

Двойная ячейка, принимая сигнал akX, проверяет, не находится ли головка чтения-записи над ней, и если это не так, передает его далее вправо. В противном случае переходит в новое состояние, соответствующее записи символа ak в нее, при этом если X≠N, то признак нахождения головки чтения записи над ней сбрасывается. В зависимости от значения X входного сигнала и того, над какой ячейкой (положительной или отрицательной) находится головка, возможны 5 вариантов:

1. В двойной ячейке головка чтения-записи находится над положительной ячейкой и X=L: влево будет выдан сигнал setP.
2. В двойной ячейке головка чтения-записи находится над положительной ячейкой и X=R: вправо будет выдан сигнал setP.
3. В двойной ячейке головка чтения-записи находится над отрицательной ячейкой и X=L: вправо будет выдан сигнал setN.
4. В двойной ячейке головка чтения-записи находится над отрицательной ячейкой и X=R: влево будет выдан сигнал setN.
5. X=N: влево будет выдан сигнал ak, записанный в ячейку.

Двойная ячейка, принимая сигнал setP, устанавливает признак нахождения головки чтения-записи над положительной ячейкой и влево выдает сигнал ai, который является символом, записанным в этой положительной ячейке. При приеме сигнала setN двойная ячейка устанавливает признак нахождения головки чтения-записи  над отрицательной ячейкой и влево выдает сигнал ai, который  является символом, записанным в этой отрицательной ячейке. Управляющее устройство, принимая сигнал setP, выдает вправо сигнал setN, а при приеме сигнала setN - сигнал setP. Возможные сигналы для управляющего устройства и двойной ячейки, а также направления их приема и выдачи представлены на рисунке 5.

Рисунок 5 - Возможные сигналы для управляющего устройства и двойной ячейки 

Рассмотрим конечный автомат Мили, реализующий управляющее устройство общего вида и имеющий для каждого перехода направление выдачи управляющего сигнала, который фрагментарно представлен ниже (рисунок 6):

Рисунок 6 - Фрагмент типового автомата управляющего устройства

Представленный на рисунке 6 фрагмент автомата управляющего устройства имеет 2 обычных состояния Sm и Sh, а также одно терминальное St. Поведение автомата соответствует требуемому поведению автомата управляющего устройства, описанному выше, а входные и  выходные сигналы совпадают с рисунком 5.

Автомат управляющего устройства (рисунок 6) достаточно  прост, так как практически полностью совпадает с управляющим устройством соответствующей машины Тьюринга, не считая некоторых дополнений, необходимых для адекватного взаимодействия с цепочкой двойных ячеек. При этом число состояний управляющего устройства машины Тьюринга и управляющего устройства рекурсивно-управляемого автомата, описывающего данную машину, совпадают. Конечный автомат, описывающий работу двойной ячейки, имеет более сложную структуру по следующим причинам:

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

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

1. ap- состояние положительной ячейки, показывающее какой символ записан в нее;
2. an- состояние отрицательной ячейки, показывающее какой символ записан в нее;
3. Z - состояние головки, которое может принимать одно из трех значений:

• P - головка чтения-записи находится над положительной ячейкой;
• N - головка чтения-записи находится над отрицательной ячейкой;
• E - головка чтения-записи не находится ни над положительной,  ни над отрицательной ячейкой.

При этом каждое состояние детерминированного конечного автомата Мили, описывающее двойную ячейку, можно представить как apanZ, соответственно число таких состояний будет равно утроенному квадрату мощности множества, задающего алфавит машины Тьюринга:

Рисунок 7 - Фрагмент типового автомата двойной ячейки 

На рисунке 7 фрагментарно представлен конечный автомат Мили, реализующий двойную ячейку общего вида и имеющий для каждого перехода направление выдачи управляющего сигнала. Данный фрагмент показывает поведение двойной ячейки для всех возможных входных сигналов. Начальное состояние автомата задает символы, которые  записаны в ячейки (положительную и отрицательную), а также факт наличия или отсутствия головки чтения-записи над соответствующей ячейкой. Здесь важно отметить, что из всех двойных ячеек рекурсивно-управляемого автомата только одна может находиться в состоянии, указывающем факт наличия головки чтения-записи над ее ячейкой.

Используя типовые фрагменты конечных автоматов, представленных на рисунках 6 и 7, а также схему рекурсивно-управляемого автомата, реализующего машину Тьюринга (рисунок 4) можно построить рекурсивно- управляемый автомат для любой заданной машины Тьюринга. Это доказывает, что класс рекурсивно-управляемых автоматов является полным по Тьюрингу.

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

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

1. Мачалин, В. А. Стратегия параллельной обработки массивов данных в системе объективного контроля радиотехнического комплекса радиолокационного дозора и наведения / В.А. Мачалин, А.Н. Токарев, Д.А. Трокоз, Д.В. Пащенко, М.П. Синев // Радиотехника, 2010. -Вып. 8. -С. 51-55.
2. Трокоз, Д.А. Формализация процесса моделирования многопоточных сетей Петри // Вопросы радиоэлектроники. 2012. Т. 3. № 4. С. 86-97.
3. Jiang S., Kumar R. Supervisory Control of Nondeterministic Discrete Event Systems with Driven Events via Masked Prioritized Synchronization // IEEE Transactions on Automatic Control, 2002, vol. 47, no. 9, pp. 1438–
4. Avalle M., Risso F., Sisto R. Efficient Multistriding of Large Non- deterministic Finite State Automata for Deep Packet Inspection // IEEE International Conference on Connunications (ICC 2012), Ottawa, Canada, June 10- 15, 2012, – 1079-1084.
5. Tanenbaum A. S., Bos H. Modern Operating Systems (4th Edition), Prentice-Hall, 2014, 1136
6. Andrews R. Foundations of Multithreaded, Parallel, and Distributed Programming. Addison-Wesley, 1999, 664 p.
7. Trokoz A. Equivalnce of inhibitory and non-inhibitory safe petri nets / Trokoz D.A., Pashchenko D.V.// Innovative information technologies: Materials of the International scientific – practical conference. Part 2 : HSE, 2014, 736 p. ISBN: 2303-9728 PP. 550-556.
8. Nikolay Konnov Modeling EMA and MA Algorithms to Estimate the Bitrate of Data Streams in Packet Switched Networks / Alexander Domnin and Victor Mekhanov //Communications in Computer and Information Science, Volume 487,―Information Technologies and Mathematical Modelling‖, Springer, 2014, P. 91 – 100.