Назовем основные положения данной парадигмы:
· алгоритмы реализуются в виде конечного автомата, причем понятие «состояние» является ключевым;
· в качестве спецификации программного продукта используются графы переходов;
· автоматная программа строится по графу переходов формально и изоморфно, поэтому
· отладка, тестирование, сопровождение и изменение программы производится по графам переходов;
· при необходимости автомат может быть разложен на систему взаимосвязанных автоматов, взаимодействующих между собой по принципу вызываемости или вложенности;
· каждый автомат реализуется конструкцией SWITCH языка Си (в Паскале – CASE) или любой аналогичной, которая является телом цикла с постусловием.
А. А. Шалыто предложил метод построения по граф-схеме алгоритма графа переходов, а затем и автоматной программы [20]. Данный метод основан на способе преобразования граф-схем в графы переходов, представленном в [2].
Приведем пример построения автоматной программы по алгоритму Евклида для нахождения наибольшего общего делителя. Граф-схема алгоритма показана на рис. 9.а.
 |
 |
Рис. 9: а – граф-схема алгоритма Евклида;
б – граф переходов автомата Мили
В заданную схему в зависимости от выбранного для ее замены типа автомата (Мура или Мили) вводятся пометки, соответствующие номерам его состояний. При этом для автоматов обоих типов начальной и конечной вершинам схемы присваивается номер 0, что обеспечивает построение «замкнутого» графа переходов. При построении автомата Мура n-й группе соединенных последовательно операторных вершин (она может состоять также и из одной вершины) присваивается номер n. При построении автомата Мили соответствующий номер присваивается точке, следующей за последней из последовательно соединенных операторных вершин группы, причем указанные точки для различных групп могут совпадать. Это приводит к тому, что автомат Мили имеет число состояний, не превышающее их число в эквивалентном автомате Мура.
Loading ...