Конечный автомат

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 13:25, 2 июня 2016.
TemplateDifinitionIcon.svg Определение «Определение - Конечный автомат»
Конечный автомат – одна из базовых моделей, используемых при проектировании программного и аппаратного обеспечения средств вычислительной техники.

Конечный автомат — это компьютерная программа, которая состоит из:

  • Элементов маркированного списка;
  • Событий, на которые реагирует программа;
  • Состояний, в которых программа пребывает между событиями;
  • Переходов между состояниями при реагировании на события;
  • Действий, выполняемых в процессе переходов;
  • Переменных, которые содержат значения, необходимые для выполнения действий между событиями.

Конечные автоматы обычно представляют в двух видах:

  • Ориентированного графа, где точки это определенные состояния, а стрелки — направления переходов.
  • Двумерной таблицей, столбцы — это события, а строки — состояния, а ячейки содержат действия и переходы.

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

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

Область применения

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

Пример реализации

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

 #include <stdio.h>
 int c;
  
 int
 main()
 {
     goto s1;
      
 s2:  c = getchar();
      
     switch(c)
         {
          case EOF:
             exit(0);
          default :
             putchar(c);
             goto s2;
         }
 s1:  c = getchar();
     switch (c)
         {
         case EOF:
             exit(0);
         case '1':
             putchar('0');
             goto s1;
         case '0':
             putchar('1');
             goto s2;
         }
      
 }
 #include <stdio.h> 
 
 int char_to_id (int c) {
     switch (c) {
         case '0': return 0;
         case '1': return 1;
         case EOF: return 2;
         default: return 2;
     }
 }
 
 typedef struct table_item_s {
     int state;
     int out_char; 
 
 } table_item_t;
 
 #define END_STATE 2
 table_item_t
 T[2][3] = {
     { {1, '1'}, {0, '0'} , {END_STATE, '\n'}},
     { {1, '0'}, {1, '1'} , {END_STATE, '\n'}}
 };
 
 
  int main() {
     int c, c_id;
     int state = 0;
     while(!feof(stdin)) {
         c = getchar();
         c_id  = char_to_id(c);
         putchar(T[state][c_id].out_char);
         state = T[state][c_id].state;
         if(state == END_STATE)
             return 0;
     }
 }