第三部分网的分析方法.ppt

第三部分Petri网的分析方法 提纲 可达标识图与可覆盖性树关联矩阵与状态方程Petri网语言Petri网进程 可达标识图与可覆盖性树 对于有界Petri网 其可达标识集R M0 是一个有限集合 因此可以以R M0 作为顶点集 以标识之间的直接可达关系为弧集构成一个有向图 称为Petri网的可达标识图 reachablemarkinggraph 定义3 1 设PN P T F M0 为一个有界Petri网 PN的可达标识图定义为一个三元组RG PN R M0 E L 其中E Mi Mj Mi Mj R M0 tk T Mi tk Mj L E T L Mi Mj tk当且仅当Mi tk Mj称R M0 为顶点集 E为弧 边 集 若L Mi Mj tk 则称tk为弧 Mi Mj 的旁标 可达标识图与可覆盖性树 通过可达标识图RG PN 可以分析有界Petri网PN的各种性质 定理3 1 对任意Mi Mj R M0 Mj是从Mi可达的当且仅当在RG PN 中 从Mi到Mj存在一条有向路 推论3 1 在RG PN 中 从M0到每个结点都有一条有向路 推论3 2 M R M0 是PN的一个死标识当且仅当在RG PN 中 M是一个终端标识 定理3 2 设pj P 在Petri网PN中pj的界B pj 等于RG PN 中各个顶点向量的第j个分量的最大值 推论3 3 PN是安全的当且仅当RG PN 中每个顶点的向量都是0 1向量 可达标识图与可覆盖性树 定理3 3 有界Petri网PN是活的当且仅当在RG PN 中 从顶点M0出发的每条有向路都走入一个强连通子图 而且在每个这样的强连通子图中 每个t T至少是一条有向弧的旁标 定理3 4 有界Petri网PN的两个变迁t1和t2处于公平关系的充分必要条件是在RG PN 的每条有向回路C中 t1是其中的一条弧的旁标当且仅当t2也是其中一条弧的旁标 定理3 5 PN是公平Petri网的充分必要条件是在RG PN 的每条有向回路C中 每个t T都至少是C中一条弧的旁标 定理3 3 3 4和3 5在无界Petri网中还成立吗 可达标识图与可覆盖性树 若PN不是有界网 则R M0 是一个无限集合 无法画出PN的可达标识图 为了用有限形式表达一个有无限个状态的系统的运行情况 引入一个表示无界量的符号 具有下述性质 1 对任意正整数n n n 2 当库所pj中的标识数在Petri网的运行过程中趋向于无限增长时 就把标识向量中的第j个分量改为 以此覆盖所有这类标识 通过引入 就可以用有限树来反映无界Petri网的运行情况 称该有限树为Petri网PN的可覆盖性树 coverabilitytree 记为CT PN 可达标识图与可覆盖性树 算法3 1 Petri网可覆盖性树的构造算法输入 PN P T F M0 输出 CT PN 算法步骤 Step0 以M0作为CT PN 的根结点 并标之以 新 Step1 While存在标注为 新 的结点Do任选一个标注为 新 的结点 设为M Step2 If从M0到M的有向路上有一个结点的标识等于MThen把M的标注改为 旧 返回Step1 Step3 If t T M t Then把M的标注改为 端点 返回Step1Step4 For每个满足M t 的t TDo4 1 计算M t M 中的M 4 2 If从M0到M的有向路上存在M 使M M Then找出使M pj M pj 的分量j 把M 的第j个分量改为 4 3 在CT PN 中引入一个 新 结点M 从M到M 画一条有向弧 并把此弧旁标以t Step5 擦去结点M的 新 标注 返回Step1 可达标识图与可覆盖性树 M0 1 0 0 0 t1 1 0 0 新 新 1 0 1 0 新 新 新 新 新 旧 旧 新 端点 可达标识图与可覆盖性树 定理3 1 PN是有界Petri网当且仅当 按算法3 1构造的 CT PN 中 每个结点的标识向量都不含有 分量 对有界Petri网PN 按照算法3 1构造出来的树结构称为PN的可达性树 reachabilitytree 记为RT PN 定义3 2 设CT PN 为Petri网的可覆盖性树 若将CT PN 中标识向量相同的结点合并在一起 便得到PN的可覆盖性图 记为CG PN M0 1 0 0 0 t1 1 0 0 1 0 0 t1 1 0 0 t3 t1 t3 提纲 可达标识图与可覆盖性树关联矩阵与状态方程Petri网语言Petri网进程 关联矩阵与状态方程 网的结构可以用一个矩阵来表示 从而可以引入线性代数的方法对Petri网进行分析 定义3 3 设PN P T F M0 为一个Petri网 P p1 p2 pm T t1 t2 tn 则网N P T F 可以用一个n行m列矩阵A aij n m 3 1 来表示 称A为PN N 的关联矩阵 incidencematrix 其中 关联矩阵与状态方程 PN的输出矩阵PN的输入矩阵行向量列向量标识M 关联矩阵与状态方程 p1 p2 t1 t2 p4 t3 t4 p3 0100 1000 0011 0110 1000 0110 1000 0001 1 100 1110 10 1 1 0 1 11 关联矩阵与状态方程 引理3 1 设PN P T F M0 为一个Petri网 A为PN的关联矩阵 ti T 则M ti 的充分必要条件是 引理3 2 设PN P T F M0 为一个Petri网 A为PN的关联矩阵 如果M ti M 则有 定理3 2 设PN P T F M0 为一个Petri网 A为PN的关联矩阵 若M R M0 则存在非负整数的n维向量X 使得 上式称为Petri网的状态方程 stateequation 状态方程是M从M0可达的一个必要条件 而非充分条件 关联矩阵与状态方程 证 变迁发生序列与Petri网语言 Petri网进行分析的另一种方法是考察网系统中所有可能发生的变迁序列以及这些序列构成的集合的性质 一个字母表上满足某些特定条件的字符串的集合 称为该字母表上的一个语言 将Petri网的变迁集T看作一个字母表 或者给出变迁集到某个字母表 上的一个映射 那么该Petri网所有可能发生的变迁序列 或其映射 的集合就是T 或 上的一个语言 变迁发生序列与Petri网语言 定义3 4 设PN P T F M0 为一个Petri网 T 为标注函数 Qt R M0 令L T M0 M M Qt L T M0 M M Qt M M 1 若Qt是预先给定R M0 的一个子集 则称L为PN产生的L 型语言 L 称为PN产生的G 型语言 2 若Qt M R M0 t T M t 则称L为PN产生的T 型语言 3 若Qt R M0 则称L为PN产生的P 型语言 变迁发生序列与Petri网语言 定义3 5 设PN P T F M0 为一个Petri网 L是PN产生的L 型 G 型 T 型 P 型 语言 对于标注函数 T 1 若 T 且 t T t t 则称L是PN产生的L 型 G 型 T 型 P 型 无标注语言 记为Lf Gf Tf Pf 2 若 t T t 表示空串 则称L是PN产生的L 型 G 型 T 型 P 型 无空标注语言 记为L G T P 否则称L是PN产生的L 型 G 型 T 型 P 型 含空标注语言 记为L G T P 变迁发生序列与Petri网语言 设Qt M1 则Lf PN Tf PN Pf PN t1 t2 t3 t4 t1 t1 t2 t3 t4 t1 t3 这里Qt M0 M1 M2 变迁发生序列与Petri网语言 变迁发生序列与Petri网语言 RL PNL CFL CSL 每种正规语言 RL 都是Petri网语言 PNL 每种Petri网语言都是上下文有关语言 CSL Petri网语言类同上下文无关语言类 CFL 是两个相交但互不包含的语言类 PNL同Chomsky体系中各型语言的关系 变迁发生序列与Petri网语言 定义3 6 设PN P T F M0 为一个Petri网 称L0 PN T M0 M 或L0 PN T M R M0 M0 M 为PN所确定的P 型无标注语言 简称为PN所确定的语言 L0 PN 是Petri网PN从初始标识M0出发的一切可发生的变迁序列的集合 由于M0 R M0 所以总有 L0 PN 变迁发生序列与Petri网语言 设 为一个串 L为一个语言 记Pref x y xy Suff x y yx Pref L x L x Pref Suff L x L x Suff 定义3 7 设L为一种语言 如果Pref L L则称L为一种前缀语言 定理3 3 Petri网PN P T F M0 所确定的语言L0 PN 是一种前缀语言 即Pref L0 PN L0 PN 变迁发生序列与Petri网语言 在形式语言理论中 Pumping引理是正规语言和上下文无关语言的一个重要性质 定理3 4 设PN P T F M0 为一个有界Petri网 L0 PN 如果 R M0 则 可写成 xyz的形式 其中x y z T xy R M0 且 y 1 使得对任意非负整数i 都有xyiz L0 PN 注 RG PN 可看作是有限自动机的一个图形表示 推论3 1 设PN P T F M0 为一个有界Petri网 若 L0 PN 使得 R M0 则L0 PN 是一个无限集 提纲 可达标识图与可覆盖性树关联矩阵与状态方程Petri网语言Petri网进程 Petri网进程 Petri网语言不能很好地反映系统中的并发行为 为此网论中引入了Petri网进程的概念 Petri网进程的概念是建立在出现网 occurrencenet 和网映射等概念基础上的 定义3 8 设N P T F 为一个网 定义 称F 为流关系F的传递闭包 id表示自反关系 定义3 9 设 N B E G 为一个网 如果 1 b B b 1 b 1 2 x y B E x y G y x G 则称N为一个出现网 其中G 表示流关系G的传递闭包 出现网中没有情态 标识 的概念 它是通过流关系来描述系统中事件发生的轨迹 Petri网进程 定义3 10 设N B E G 为一个出现网 l B E 如果 x y l x y G y x G 则称l为N的一个线集 若l是N的一个线集 且任意l l都不是N的线集 则称l为N的一条线 定义3 11 设N B E G 为一个出现网 u B E 如果 x y u x y G y x G 则称u为N的一个切集 若u是N的一个切集 且任意u u都不是N的切集 则称u为N的一个切 若u是N的一个切 且u B 则称u为N的一个s 切 设u1 u2为N的两个切 如果 x u1 y u2 x y G 则记为u1 u2 事件e1和e2存在并发关系当且仅当N中存在一个切u 使得e1 u且e2 u事件e1和e2存在固定的顺序关系当且仅当N中存在一条线l 使得e1 l且e2 l Petri网进程 定义3 12 设N P T F 为一个网 N B E G 为一个出现网 若映射 B E P T满足条件 1 对于 B P E T x y B E x y G x y F 2 e E e e e e 则称 定义了N到N的一个映射 记为 N N 定义3 13 设PN N M0 P T F M0 为一个Petri网 N B E G 为一个出现网 如果 N N满足条件 1 b1 b2 B b1 b2 b1 b2 b1 b2 b1 b2 2 p P b b p b M0 p 则称 N 为PN的一个进程 process Petri网进程 Petri网进程 定义3 14 设PN N M0 P T F M0 为一个Petri网 N B E G 为一个出现网 如果 N N满足条件 1 b1 b2 B b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 b1 b2 2 p P b b p b M0 p 则称 N 为PN的一个满进程 process 定理3 5 设 N 为Petri网PN N M0 P T F M0 的一个满进程 则对的任一个s 切u 都存在M R M0 使得 b b u b p M p 简记为 u M Petri网进程 证 令u0 b b 显然u0是N的一个s 切 且 u0 M0 设u为N的任一个s 切 显然u0 u 记E u0 u e E b0 u0 b u b0 e G e b G 下面对 E u0 u 用数学归纳法证明定理的结论 当 E u0 u 0时 显然u u0 从而 u0 M0 R M0 设对 E u0 u k的任一个s 切u 都有M R M