Читайте также:
|
|
Сети Петри предназначены для моделирования дискретных асинхронных процессов. Их основные отличия от автоматной модели – возможность отображать параллелизм, асинхронность и иерархичность моделируемых объектов.
Сети Петри можно описать формально в виде
N=(P,T,F,H,m0 )
Где P – конечное непустое множество позиций (состояний);
Т - конечное непустое множество переходов (событий);
F:PхT®{0,1,2..} – функция входных инциденций
H:TхP®{0,1,2..} - функция выходных инциденций
m0 :P®{0,1,2..} – начальная маркировка (разметка) сети.
Сети Петри удобно представлять графически в виде двудольного ориентированного графа с двумя типами вершин, соответствующими
0001 0011 0010
а) S1 S2 б) S1 S2
1001
0101 1010
0110
![]() |
S3 S4 S3 1100 S4
0100 1000
00 01 000 001
в) S1 S2 г) S1 S2
101
011
![]() |
S3 S4 S3 110 S4
10? 100 010
Рис.27.1
позициям pÎP и переходам tÎT (рис.44) Позиции изображаются кружками. Внутри кружка могут находиться маркеры (фишки), изображаемые точками. Переходы изображаются черточками (барьерами).
Функции входных и выходных инциденций могут быть представлены матрицами. Для сети на рис. 27.1 имеем:
t1 t2 t3 t4 p1 p 2 p3 p4 p5
p1 1 0 0 0 t1 0 0 1 2 0
p2 1 0 0 0 t2 1 0 0 0 1
F= p3 0 1 0 0 H= t3 1 1 0 0 0
p4 0 0 1 0 t4 0 0 0 1 0
p5 0 0 0 1
Если можность множества P равна n, то маркировка представляется n-мерным вектором, значения координат которого равны числу маркеров в соответствующих позициях.
Переход от одной маркировки к другой происходит в результате срабатывания переходов. Переход t может сработать при маркировке m, если является возбужденным, т.е. в каждой входной позиции перехода, t число маркеров не меньше веса (кратности) дуги, соединяющую эту позицию с переходом:
" pÎP:m1(p) – F(p,t)³0
В результате срабатывания перехода t маркировка М заменяется маркировкой М1
VPÎP:M1(P)= M(P) – F(p,t)+H(t,p).
Это означает, что в результате срабатывания из всех входных позиций перехода t удаляются F(p,t) маркеров, а в каждую входную позицию добавляется H(t,p) маркеров. В рассматриваемом случае маркировка M1 непосредственно достижима из маркировки М, что обозначается М→ M1 функционирование сети Петри – это последовательная система маркировок в результате срабатывания возбужденных переходов. Состояние сети Петри – в каждый момент времени определяется ее текущей маркировкой.
Два возбужденных не взаимодествующих перехода могут сработать независимо друг от друга, поэтому сеть Петри как модель отражает альтернативность поведения, паралельность и асинхронность.
Возможные варианты функционирования сети описываются графом достижимости. Вершинами графа достижимости являются маркировки, а
дуги представляют отношение непосредственной достижимости на множестве маркировок.
Маркировка М называется тупиковой, если при этой маркировке ни один переход не может сработать.
Маркировка М1 достижима из маркировки М, если на графе достижимости существует такой путь ΐ=(t1,t2,…,tk), что
t1 t2 tk
m→m1→…→m1
Множество всех маркировок, достижимых из начальной маркировки m0, называется множеством достижимости сети Петри и обозначается R(N). На рис.26.1 показано построение графа достижимости.
Лекция №28.
Тестирование абстрактных автоматов
Продолжительность: 2 часа (90) минут
Ключевые (основные) вопросы (моменты)
теория экспериментов с автоматами
установочный эксперимент
диагностика автомата
Дата добавления: 2015-12-01; просмотров: 29 | Нарушение авторских прав