Применение сетей Петри к задачам моделирования
По Питерсону [2], простое представление системы основано на основополагающих понятиях: событиях и условиях. События – это действия, которые имеют место быть в системе. Возникновение событий управляет состоянием системы. Состояние системы, в свою очередь, может быть описано множеством условий. В данном случае условия – это предикаты. Таким образом они могут принимать значения «истина» или «ложь».
Так как события являются действиями, то они могут происходить. Чтобы оно произошло должно реализоваться предусловие. Возникновение событий может нарушать предусловия и может привести к выполнению других событий – постусловий.
Логичным примером построения простейшей системы с помощью сетей Петри может быть моделирование простого исполнителя, в данном случае – процессора компьютера. С достаточным уровнем абстракции он может быть описан в виде графа сети Петри на рис. 13.
Рис. 13. Моделирование простой вычислительной схемы
Следующим важным фактом является тот факт, что выполнение переходов в сети Петри мгновенно. То есть фактор времени здесь не учитывается. Но на деле это не так. Однако зачастую переходами моделируется выполнение каких-либо далеко не мгновенных операций. В этом случае выполнению операции может быть сопоставлен длительный переход. Для наглядности длительные переходы, в отличие от простых, часто обозначаются прямоугольником [5].
Рис. 14. Номенклатура длительного процесса
Длительный переход, как и простой, начинает выполнение с изъятия фишек из входных позиций и завершает, соответственно, помещая фишки в выходные. Основное отличие от простого перехода заключается в том, что между этими двумя моментами могут срабатывать другие переходы. Иначе говоря, срабатывание длительного перехода не атомарно.
С момента начала выполнения до момента завершения длительный переход считается активным, в противном случае – пассивным. Длительный переход не может сработать, если он активен, т.е. уже выполняется, даже если он разрешен по наличию фишек во входных позициях.
Рис. 13 может быть перерисован в следующем виде:
Рис. 15. Использование другой номенклатуры для процесса на рис. 13
Поскольку длительный переход не мгновенен и его срабатывание не атомарно, выполнение различных длительных переходов может перекрываться во времени, т.е. осуществляться параллельно. Длительный переход не мгновенен и его срабатывание не атомарно, выполнение различных длительных переходов может перекрываться во времени, т.е. осуществляться параллельно [5].
Моделирование конечных автоматов
Конечный автомат — абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
Существуют
различные варианты задания конечного
автомата. Например, конечный автомат
может быть задан с помощью пяти
параметров: 
,
где:
-
Q — конечное множество состояний автомата;
-
q0 — начальное состояние автомата (
); -
F — множество заключительных (или допускающих) состояний, таких что
; -
Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
-
δ — заданное отображение множества
во
множество 
подмножеств
Q:
(иногда δ
называют функцией
переходов автомата).
Так как целью данной работы не является построение конечных автоматов, то подробно мы их описывать не будем. Но скажем, что автоматы часто представляются в виде графов-переходов. А моделирование в рамках сети Петри осуществляется посредством представления алфавитов автомата (входного или выходного) позициями или переходами. Обычно входы представляются позициями. Приведём небольшой пример:
Рис. 16. Граф конечного автомата, вычисляющего дополнение до двух
Рис. 17. Эквивалентная сеть Петри
Но основным применением сетей Петри в данной конкретной работе будет возможность преобразования блок-схемы в сеть Петри. Таким образом, в виде сети Петри можно представить любой готовый алгоритм, который построен на вычислениях и ветвлениях. Рис. 18 иллюстрирует правила перевода:
Рис. 18. Правила перевода блок-схемы в сеть Петри