На низком уровне вычислительные системы могут быть описаны автоматами. Автомат — это пятерка (Q, ∑, ∆, δ, Г), где
Q — конечное множество состояний {q1, q2,…, qk};
∑ — конечный входной алфавит;
∆ — конечный выходной алфавит;δ : Q х ∑ → Q — функция следующего состояния, отображающая текущее состояние и текущий вход в следующее состояние; Г : Q х ∑→∆ — функция выхода, отображающая текущее состояние и текущий вход в выходной символ.
Автоматы часто представляют в виде графов переходов, как, например, на рис. 3.9. В графе переходов состояния представляются кружками, являющимися вершинами. Дуга из состояния qi в qj помеченная a|b, означает, что, находясь в состоянии qi автомат при входе а перейдет в состояние qj выдавая при этом символ b. Формально следовало бы записать
δ(qi ,a)=qj и Г (qi ,a)=b
Входной алфавит определяет входы автомата из внешнего мира, а выходной алфавит — выходы автомата во внешний мир.
В качестве примера рассмотрим автомат, изображенный на рис. 3.9. Этот автомат преобразует двоичное число, представленное последовательностью бит, начиная с младшего, в дополнение до двух. В данном случае входной и выходной алфавит состоит из трех символов: 0, 1 и R. Автомат начинает работать в состоянии qt. Символ сброса (R) означает конец (или начало) числа и возвращает автомат в исходное состояние. Выход автомата для символа сброса является просто его повторением.
Аналогичный автомат показан на рис. 3.10. При тех же самых входах этот автомат вычисляет четность входного числа. Он начинает работу в состоянии q1. Выход копирует вход до тех пор, пока входным символом не окажется символ сброса. Выходом для символа сброса будет 0 в случае нечетного числа и 1 — в случае четного числа.
При представлении конечного автомата сетью Петри следует обратить внимание на связь между сетью Петри и внешним миром, которая ранее не учитывалась. Моделирование взаимодействия с внешним миром можно реализовать многими способами. В нашей задаче мы моделируем это взаимодействие с помощью специального множества позиций. Позициями будут представлены каждый входной и выходной символы. Мы допускаем, что из внешнего мира помещается фишка в позицию, соответствующую входному символу, а затем фишка, появившаяся в позиции, соответствующей выходному символу, удаляется оттуда. Эта последовательность действий будет повторяться необходимое число раз. Общая схема проиллюстрирована на рис. 3.11.
Заметим, что здесь не исключена возможность путаницы в понятиях, так как позиции, соответствующие входным и выходным символам, могут быть обоснованно названы входными и выходными Позициями сети. Однако их не следует путать с входными или вы-
ходными позициями переходов. Несмотря на возможную путаницу, эти термины наиболее естественны для обоих понятий.
В качестве альтернативного подхода к моделированию входов и выходов сети могут быть использованы переходы. Для определения следующего входного символа из внешнего мира следует выбирать входной переходи запускать его. Сеть Петри ответит (в конце концов) запуском соответствующего перехода из множества выходных переходов, связанного с соответствующим выходом. Затем из внешнего мира будет запущен новый входной переход и т. д. Этот подход проиллюстрирован на рис. 3.12. Нетрудно показать, что оба этих подхода эквивалентны, поэтому будем использовать первый из них, в котором входные и выходные символы моделируются позициями.
Задав представление позиций, соответствующих символам входа и выхода, мы можем завершить построение модели системы конечных состояний. Представим каждое состояние автомата позицией в сети Петри. Текущее состояние отмечается фишкой; все остальные позиции пусты. Теперь для определения переходов из состояния в состояние можно ввести переходы сети следующим образом. Для каждой пары (состояние и входной символ) мы определяем переход, входными позициями которого являются позиции, соответствующие состоянию и входному символу, а выходными позициями — позиции, соответствующие следующему состоянию и выходу.
Для конечного автомата (Q, ∑, ∆, δ, Г) мы определили сеть Петри (Р, Т, I, О) таким образом:
P = Q∑∆,
T = {tq,σ|q и σ ∑ },
I(tq,σ) ={q,σ},
O(tq,σ) = {δ(q,σ), Г(q,σ)}
Эта сеть Петри является моделью конечного автомата.
На рис. 3.13 изображена сеть Петри, соответствующая автомату с рис. 3.9. На рис. 3.14 - cеть Петри, соответствующая автомату с рис. 3.10.
При сравнении сетей Петри на рис. 3.13, 3.14 с эквивалентными автоматами на рис. 3.9, 3.10 возникают некоторые вопросы. Прежде всего: почему модель сети Петри предпочтительнее описания конечным автоматом? Описание автоматом более понятно, чем описание сетью Петри, в которой 6 переходов, 24 дуги и 7 или 8 позиций. Это верно. Однако мы показали, что сети Петри могут представлять любую систему, представимую автоматом, и это свидетельствует о больших возможностях сетей Петри.
Кроме того, следует отметить, что модель сети Петри имеет определенное преимущество при композиции автоматов. Например,
заметим, что выходной алфавит автомата с рис. 3.9 идентичен входному алфавиту автомата с рис. 3.10. Передавая выход автомата с рис. 3.9 на вход автомата с рис. 3.10, можно построить композицию автоматов, вычисляющую дополнение до двух и проверяю
щую четность. Такая композиция является автоматом с составными состояниями, компоненты которых — это состояния обоих подавтоматов. В сетях Петри такая композиция есть просто совмещение выходных позиций первой сети с входными позициями второй. На рис. 3.15 показана композиция автоматов, а на рис. 3.16 — составная сеть Петри.
Другое преимущество представления сети Петри связано с иными формами композиции. Например, параллельная композиция позволяет компонентам композиции автоматов работать одновременно. В этом случае вновь получаем автомат с составными состояниями, в то время как для сети Петри — это просто дублирование фишек во входах, соответствующих входным символам, и использование их во всех компонентах сети Петри. Наконец, на выходе мы просто выбираем соответствующие позиции выхода. Например, если мы хотим соединить параллельно две сети Петри (рис. 3.13 и 3.14), то в результате получим сеть Петри, подобную изображенной на рис. 3.17, которая вычисляет дополнение числа до двух и его четность. Если на входе появляется символ сброса, то выходом является четность.
∑
и σ 
