Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






 

Состояние сети Петри определяется ее маркировкой. Пространство состояний сети Петри, обладающей п позициями, есть множество всех маркировок, т.е. Е". Изменение в состоянии, вызванное запуском перехода, определяется функцией перехода S или функцией следующего состояния. Когда эта функция применяется к маркировке М и переходу t.

(если он разрешен), то в соответствии с (2.7) получается новая маркировка М' = b\M, tj). Она, как уже говорилось, получается

изъятием, фишек из позиции pt таких, что ff Ф 0 (ц.(. > ff)} и

помещением фишек в позиции рк такие, что f-k^0. Процесс создания новых маркировок продолжается до тех пор, пока в сети Петри при данной маркировке существует хоть один разрешенный переход. Если же при некоторой маркировке М(о) ни один переход не разрешен, то такая маркировка называется тупиковой.

При выполнении сети Петри получается две последовательности:

1) последовательность маркировок

{ М (О), М (1), М (2) ,... };

3) последовательность запущенных переходов

{ tj0, tj1, tj2, … }.

Эти две последовательности связаны следующим соотношением:

М+ 1) = δ (M (θ), t). (2.8)

Если в результате запуска перехода при маркировке М образуется новая маркировка М', то говорят, что М' достижима из М.

Множество достижимости R(PN, M) сети Петри PN cмаркировкой М есть множество всех Мк, достижимьгх из М.

Маркировка М принадлежит R(PN, M), если существует какая-либо последовательность изменяющих М на М.

Множество достижимости R(PN, М) для сети РN = {&, Р, 7', F, M0} с маркировками М есть наименьшее множество маркировок, определенных следующим образом:

а) М' ε R(PN, M);

б) если М' ε R(PN, M) и М" = δ (M’, tj) для некоторого tj ε T, то M" ε R(PN, M).

Вернемся к примеру на рисунке 2.1. При начальной маркировке Мо - [2, 2, 0] могут сработать переходы t1 (в результате получаем М1’ = [2, 3, 0]) и t7 (получается маркировка M1” = [1, 0, 1]). Каждая из полученных маркировок порождает новые, в результате чего получается дерево маркировок, фрагмент которого показан на рисунке 2.2. Обратим внимание на то, что в дереве маркировок могут встречаться повторяющиеся маркировки. В этом случае дальнейшее построение дерева ведется только для одной из них.

Если выделить путь по дугам графа маркировок, начинающийся в вершине Мо и заканчивающийся в различных вершинах М', и выписать подряд все встречающиеся символы переходов, то полученное слово образует последовательность срабатываний сети, а их совокупность - свободный язык сети Петри - L(PN, M0).

Так, язык рассматриваемой сети включает слова:

{ λ, t1, t2, t1t1, t1t2, t2t1, t2t3, t2t4, t1t1t1, t1t1t2, t1t2t1, t1t2t3, t1t2t4, t2t1t1, t2t3t1, t2t4t1, t1t1t1t1, t1t1t1t2, t1t1t2t1, t1t1t2t3, t1t1t2t4, t1t2t1t1, … }

Здесь λ – пустой символ, соответствующий начальной маркировке М0.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.