Конечный автомат, управляемый событиями

П ≟ НП

Эта теоретической информатикой, статья, связанная с незавершена . Вы можете помочь Википедии, расширив ее .

В вычислениях ( конечный автомат FSM) управляется событиями , если переход из одного состояния в другое инициируется событием или сообщением . Это контрастирует с происхождением термина «конечный автомат» из теории синтаксического анализа, где машина описывается как потребляющая символы или токены .

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

Пример на языке C

Этот код описывает конечный автомат для очень простой автомобильной радиосистемы. По сути, это бесконечный цикл, считывающий входящие события. Конечный автомат имеет только 2 состояния: режим радио или режим CD. Событием является либо смена режима с радио на компакт-диск туда и обратно, либо переход к следующему (следующий пресет для радио или следующий трек для компакт-диска).

/********************************************************************/
#include <stdio.h>

/********************************************************************/
typedef enum {
        ST_RADIO,
        ST_CD
} STATES;

typedef enum {
        EVT_MODE,
        EVT_NEXT
} EVENTS;

EVENTS readEventFromMessageQueue(void);

/********************************************************************/
int main(void)
{
  /* Default state is radio */  
  STATES state = ST_RADIO;
  int stationNumber = 0;
  int trackNumber = 0;

  /* Infinite loop */
  while (1)
  {
    /* Read the next incoming event. Usually this is a blocking function. */
    EVENTS event = readEventFromMessageQueue();

    /* Switch the state and the event to execute the right transition. */
    switch (state)
    {
      case ST_RADIO:
        switch (event)
        {
          case EVT_MODE:
            /* Change the state */
            state = ST_CD;
            break;
          case EVT_NEXT:
            /* Increase the station number */
            stationNumber++;
            break;
        }
        break;

      case ST_CD:
        switch (event)
        {
          case EVT_MODE:
            /* Change the state */
            state = ST_RADIO;
            break;
          case EVT_NEXT:
            /* Go to the next track */
            trackNumber++;
            break;
        }
        break;
    }
  }
}

Тот же пример в Гинре

Ginr — это промышленный компилятор, создающий многоленточные автоматы с конечным состоянием на основе рациональных шаблонов, функций и отношений, выраженных в полукольцевых алгебраических терминах. В приведенном ниже примере показана двоичная рациональная функция, эквивалентная приведенному выше примеру, с дополнительным переходом (ноль, радио) для перевода системы в исходное состояние. Здесь входные символы nil, mode, next обозначают события, которые приводят в действие преобразователь с выходными эффекторами cd, nextTrack, radio, nextStation . Подобные выражения обычно гораздо проще выражать и поддерживать, чем явные списки переходов.

StateMachine = (
  (nil, radio)
  (
    (mode, cd) (next, nextTrack)*
    (mode, radio) (next, nextStation)*
  )*
  (
    (mode, cd) (next, nextTrack)*
  )?
);

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

StateMachine:prsseq;

(START)  nil [ radio ]          1
1        mode [ cd ]            2
2        mode [ radio ]         3
2        next [ nextTrack ]     2
3        mode [ cd ]            2
3        next [ nextStation ]   3

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

См. также

Внешние ссылки

Ginr (технический документ и руководство пользователя ginr)
Рибоза (демонстрирует использование ginr для преобразования последовательных сред)

Дальнейшее чтение

Питман, Джон Б. (1977). Проектирование на основе микрокомпьютера . Нью-Йорк: McGraw-Hill, Inc. ISBN 0-07-049138-0 .
Брукшир, Дж. Гленн (1989). Теория вычислений: формальные языки, автоматы и сложность . Редвуд-Сити, Калифорния: ISBN Benjamin/Cummings Publish Company, Inc. 0-8053-0143-7 .