1. Понятие дискретной динамической системы

• Название: 1. Понятие дискретной динамической системы
• Дата: 23.11.2018
• Размер: 0.51 Mb.
• Имя файла: tmp_4118-Otvety_k_ekzamenu_po_predmetu_Teoria_vychislitelnykh_pr.docx
• Тип: Документы; #57412
• страница: 7 из 15

21. Правила выполнения сети Петри. Пример выполнения сети Петри.

1. Если переход t_j разрешен, то он может быть запущен, в результате маркировка μ заменяется на новую маркировку μ'.

2. Если два или более переходов, не имеющих общих входных позиций, разрешены, то они могут быть запущены в любой последовательности или параллельно.

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

4. Запуск переходов продолжается до тех пор, пока в СП не останется разрешенных переходов. Тогда сеть останавливается. Не исключено, что СП не останавливается.

22.Пространство состояний сети Петри. Функция следующего состояния

Состояние СП определяется ее маркировкой. Запуск перехода изменяет состояние сети Петри посредством изменения маркировки сети. Пространство состояний СП, обладающей n позициями, есть множество всех маркировок, т. е.N.

Изменение в состоянии μ, вызванное запуском перехода t_j, определяется функцией следующего состояния: δ(μ,t_j): NТ→ N. δ(μ,t_j)=

23.Две последовательности, описывающие выполнение сети Петри. Расширенная функция следующего состояния. Принцип монотонности.

При выполнении сети Петри получаются две последовательности: последовательность маркировок (μ₀,μ₁,μ₂,..) и переходов, которые были запущены σ=(t_jo,t_j1,t_j2,..). Эти последовательности связаны соотношением: δ(μ_k,t_jk)= μ_k+1 для k=0,1,2,..

Имея μ₀ и σ, легко получить последовательность маркировок сети Петри. Наоборот, зная μ₀ и последовательность маркировок, можно восстановить σ (Неоднозначность восстановления последовательности переходов может получиться, если два различных перехода имеют одинаковые комплекты входных и выходных позиций).

Пусть имеется маркированная СП С=(P, T, I, O, μ₀) и σ=(t_jo, t_j1, t_j2,..). δ(μ_k,t_jk)= μ_k+1 для k=0,1,2,.. Расширенная функция следующего состояния - это δ(μ₀,σ)= δ(μ₀, t_jo, t_j1, t_j2, ...). Она определена только когда каждый из переходов в разрешен к моменту запуска.

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

24. Достижимая маркировка. Непосредственно достижимая маркировка. Множество достижимости сети Петри. Пример.

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

Маркировка μ* достижима из маркировки μ, если существует последовательность маркировок с начальной маркировкой μ и конечной μ*, в которой каждая последующая маркировка непосредственно достижима из предыдущей.

Множество достижимости R(C,μ₀) маркированной СП (C,μ₀) - множество всех маркировок, достижимых из μ_0.

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