Моделирование конечных автоматов

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

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

Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров:

,

где:

§ Q - конечное множество состояний автомата;

§ q0 - начальное состояние автомата ();

§ F - множество заключительных (или допускающих) состояний, таких что ;

§ Σ - допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;

§ δ - заданное отображение множества во множество подмножеств Q: (иногда δ называют функцией переходов автомата).

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

Рис. 16.

Граф конечного автомата, вычисляющего дополнение до двух

Рис. 17.

Эквивалентная сеть Петри

Но основным применением сетей Петри в данной конкретной работе будет возможность преобразования блок-схемы в сеть Петри. Таким образом, в виде сети Петри можно представить любой готовый алгоритм, который построен на вычислениях и ветвлениях. Рис. 18 иллюстрирует правила перевода:

Рис. 18.

Правила перевода блок-схемы в сеть Петри