 |
Тема 6 Автоматное программирование и интерпретация цифровых автоматов
|
|
|
|
В работе [10, с. 168-177] рассматривается задача преобразования циклического алгоритма, представленного традиционной блок-схемой с условными и операторными вершинами, в диаграмму состояний или граф переходов конечного автомата (см. приложение). Задача решается для произвольного циклического алгоритма. Это основной психологический момент рассматриваемого вопроса, а именно: произвольный циклический алгоритм можно задать в виде графа переходов конечного автомата. Обратная задача – преобразование графа переходов в традиционную блок-схему рассматривается в [4, c. 39–42].
Основной особенностью программной реализации конечных автоматов является обязательное наличие цикла, объемлющего код собственно реализации автомата. В литературе этот принципиальный момент опускается, делая невозможным понимание практического использования автоматных программ.
В отличие от традиционных алгоритмов, включающих два вида компонент: условие и действие, конечный автомат включает дополнительно состояния. Не будем описывать известные положения теории автоматов, с которыми можно ознакомиться, например в [11, 9, 10]. Вместо этого станем рассматривать практические аспекты создания автоматных алгоритмов и программ, в том числе на простом примере.
Вначале представим в общем виде автоматный алгоритм, пример которого изображен на рис. 1.
Прежде всего, обратим внимание на рамку, имитирующую цикловую природу реализации автомата. В частности, вверху явно указан оператор “while(cycle)”, где “cycle” – признак продолжения цикла, который перед передачей управления оператору while должен быть установлен в ненулевое значение. Итак, автомат реализуется программной конструкцией на Си:
|
|
|
static char state = ‘A’;
int cycle = 1;
while (cycle)
{
тело_автомата;
}
где state и тело_автомата подлежат дальнейшему рассмотрению.
Для понимания автоматной программы следует ввести определения: состояние, локальное событие, переход, модификация, действие на переходе. Наиболее сложным для восприятия конечных автоматов является понятие “состояние”. Однако начнем с определения “локальное событие”.
Локальным событием в автоматной программе будем считать положительный результат (не нулевое значение) вычисления некоторого логического выражения. Если логических выражений в программе более одного, то каждому из них ставится в соответствие свое локальное событие. Логическим выражением считается произвольная одноименная конструкция языка программирования C, в том числе: булева формула, выражение с операторами сравнения (аргументами которых могут быть и целочисленные функции). Локальное событие будем обозначать символом Хij и отождествлять с буквой входного алфавита конечного автомата.
В общем случае, состояние чего – либо, например, воды (жидкость, твердое – лед, газообразное – пар), не требует пояснений. Отметим, что та же вода в жидком состоянии “ожидает” наступления “события” (повышения температуры выше 100 град. или понижения температуры ниже 0 град. ) для перехода в другое состояние. Если ни одно из этих двух событий не произошло, то вода остается в прежнем своем (жидком) состоянии.
Аналогично, состояние автоматной программы есть фрагмент (группа строк) этой программы, в котором ожидается локальное событие по результатам вычислений логических выражений, входящих в данный фрагмент программы. Если ни одно локальное событие в текущем проходе цикла не произошло, то программа остается в том же состоянии, то есть вычисляет тот же фрагмент и в следующем проходе цикла. Если локальное событие наступило, то к следующему проходу цикла программа переходит в новое состояние (к другому фрагменту), где должны ожидаться другие локальные события. Заметим, что в конкретном состоянии может ожидаться не одно, а несколько локальных событий, из которых наступает всегда только одно из них.
|
|
|
Другими словами: состояние автоматной программы – это зацикливание на одном и том же фрагменте программы до наступления локального события.
Автоматная программа имеет несколько состояний, для обозначения которых отводится специальная символьная переменная – “state”. Обязательно наличие начального состояния, обозначаемого, например, символом ‘A’.
Переход в автоматной программе есть переход от текущего состояния, например, ‘B’, в новое состояние, например, ‘C’, при наступлении локального события XBC, приписанного к состоянию ‘B’. При этом переменная состояния state = ‘B’ изменяется на state = ‘C’.
Каждый переход сопровождается действием на переходе. Это означает, что при наступлении локального события нужно не только изменить переменную state, но и выполнить некоторую последовательность операторов, в том числе функций, и эта последовательность должна подготовить функционирование автоматной программы в новом состоянии.
Автоматная программа в каждом проходе цикла “while(cycle)” должна изменять значения аргументов вычисляемых логических выражений. В обеспечение этого каждое состояние должно иметь операторы модификации указанных аргументов.
Теперь рассмотрим абстрактный пример автоматной программы. Внутри прямоугольника – цикла на рис. 1 показан граф переходов (диаграмма состояний) некоторого автомата. Прямоугольниками, обозначенными буквами A – D, указаны вершины графа, обозначающие его четыре (в данном примере) состояния.
Укажем, что перед вычислением логических выражений, определяющих локальные события, во фрагменте-состоянии, как правило, осуществляется однократная модификация одной или нескольких переменных, обеспечивающих продвижение по циклу. Например, если автомат реализует анализ массива (файла), то модификация означает переход к очередному элементу массива (к очередной записи файла). В начальном состоянии модификация не производится. Модификация на рис. 1 обозначена символом Z с индексом соответствующего состояния.
|
|
|
Состояния реализуются оператором switch(state) – case [12, 9]. Например, программа для автомата (рис. 1) имеет следующую конструкцию:
static char state = ‘A’;
int cycle = 1;
while(cycle)
{
switch(state)
{
case ‘A’:
состояние A пока_не_рассматриваем;
break;
case ‘B’:
состояние B пока_не_рассматриваем;
break;
case ‘C’:
состояние C пока_не_рассматриваем;
break;
case ‘D’:
состояние D пока_не_рассматриваем;
break;
}
}
Переходы между состояниями обозначены на рис. 1 стрелками. Переходы помечены дробью: локальное событие Х / действие на переходе Y. За обозначением локального события сокрыто соответствующее логическое выражение.
Отметим обязательное правило: анализируемые логические выражения (условия), прописанные в одном и том же состоянии, должны быть обязательно ортогональны, что означает невозможность появления одновременно двух и более локальных событий. Локальные события, или логические условия, на рис. 1 обозначены символом Х с двумя индексами, первый из которых обозначает текущее состояние, а второй – состояние, в которое должна перейти программа в следующем цикле при наступлении данного локального события.
Локальному событию взаимно однозначно соответствует переход из текущего состояния в другое состояние. Если ни одно из вычисляемых в данном состоянии локальное событие не наступило, то сохраняется текущее состояние, и этому соответствует логическое условие, отрицающее любое из локальных событий – условий переходов в другие состояния (смотри “петли” - дуги, исходящие и заходящие в одну и ту же вершину - у вершин B, C, D на рис. 1).
Итак, по локальному событию программа переходит в следующем цикле в новое или остается в старом состоянии. Однако, прежде, чем перейти в новое состояние, программа должна совершить некоторое действие на переходе, следующее за соответствующим локальным событием и предваряющее модификацию в соответствующем переходу новому (прежнему) состоянию (в следующем цикле). Таким действием может быть произвольный оператор языка С++, включая произвольную последовательность произвольных операторов (в том числе вызов подпрограмм, в частности реализующих и другие автоматы, но - это отдельная тема). На рис. 1 такие действия стоят после дробной наклонной черты и обозначаются символом Y с индексами обозначающими направление перехода.
|
|
|
Отдельно, через запятую, указаны операторы вида “cycle = 0”, что означает конец циклической обработки. При этом направление перехода всегда к начальной вершине, она же является и заключительной для обеспечения корректного повторного использования данной подпрограммы – автомата.
Отметим, что правильная программа – автомат должна содержать переходы из любой вершины в начальную с указанным оператором обнуления переменной cycle во избежание зацикливания в одном состоянии. (В рассмотренном примере в состоянии С возможно зацикливание).
При первом обращении к автоматной подпрограмме, она находится в начальном состоянии, в котором не ожидается ни одно локальное событие. При этом осуществляется безусловный переход в состояние ‘B’ и выполняется действие YAB на этом переходе.
После данных пояснений приведем частично программу, реализующую автомат (рис. 1):
static char state = ‘A’;
int cycle = 1;
while(cycle)
{
switch(state)
{
case ‘A’:
оператор YAB;
state = ‘B’;
break;
case ‘B’:
оператор ZB;
if(XBA)
{
оператор YBA;
cycle = 0;
state = ‘A’;
}
else if(XBC)
{
оператор YBC;
state = ‘C’;
}
else // if (! ( XBA || XBC ) == 1 )
{
оператор YBB;
// state = ‘B’;
}
break;
case ‘C’:
состояние C не_рассматриваем;
break;
case ‘D’:
состояние D не_рассматриваем;
break;
}
}
|
|
|
