【Petri网导论学习笔记】Petri网导论入门学习（十一） —— 3.3 变迁发生序列与Petri网语言

3.3 变迁发生序列与Petri网语言

对于 Petri 网进行分析的另一种方法是考察网系统中所有可能发生的变迁序列以及这些序列所构成的集合的性质。如所周知，一个字母表上满足某些特定条件的字符串的集合，称为该字母表上的一个语言。如果我们把一个 Petri 网的变迁集 $T$ 看作一个字母表（即把每个变迁看作一个字符），或者给出变迁集到某个字母表 $\Gamma$ 上的一个映射的定义，那么该 Petri 网的所有可能发生的变迁序列（或这些序列映射到 ${\Gamma }^{\ast }$ 的字符串）的集合就是 $T$（或 $\Gamma$）上的一个语言。

变迁为字母表

在 Petri 网语言理论中，根据终止状态的不同取法，把 Petri 网语言（Petri net language) 分成 4 型。在每一型中，又根据变迁集 $T$ 到字母表 $\Gamma$ 的映射 $\phi$ 的不同规定，分成 3 类。一共给出了 4 型 12 类 Petri 网语言。

根据终止状态划分4型，映射划分3类，共4型12类

定义 3.4

设 $\Sigma =(S,T;F,M_0)$ 为一个 Petri 网，$\phi :T\to \Gamma$ 为标注函数，$Q_t\subseteq R(M_0)$。令

L = { φ ( σ ) ∈ Γ ∗ ∣ σ ∈ T ∗ : M 0 [ σ ⟩ M , M ∈ Q t } L = \{\varphi(\sigma) \in \Gamma^* \mid \sigma \in T^*: M_0 [\sigma \rangle M, M \in Q_t\} L={ φ(σ)∈Γ∗∣σ∈T∗:M0​[σ⟩M,M∈Qt​} (3.19)

L ′ = { φ ( σ ) ∈ Γ ∗ ∣ ( σ ∈ T ∗ : M 0 [ σ ⟩ M ) ∧ ( ∃ M ′ ∈ Q t : M ≥ M ′ ) } L' = \{\varphi(\sigma) \in \Gamma^* \mid (\sigma \in T^*: M_0 [\sigma \rangle M) \land (\exists M' \in Q_t: M \geq M')\} L′={ φ(σ)∈Γ∗∣(σ∈T∗:M0​[σ⟩M)∧(∃M′∈Qt​:M≥M′)} (3.20)

1. 若 $Q_t$ 是预先给定的 $R(M_0)$ 的一个子集，则称 $L$ 为 $\Sigma$ 产生的 $L$-型语言；$L^{\prime }$ 称为 $\Sigma$ 产生的 $G$-型语言。
2. 若 Q t = { M ∈ R ( M 0 ) ∣ ∀ t ∈ T : M [ t ⟩ } Q_t = \{M \in R(M_0) \mid \forall t \in T: M[t\rangle\} Qt​={ M∈R(M0​)∣∀t∈T:M[t⟩}，则称 $L$ 为 $\Sigma$ 产生的 $T$-型语言。
3. 若 $Q_t=R(M_0)$，则称 $L$ 为 $\Sigma$ 产生的 $P$-型语言。

1. $L$-型语言：

   • 定义：终止状态 $Q_t$ 是初始标记状态可达集 $R(M_0)$ 的一个子集。
   • 特点：只包含那些能精确到达 $Q_t$ 中某个标记的变迁序列。

2. $G$-型语言：

   • 定义：允许到达的标记 $M$ 可以大于 $Q_t$ 中的某个标记。
   • 特点：包含那些能到达或超过 $Q_t$ 中某个标记的变迁序列。（能到就可以不要求精确到，能大于他的那个状态也行，能覆盖）

3. $P$-型语言：

   • 定义：终止状态 $Q_t$ 是所有可达标记，即 $R(M_0)$。
   • 特点：包含所有从初始标记 $M_0$ 出发可达的变迁序列。

4. $T$-型语言：

   • 定义：终止状态 $Q_t$ 包含所有可以从 $M_0$ 出发的死标签。
   • 特点：包含那些死标签。

   区别总结

• 终止条件：$L$ 型要求精确到达，$G$ 型允许覆盖，$P$ 型包括所有可达状态，$T$ 型是死标签集合。
• 应用场景：不同类型语言适用于不同的系统建模需求。例如，$L$ 型适合需要精确控制的系统，而 $T$ 型适合需要持续运行的系统。

定义 3.5

设 $\Sigma =(S,T;F,M_0)$ 为一个 Petri 网，$L$ 是 $\Sigma$ 产生的 $L$-型 ($G$-型, $T$-型, $P$-型) 语言。对于标注函数 $\phi :T\to \Gamma$:

1. 若 $\Gamma =T$，且 $\forall t\in T:\phi (t)=t$，则称 $L$ 为 $\Sigma$ 产生的 $L$-型 ($G$-型, $T$-型, $P$-型) 无标注语言，记为 $L^f(G^f,T^f,P^f)$。

2. 若 $\forall t\in T,\phi (t)\ne \lambda (\lambda \text{ 表示空串})$，则称 $L$ 为 $\Sigma$ 产生的 $L$-型 ($G$-型, $T$-型, $P$-型) 无空标注语言，记为 $L(G,T,P)$；否则称 $L$ 为 $\Sigma$ 产生的 $L$-型 ($G$-型, $T$-型, $P$-型) 含空标注语言，记为 $L^{\lambda }(G^{\lambda },T^{\lambda },P^{\lambda })$。

如果映射后两者相等，则称无标注语言

不相等，如果不存在空串称为无空标注语言

有空串称为含空标注语言

定义 3.4 和定义 3.5 把 Petri 网语言分成 4 型 12 类，如表 3.1 所示。

各种型（类）语言的背景是明显的。对于一个 Petri 网 $\Sigma =(S,T;F,M_0)$，$L$-型语言和 $G$-型语言分别为 $\Sigma$ 中到达或覆盖某些预先给定的标识的变迁发生序列（或它们到某字母表上的映象）的集合，$T$-型语言是指那些导致死标识的变迁序列（或它们到 $\Gamma$ 的映象）的集合，$P$-型语言是 $\Sigma$ 中一切可能发生的变迁序列（或它们到 $\Gamma$ 的映象）的集合。可见，Petri 网语言的分“型”同形式语言中 Chomsky 文法体系的“型”没有任何联系。标注函数 $\phi$ 则是对各个变迁在被描述的实际系统中所对应的动作的一个注解。例如，当两个变迁在被描述的系统中对应同一个（种）动作时，可以对它们赋予相同的标注。当一个变迁在被描述系统中不代表任何实际动作（即是一种虚动作，虚工序）时，则可以对它赋予空标注（$\lambda$-标注）。

与乔姆斯基分类的型没有关系

标注函数只是变迁在实际系统对应动作的一个注解

空标注代表一个变迁在被描述的系统中不代表任何实际动作，虚动作，虚工序

在所定义的 12 类 Petri 网语言中，$L^{\lambda }$是范围最广的一类。其他各类型的 Petri 网语言都可以转化为$L^{\lambda }$的一个子类。[4] 对$L$- 型语言作了详细的讨论，并指出每一个$L$一型 Petri 网语言都可以由一个标准 Petri 网产生。

定义 3.6

设$\Sigma =(S,T;F,M_0)$为一个 Petri 网。如果
1)存在$s_b,s_f\in S$,使得 ∙ s b = ∅ ^\bullet s_b=\emptyset