Аппаратные и программные

Состояние/условие 
a 
b 
c 
S1 
S3 
S2
S3 
S3 
S2 
В левой колонке показаны состояния, в шапке таблицы – условия 
перехода. В пересечении строки и столбца показано новое состояние, в которое 
должен перейти автомат их указанного состояния по данному условию [52]. 
Реализация конечного автомата в виде программы выглядит следующим 
образом: 
// Коды состояний 
#define S1 0 
#define S2 1 
#define S3 2 
// Глобальные переменные, через которые мы получаем условия 
// (например, из обработчика прерывания) 
extern int a; 
extern int b; 
extern int c; 
int main( void ) 
{ 
int state = S1; 
… 
while( 1 ) 
{ 
switch( state ) 
{ 
case S1: if( a ) state = S3; break; 
case S2: if( c ) state = S3; break; 
case S3: if( b ) state = S2; break; 
} 
} 
return 0; 
} 
Идея конечного автомата развилась из близкого понятия, введенного в 
1936 году Аланом Тьюрингом (см. Машина Тьюринга). К достоинствам 
конечного автомата можно отнести простоту реализации. К сожалению, далеко 
не все можно представить в рамках этой модели вычислений. Во многих 
случаях, количество состояний в модели становится настолько большим, что 
делает ее использование практически невозможным. 
Известно деление конечных автоматов на автомат Мура и автомат Мили. В 
автомате Мура выходные сигналы зависят только от текущего состояния 
автомата (действия совершаются в состояниях), в автомате Мили выходные 
сигналы зависят и от текущего состояния, и от входных сигналов автомата 
(действия совершаются при переходах между состояниями). 

---

267 
Рисунок 100. Диаграмма конечного автомата 
Рисунок 101. а) Конечный автомат Мура; б) Конечный автомат Мили 
Автоматная теория, являясь частью теории алгоритмов, позволяет 
трактовать конечные автоматы как алгоритмы с конечной памятью, многие 
свойства которых можно исследовать безотносительно от способа реализации 
автоматов (которые могут быть, например, как аппаратными, так и 
программными). Таким образом, допустимо констатировать о классе задач, 
решаемых автоматами, так: если и только если задача алгоритмически 
разрешима, возможно построить конечный автомат, решающий эту задачу. 
Перефразируя, можно сказать, что с помощью конечного автомата 
потенциально возможно решить любую алгоритмически разрешимую задачу.
Исходя из трактовки автоматов, как алгоритмов с конечной памятью, 
центральной проблемой становится изучение возможностей автоматов в 
терминах множеств слов, с которыми они работают. Допустимо выделить два 
основных аспекта работы автоматов:

---

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