Конечный автомат, управляемый событиями
В вычислениях ( конечный автомат FSM) управляется событиями , если переход из одного состояния в другое инициируется событием или сообщением . Это контрастирует с происхождением термина «конечный автомат» из теории синтаксического анализа, где машина описывается как потребляющая символы или токены .
Часто эти машины реализуются как потоки или процессы, взаимодействующие друг с другом как часть более крупного приложения. Например, телекоммуникационный протокол в большинстве случаев реализуется как управляемый событиями конечный автомат.
Пример на C [ править ]
Этот код описывает конечный автомат для очень простой автомобильной радиосистемы. По сути, это бесконечный цикл, считывающий входящие события. Конечный автомат имеет только 2 состояния: режим радио или режим CD. Событием является либо смена режима с радио на компакт-диск туда и обратно, либо переход к следующему (следующий пресет для радио или следующий трек для компакт-диска).
/*************************************************** *****************/ #include <stdio.h> /************************ **********************************************/ typedef enum { ST_RADIO , ST_CD } СОСТОЯНИЯ ; typedef enum { EVT_MODE , EVT_NEXT } EVENTS ; СОБЫТИЯ readEventFromMessageQueue ( void ); /*************************************************** *******************/ int main ( void ) { /* Состояние по умолчанию — радио */ STATES state = ST_RADIO ; int номер станции = 0 ; int trackNumber = 0 ; /* Бесконечный цикл */ while ( 1 ) { /* Читаем следующее входящее событие. Обычно это функция блокировки. */ EVENTS event = readEventFromMessageQueue (); /* Переключаем состояние и событие, чтобы выполнить правильный переход. */ переключатель ( состояние ) { case ST_RADIO : переключатель ( событие ) { случае EVT_MODE : /* Изменение состояния */ состояние = ST_CD ; перерыв ; case EVT_NEXT : /* Увеличить номер станции */ StationNumber ++ ; перерыв ; } перерыв ; case ST_CD : switch ( event ) { case EVT_MODE : /* Изменение состояния */ state = ST_RADIO ; перерыв ; case EVT_NEXT : /* Переход к следующему треку */ trackNumber ++ ; перерыв ; } перерыв ; } } } Тот же пример в Гинре [ править ]
Ginr — это промышленный компилятор, создающий многоленточные автоматы с конечным состоянием на основе рациональных шаблонов, функций и отношений, выраженных в полукольцевых алгебраических терминах. В приведенном ниже примере показана двоичная рациональная функция, эквивалентная приведенному выше примеру, с дополнительным переходом (ноль, радио) для перевода системы в исходное состояние. Здесь входные символы nil, mode, next обозначают события, которые приводят в действие преобразователь с выходными эффекторами cd, nextTrack, radio, nextStation . Подобные выражения обычно гораздо проще выражать и поддерживать, чем явные списки переходов.
ГосударственнаяМашина = ( (ноль, радио) ( (режим, компакт-диск) (следующий, следующий трек)* (режим, радио) (следующая, следующая станция)* )* ( (режим, компакт-диск) (следующий, следующий трек)* )?);
Компиляция создает последовательный (однозначный) двоичный преобразователь, отображающий последовательности событий в последовательности эффекторов, которые активируют функции компакт-диска/радиоустройства.
StateMachine:prsseq;(СТАРТ) ноль [радио] 11 режим [ компакт-диск ] 22 режим [радио] 32 следующий [ следующий трек ] 23 режим [ компакт-диск ] 23 следующая [ следующая станция ] 3
Моделирование дискретных систем таким образом позволяет четко разделить синтаксис (приемлемый порядок событий) и семантику (реализация эффектора). Синтаксический порядок событий и их расширение в семантическую область выражаются в символической (полукольцевой) области, где ими можно манипулировать алгебраически, в то время как семантика выражается на процедурном языке программирования как простые эффекторные функции, свободные от синтаксических проблем. Рациональные выражения предоставляют краткую целостную карту протоколов, влияющих на управление системой. Скомпилированные автоматы подвергаются постобработке для получения эффективных контроллеров для развертывания во время выполнения.
См. также [ править ]
Внешние ссылки [ править ]
- Ginr (технический документ и руководство пользователя ginr)
- Рибоза (демонстрирует использование ginr для преобразования последовательных сред)
Дальнейшее чтение [ править ]
- Питман, Джон Б. (1977). Проектирование на основе микрокомпьютера . Нью-Йорк: McGraw-Hill, Inc. ISBN 0-07-049138-0 .
- Брукшир, Дж. Гленн (1989). Теория вычислений: формальные языки, автоматы и сложность . Редвуд-Сити, Калифорния: ISBN Benjamin/Cummings Publish Company, Inc. 0-8053-0143-7 .