ВУЗ:
Составители:
34
Начальная разметка
0
M
задается следующим образом:
1)(
10
=pM
,
2)(
20
=pM
,
0)(
30
=pM
или в векторной форме:
)0,2,1(
0
=M
.
При разметке
0
M
могут сработать переходы
1
t
и
2
t
, так как
)0,2,1()(),0,0,1()()0,2,1(
2010
=•≥=•≥= tFMtFM
. Пе-
реходы
3
t
и
4
t
не могут сработать, так как
030
),1,0,0()( MtFM =≥
.
В результате срабатывания перехода
1
t
разметка
0
M
сменяется на разметку
)0,3,1(
, а в результате срабатывания пере-
хода
2
t
разметка
0
M
сменяется на разметку
)1,0,0(
. Обе новые разметки непосредственно следуют после
0
M
в рассматри-
ваемой сети
N
, происходящие в результате срабатывания ее переходов, в виде графа разметок – ориентированного графа,
множество вершин которого образовано множеством
)(NR
достижимых в
N
разметок. Из вершины
M
в вершину
M
′
ве-
дет дуга, помеченная символом перехода
t
, если и только если
MtM
′
[
.
Разметка
)(
NRM
∈
называется тупиковой. Если в сети
N
не существует ни одного перехода, который может срабо-
тать при этой разметке. Для рассматриваемой сети тупиковыми являются разметки
)0,2,0(
,
)0,3,0(
,
)0,4,0(
,…,
)0,,0(
n
,
…
Легко видеть, что если выделить путь по дугам графа разметок, начинающийся в вершине
M
и заканчивающийся в
вершине
M
′
, и выписать подряд все встречающиеся символы переходов, то полученное слово образует последовательность
срабатываний, ведущих от
M
к
M
′
. Множество всех слов, полученных выписыванием символов переходов вдоль путей,
начинающихся в
0
M
, образует множество последовательностей срабатываний сети, или ее свободный язык. Так, язык рас-
сматриваемой сети включает слова
,,,,,,{
32211121
ttttttttλ
,,,
12111142
tttttttt
,
321
ttt
,
421
ttt
,
142
ttt
,
1111
tttt
,
2111
tttt
,
3211
tttt ,
4211
tttt ,
1421
tttt ...}
.
Следующая теорема характеризует эффект увеличения начальной разметки в сети.
Теорема. Пусть
),,,,(
0
MWFTPN =
,
),,,,(
0
KMWFTPN +=
′
, где
||P
NK
∈
. Тогда
а)
)()()( NRKM
NRM
′
∈+⇒∈
;
б)
)()(
NLNL
′
⊆
;
в)
)()[([
2121
KMKMMM +τ+⇒τ
.
Доказательство. Воспользуемся индукцией по длине срабатываемых последовательностей. Прежде всего
)(
0
NRM ∈
и
)()(
0
NRKM
′
∈+
. Заметим также, что
00
[
MM λ
, где
λ
– пустая последовательность,
)(NL∈λ
и
)(NL
′
∈λ
. Предполо-
жим, что
MM τ[
0
в
N
и
)()[(
0
KMKM +τ+
.
Покажем, что
)()[([: KMtKMMtMTt +
′
+⇒
′
∈∀
.
Если
t
может сработать при разметке
M
в сети
N
, т.е.
)(tFM •≥
, то
t
может сработать и при разметке
MKM
≥+ )(
в сети
N
′
. Это означает, что последовательность срабатываний
tτ
принадлежит как
)(NL
, так и
)(
NL
′
. (Если
t
не может
сработать при
M
в
N
, то это не исключает возможности срабатывания
t
при
MKM ≥+ )(
в сети
N
′
.) После срабатывания
перехода
t
в
N
и соответственно в
N
′
разметка в обеих сетях изменяется следующим образом:
MtFtFM
′
=•+•− )()(
;
KMKtFtFMtFtFKM +
′
=+•+•−=•+•−+ ))()(()()()(
.
Тем самым установлена справедливость соотношений а) и б). Аналогично можно убедиться в том, что имеет место со-
отношение в). □
3.2. СВОЙСТВА СЕТЕЙ ПЕТРИ И ИХ АНАЛИЗ
Для постановок задач анализа сетей Петри прежде всего необходимо указать и формально определить те свойства се-
тей, которые целесообразно анализировать. Естественно, что при выборе таких свойств главную роль играет ориентация на
практические задачи, возникающие при исследовании моделируемых сетями дискретных систем. Когда такие свойства вы-
делены, становится вопрос о возможности их автоматического распознавания в произвольных сетях Петри или в некоторых
частных случаях сетей. Наконец, третий этап исследований состоит в нахождении оптимальных алгоритмов распознавания
свойств сетей, которые оказываются принципиально распознаваемыми.
3.2.1. Основные свойства сетей Петри
Первое из рассматриваемых ниже свойств сетей Петри связано с ограниченной емкостью реальных условий реализации
событий. Действительно, из определения правил срабатывания переходов сети следует, что для реализации события, моде-
лируемого некоторым переходом, достаточно, чтобы каждое его входное место-условие содержало некоторое конечное чис-
Страницы
- « первая
- ‹ предыдущая
- …
- 30
- 31
- 32
- 33
- 34
- …
- следующая ›
- последняя »
