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

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

35. Классы языков сетей Петри. Пример.

Пусть N – класс всех СП. На основе введенных ранее понятий и видов помечающих функций (свободная ПФ, всюду определенная ПФ и частично определенная ПФ) можно образовать следующие классы языков СП. В данном случае верхний индекс λ :ПФ могут быть частично определенными, то есть сеть может содержать λ-переходы. Верхний индекс f означает, что используются свободные ПФ. Нижний индекс 0 означает, что рассматриваются терминальные языки.

Рассмотрим СП с различными вариантами помечающей функции, для каждой найдем префиксный и терминальный языки (Рис. 41).

Пусть μ₀=(1000), μ_t=(0001).

Допустимые последовательности запусков: 1) t₂t₄; 2) (t₁ ...t₁) t₂ (t₃ ...t₃) t₄

^{n1 раз n2 раз}

Варианты помечающей функции:

1. 
   Свободная ПФ – Σ₁(t_j)=t_j.
   

Префиксный язык:L(C)={t₂, t₂t₄, t₁ⁿ¹, t₁ⁿ¹t₂, t₁ⁿ¹t₂t₃ⁿ³, t₁ⁿ¹t₂t₃ⁿ³t₄:n₁1,n₁n₃}={t₁ⁿ¹t₂ⁿ²t₃ⁿ³t₄ⁿ⁴: 0≤n₁, 0n₂1, 0n₃n₂*n₁, 0n₄n₂}.

Терминальный язык: L(C, μ₀, μ_t)={t₁ⁿt₂t₃ⁿt₄ ,t₂t₄:nN₀}.

2) Пусть Σ2- всюду определенная помечающая функция, сеть не содержит λ-переходы
Префиксный язык: L(C, Σ2) ={ an1bn2: n11, 0n2n1}. Терминальный язык: L(C, Σ2, μ0, μt) ={anbn: nN}.

3) Пусть Σ3 - частично определенная помечающая функция, сеть содержит λ-переходы
Префиксный язык: L(C, Σ3) ={an1bn2cn3: 0n11, (n1=0→n2=0), (n1=1→n2=1), 0n3n1}. Терминальный язык: L(C, Σ3, μ0, μt) ={abnc: n≥0}.