ПОСЛЕДОВАТЕЛЬНО-СОБЫТИЙНЫЕ АВТОМАТЫ

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

Содержание

1. Введение

Конечные автоматы Мура и Мили предложено использовать в программах общего назначения (не только для логического управления) сравнительно давно [1]. При этом наиболее разработанным вопросом применения конечных автоматов является синтаксический анализ в различного рода трансляторах алгоритмических языков [2]. В настоящее время интерес к использованию конечных автоматов в программировании возобновляется, например, в области логического управления [3] и в объектно-ориентированном программировании [4].

В известных применениях процесс вычисления входной информации автоматов вынесен за пределы соответствующей, реализующей автомат, подпрограммы, например [3]. Поэтому такие автоматы можно реализовать не только с помощью программы, но и на элементах параллельной логики по одному и тому же классическому заданию. Такие программно реализуемые автоматы будем называть автоматами с независимыми событиями (АНС).

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

2. Последовательное вычисление событий

Говоря о программной реализации автоматов будем иногда ссылаться на языковые особенности, подразумевая наиболее распространенный универсальный язык программирования С++ [6].

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

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

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

(a | b & с) – выражение с булевыми переменными (примитивная булева формула;

(А >= 0.15 & B < А) – использование сравнения и логического И;

(exp(X) != sin(Y)) – сравнение вещественных функций;

(n--) – не нулевое значение целого числа с декрементом;

(a & func1(A,B)) – логическое И булевой переменной и ненулевого значения целочисленной функции с двумя параметрами;

(Тxt & len(Txt)) – наличие объекта текстового класса ненулевой длины.

Логическое выражение будем обозначать Xk = (…), где k – порядковый номер выражения. Другим обозначением логического выражения будем использовать конструкцию вида Xa_n, Xb_n и так далее, где a (b) – обозначения состояний, n – порядковый номер дуги, исходящей из вершины a (b).

Событием Ti_n будем называть выражение вида

Ti_n = ~Ti_n-1 & [Аi_n -> Xi_n],

Ti_1 = [Ai_1 -> Xi_1],

где i – обозначение состояния, Ai_n – обозначение подпрограммы, которую будем называть активизирующим действием, предназначенным для вычисления, или подготовки к вычислению, одного или нескольких аргументов логического выражения Xi_n; стрелка “->” означает: сначала выполнить действие слева от нее, а затем вычислить значение (ноль, не ноль) логического выражения, стоящего справа от стрелки; в целом значение выражения, заключенного в квадратные скобки, равно нулю при нулевом значении логического выражения Xi_n, и равно единице в противном случае [7] (напомним, что логическое выражение, не равное нулю, может принимать произвольное целочисленное, в том числе отрицательное, значение).

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

Дуги (петли) переходов ПСА помечаются обозначением событий или правой частью выражений (1). Как следует из (1), события ранжированы во времени их вычисления, начиная с простейшего события вида Ti_1 = [Ai_1 -> Xi_1].

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

Другим обозначением событий в БПСА будем считать двухиндексное, вида Tij, где i – номер вершины графа переходов (состояния или обозначающая его буква), из которого исходит дуга, помеченная данным событием, а j – номер вершины, в которую заходит эта дуга. Например, событие на переходе из вершины a в вершину b обозначается Tab.

С учетом бесповторности событий будет иметь место и одноиндексное обозначения вида Tj, где j – порядковый номер события, не превышающий общего числа событий в БПСА.

[ Содержание, 1, 2 | 3 - 5 | 6, 7 | 8, 9 | 10, Литература | >>> ]