Пространство состояний сети Петри

Состояние сети Петри определяется ее маркировкой. Запуск перехода изменяет состояние сети Петри посредством изменения маркировки сети. Пространство состояний сети Петри, обладающей n позициями, есть множество всех маркировок, т. е. Nⁿ. Изменение в состоянии, вызванное запуском перехода, определяется функцией изменения d, которую мы назовем функцией следующего состояния. Когда эта функция применяется к маркировке m (состоянию) и переходу t_j, она образует новую маркировку (состояние), которая получается при запуске перехода t_j в маркировке m. Так как t_j может быть запущен только в том случае, когда он разрешен, то функция d(m, t_j) не определена, если t_j не разрешен в маркировке m. Если же t_j разрешен, то , где есть маркировка, полученная в результате удаления фишек из входов t_j и добавления фишек в выходы t_j.

Определение 6. Функция следующего состояния d: Nⁿ´T ® Nⁿ для сети Петри С = (Р, Т, I, O) с маркировкой m и переходом t_jÎT определена тогда и только тогда, когда m(p_i) ³ #(p_i, I(t_j)) для всех p_i Î P. Если d(m, t_j) определена, то , где для всех p_iÎP.

Пусть дана сеть Петри С = (Р, Т, I, O) с начальной маркировкой m. Эта сеть может быть выполнена последовательными запусками переходов. Запуск разрешенного перехода t_j в начальной маркировке образует новую маркировку . В этой новой маркировке можно запустить любой другой разрешенный переход, например t_k, образующий новую маркировку . Этот процесс будет продолжаться до тех пор, пока в маркировке будет существовать хотя бы один разрешенный переход. Если же получена маркировка, в которой ни один переход не разрешен, то никакой переход не может быть запущен, функция следующего состояния не определена для всех переходов, и выполнение сети должно быть закончено.

При выполнении сети Петри получаются две последовательности: последовательность маркировок и последовательность переходов, которые были запущены . Эти две последовательности связаны следующим соотношением: для k = 0,1,2, ... . Имея последовательность переходов и m⁰, легко получить последовательность маркировок сети Петри, а имея последовательность маркировок, легко получить последовательность переходов, за исключением нескольких вырожденных случаев. Таким образом, обе эти последовательности представляют описание выполнения сети Петри.

Пусть некоторый переход в маркировке m разрешен и, следовательно, может быть запущен. Результат запуска перехода в маркировке m есть новая маркировка m'. Говорят, что m' является непосредственно достижимой из маркировки m, иными словами, состояние m' непосредственно получается из состояния m.

Определение 7. Для сети Петри С = (Р, Т, I, O) с маркировкой m маркировка m' называется непосредственно достижимой из m, если существует переход t_jÎT, такой, что d(m, t_j) = m'.

Можно распространить это понятие на определение множества достижимых маркировок данной маркированной сети Петри. Если m' непосредственно достижима из m, а m'' – из m', говорят, что m" достижима из m. Определим множество достижимости R(C, m) сети Петри С с маркировкой m как множество всех маркировок, достижимых из m. Маркировка m' принадлежит R(C, m), если существует какая-либо последовательность запусков переходов, изменяющих m на m'. Отношение «достижимости» является рефлексивным, транзитивным замыканием отношения «непосредственной достижимости».

Определение 8. Множество достижимости R(C, m) дли сети Петри С = = (Р, Т, I, O) с маркировкой m есть наименьшее множество маркировок, определенных следующим образом:

1. m Î R(C, m);

2. Если m' Î R(C, m) и m'' = d(m, t_j) для некоторого t_j Î T, то m'' Î R(C, m).

События и условия

Простое представление системы сетью Петри основано на двух основополагающих понятиях: событиях и условиях. События – это действия, имеющие место в системе. Возникновением событий управляет состояние системы. Состояние системы может быть описано множеством условий. Условие – есть предикат или логическое описание состояния системы. Условие может принимать либо значение «истина», либо значение «ложь».

Так как события являются действиями, то они могут происходить. Для того чтобы событие произошло, необходимо выполнение соответствующих условий. Эти условия называются предусловиями события. Возникновение события может вызвать нарушение ; предусловий и может привести к выполнению других условий, постусловий.

В качестве примера рассмотрим задачу моделирования простого автомата–продавца. Автомат–продавец находится в состоянии ожидания до тех пор, пока не появится заказ, который он выполняет и посылает на доставку. Условиями для такой системы являются: а) автомат–продавец ждет; б) заказ прибыл и ждет; в) автомат–продавец выполняет заказ; г) заказ выполнен. Событиями будут: 1. Заказ поступил. 2. Автомат–продавец начинает выполнение заказа. 3. Автомат–продавец заканчивает выполнение заказа. 4. Заказ посылается на доставку. Предусловия события 2 (автомат–продавец начинает выполнение заказа) очевидны: (а) автомат–продавец ждет; (б) заказ прибыл и ждет. Постусловие для события 2: (в) автомат–продавец выполняет заказ. Аналогично мы можем определить предусловия и постусловия для других событий и составить следующую таблицу событий и их пред– и постусловий:

Такое представление системы легко моделировать сетью Петри. В сети Петри условия моделируются позициями, события – переходами. При этом входы перехода являются предусловиями соответствующего события; выходы – постусловиями. Возникновение события равносильно запуску соответствующего перехода. Выполнение условия представляется фишкой в позиции, соответствующей этому условию. Запуск перехода удаляет разрешающие фишки, представляющие выполнение предусловий и образует новые фишки, которые представляют выполнение постусловий.

Сеть Петри на рис.6.6 иллюстрирует модель приведенного выше автомата–продавца.

Рис.5.6. Сеть Петри для простого автомата–продавца

Поиск по сайту: