Аппаратные и программные средства встраиваемых систем
жүктеу/скачать 3,23 Mb. Pdf көрінісі
|
| Состояние/условие
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 • Автоматы распознают входные слова, то есть отвечают на вопрос, принадлежит ли поданное на вход слово данному множеству (автоматы- распознаватели). • Автоматы преобразуют входные слова в выходные, то есть реализуют автоматные отображения (автоматы-преобразователи). Автоматы-распознаватели принципиально ничем не отличаются от автоматов-преобразователей, то есть допустимо один аспект свести к другому. Но при сведении, понятия и проблемы, важные при первом аспекте, оказываются либо несущественными, либо сильно видоизмененными во втором. Конечные автоматы широко используются на практике, например в синтаксических анализаторах, а также в других случаях, когда количество состояний объекта и переходов между ними сравнительно невелико. жүктеу/скачать 3,23 Mb. Достарыңызбен бөлісу:
|