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

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

32. Помеченные сети Петри. Пример.

Помеченная СП – пара (C,Σ), где С=(Р, Т, I, О), Σ: Т→А – помечающая функция над некоторым алфавитом А. На рисунке показан пример помеченной СП (C, Σ) над алфавитом {a, b, c}: Σ: Σ(t1)= a, Σ(t2)= c, Σ(t3)= b, Σ(t4)= c.

В зависимости от вида получают различные классы языков СП.

Если Σ – частичная функция, т.е. некоторым переходам не сопоставляется никакой символ из А, то эти непомеченные переходы называются λ-переходами и помечаются одним и тем же «пустым» символом λ.

Частичные функции удобны в тех случаях, когда при моделировании системы нужно ввести вспомогательные переходы, не связанные непосредственно с событиями системы, а используемые для некоторых специальных целей моделирования. С помощью λ-переходов также можно «маскировать» события, которые не должны рассматриваться в данной задаче моделирования.

33.Префиксный язык сети Петри. Свободный терминальный язык сети Петри. Терминальный язык сети Петри. Пример.

Пусть τT* - допустимая последовательность запусков переходов СП C, (C, Σ) – помеченная сеть, Σ (τ)A* - помечающая последовательность, соответствующая τ.

Если L(C) – свободный язык СП C, то множество {Σ (τ)| τL(C)} называется префиксным языком помеченной сети (C, Σ); если A=T, то свободный язык СП совпадает с ее префиксным языком.

Пусть μ₀ – начальная маркировка СП, а μ_t – некоторая фиксированная терминальная маркировка. Множество L(C,μ₀,μ_t)={τT*|δ(μ₀,τ)=μ_t} называется свободным терминальным языком СП C, т.е. свободный терминальный язык состоит из всех последовательностей переходов, ведущих от начальной маркировки μ₀к некоторой фиксированной терминальной маркировке μ_t. Такие последовательности образуют подмножество терминальных последовательностей СП.

Соответственно множество {Σ(τ)|τL(C,μ₀,μ_t)} образует терминальный язык помеченной сети (C,Σ).

Пример: пусть τ₁, τ₂ - допустимые последовательности запусков переходов некоторой СП, ведущие из начальной маркировки в: τ₁=t₁t₁; τ₂=t₂t₄t₃t₃t₃.

Тогда префиксный язык: {t₁, t₁t₁, t₂t₄t₃t₃t₃, t₂t₄t₃t₃, t₂t₄t₃, t₂t₄, t₂}; терминальный язык: {t₁t₁, t₂t₄t₃t₃t₃}.

34.Три вида помечающих функций для сетей Петри.

Вид 1. Σ(t_j)=t_j для t_jT – свободная помечающая функция (ПФ).

Вид 2. Σ(t_j) определена для t_jT пометки – символы из А. Это всюду определенная помечающая функция. Сеть без λ-переходов.

Вид 3. Σ(t_j) не определена для некоторых переходов, т.е. t_jT– такой переход, t_jпомечается пустым символом λ и объявляется λ-переходом. Тогда это частично определенная помечающая функция.