Для систем логического управления и событийных систем выделение состояний является естественным, так как они в значительной мере определяются физическими состояниями объектов управления [1].
Для вычислительных алгоритмов выделение состояний не столь естественно, однако и для этого класса задач автоматный подход может быть применен [2].
Автоматный подход позволяет унифицировать процесс построения структурированных программ с визуализацией их состояний, что имеет важное значение особенно для целей обучения [3]. Это не удается обеспечить при традиционном процедурном подходе, так как в нем в качестве базовых используются понятия "условие" и "действие", а не "состояние", и поэтому процедура визуализации алгоритма является неформальной.
Программы, построенные на основе явного выделения состояний, назовем автоматными.
В работе показано, что в отличие от теоремы структурирования программ, изложенной в работе [4], схема произвольного итеративного алгоритма (программы), может быть реализована одним оператором do-while, телом которого является один оператор switch. При этом оператор switch изоморфно реализует граф переходов конечного автомата, формально построенного по исходной схеме. Предложен метод преобразования итеративных алгоритмов в автоматные. Показано, что результат, получаемый при использовании этого метода проще, чем при применении метода Ашкрофта-Манны [5].
С помощью предлагаемого метода в настоящей работе решаются две задачи: преобразование традиционных программ (обычно структурированных) в автоматные и преобразование неструктурированных схем алгоритмов в автоматные.
Сопоставление рассмотренных в настоящей работе традиционных схем алгоритмов и графов переходов показывает, что последние более компактны и понятней специфицируют алгоритм. Это связано с тем, что построение графа переходов сводится к исследованию всех путей между соседними пометками в традиционной схеме алгоритма и компактному их представлению в виде помеченных дуг и петель графа.
Преимущество автоматного подхода по сравнению с традиционным достигается за счет добавления к понятиям "входное и выходное воздействия" понятия "состояние", а по сравнению с методом Ашкрофта-Манны - за счет сокращения числа состояний.
Работа выполнена в Федеральном государственном унитарном предприятии "НПО "Аврора"" и на кафедре "Компьютерные технологии" Санкт-Петербургского государственного института точной механики и оптики (технического университета) при поддержке Российского фонда фундаментальных исследований по гранту №02-07-90114 "Разработка технологии автоматного программирования".