Моделирование дискретных асинхронных процессов и сети Петри.( до 90 минут)

Сети Петри предназначены для моделирования дискретных асинхронных процессов. Их основные отличия от автоматной модели – возможность отображать параллелизм, асинхронность и иерархичность моделируемых объектов.

Сети Петри можно описать формально в виде

N=(P,T,F,H,m₀ )

Где P – конечное непустое множество позиций (состояний);

Т - конечное непустое множество переходов (событий);

F:P^хT®{0,1,2..} – функция входных инциденций

H:T^хP®{0,1,2..} - функция выходных инциденций

m₀ :P®{0,1,2..} – начальная маркировка (разметка) сети.

Сети Петри удобно представлять графически в виде двудольного ориентированного графа с двумя типами вершин, соответствующими

0001 0011 0010

а) S₁ S₂ б) S₁ S₂

1001

0101 1010

0110

S₃ S₄ S_{3 1100} S₄

0100 1000

00 01 000 001

в) S₁ S₂ г) S₁ S₂

101

011

S₃ S₄ S_{3 110} S₄

10? 100 010

Рис.27.1

позициям pÎP и переходам tÎT (рис.44) Позиции изображаются кружками. Внутри кружка могут находиться маркеры (фишки), изображаемые точками. Переходы изображаются черточками (барьерами).

Функции входных и выходных инциденций могут быть представлены матрицами. Для сети на рис. 27.1 имеем:

t₁ t₂ t₃ t₄ p₁ p ₂ p₃ p₄ p₅

p₁ 1 0 0 0 t₁ 0 0 1 2 0

p₂ 1 0 0 0 t₂ 1 0 0 0 1

F= p₃ 0 1 0 0 H= t₃ 1 1 0 0 0

p₄ 0 0 1 0 t₄ 0 0 0 1 0

p₅ 0 0 0 1

Если можность множества P равна n, то маркировка представляется n-мерным вектором, значения координат которого равны числу маркеров в соответствующих позициях.

Переход от одной маркировки к другой происходит в результате срабатывания переходов. Переход t может сработать при маркировке m, если является возбужденным, т.е. в каждой входной позиции перехода, t число маркеров не меньше веса (кратности) дуги, соединяющую эту позицию с переходом:

" pÎP:m¹(p) – F(p,t)³0

В результате срабатывания перехода t маркировка М заменяется маркировкой М¹

V_PÎP:M¹(P)= M(P) – F(p,t)+H(t,p).

Это означает, что в результате срабатывания из всех входных позиций перехода t удаляются F(p,t) маркеров, а в каждую входную позицию добавляется H(t,p) маркеров. В рассматриваемом случае маркировка M¹ непосредственно достижима из маркировки М, что обозначается М→ M¹ функционирование сети Петри – это последовательная система маркировок в результате срабатывания возбужденных переходов. Состояние сети Петри – в каждый момент времени определяется ее текущей маркировкой.

Два возбужденных не взаимодествующих перехода могут сработать независимо друг от друга, поэтому сеть Петри как модель отражает альтернативность поведения, паралельность и асинхронность.

Возможные варианты функционирования сети описываются графом достижимости. Вершинами графа достижимости являются маркировки, а

дуги представляют отношение непосредственной достижимости на множестве маркировок.

Маркировка М называется тупиковой, если при этой маркировке ни один переход не может сработать.

Маркировка М¹ достижима из маркировки М, если на графе достижимости существует такой путь ΐ=(t₁,t₂,…,t_k), что

t₁ t₂ t_k

m→m₁→…→m¹

Множество всех маркировок, достижимых из начальной маркировки m₀, называется множеством достижимости сети Петри и обозначается R(N). На рис.26.1 показано построение графа достижимости.

Лекция №28.

Тестирование абстрактных автоматов

Продолжительность: 2 часа (90) минут

Ключевые (основные) вопросы (моменты)

теория экспериментов с автоматами

установочный эксперимент

диагностика автомата

Дата добавления: 2015-12-01