（机械设计及理论专业论文）分析多时序petri网的自动机模型.pdf

； j j j at h e s i si nm e c h i n e d e s i g na n dt h e o r y a u t o m a t am o d e lf o r a n a l y z i n g m u l t i t i m ep e t r in e t b ys u ny u x i n s u p e r v i s o r ：p r o f e s s o rx i el i y a n g n o r t h e a s t e r nu n i v e r s i t y j a n u a r y2 0 0 8 62 肼6m 3 伽禾肌8肼肌y 、丫；卫 ollli- ，_ ， -1，rj， 、of0，； 独创性声明 本人声明，所呈交的学位论文是在导师的指导f 完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 !的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 t 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 ：茁 思。 学位敝作者虢羽1 釉7 日 期：裾、厶矛 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 f 或部分内容编入有关数据库进行检索、交流。 j ( 如作者和导师不同意网上交流，诸在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 、口rl。 东北大学硕士学位论文摘要 分析多时序p e t ri 网的自动机模型 摘要 p e t r i 网以研究系统模型的组织结构和动态行为为目标，着眼于系统中可能发生的 各种状态变化以及变化之间的关系。p e t r i 网可以用简单的图形元素表示系统变化发生 的条件，以及变化发生后的系统状态。 随着分析问题的深入和系统复杂度的提高，大量的因素引入p e t r i 网系统中。网系 统增加的因素包括条件、时间等等。其中时间因素对网系统的影响很大，在时间因素的 作用下网系统的运行方式，基础特性以及运行情况也发生了变化。 因而，求解多时序p e t r i 网的各种特性变得较为困难。同时，原有求解p e t r i 网系 统的方法都是通过网系统的转置矩阵。根据不同的特性，建立与转制矩阵相关的表达式 与矩阵方程。通过对方程和表达式的求解来得到相应问题域的答案。但这样的求解方式 是建立在矩阵计算基础之上的。我们都知道矩阵的计算需要进行大量的乘法，同时矩阵 中存在大量的元素其数值为零。这样的矩阵运算中存在很多不必要的乘零运算。特别是 随着问题规模的扩大，必然带来矩阵维数的增加，这些乘零运算就更加降低系统的效率。 这样利用矩阵方程来求解p e t r i 网的方式的效率将越来越低，计算机实现的效率也大幅 度的降低。 回避矩阵计算是提高计算分析性能的有效方法。我们可以从网系统的结构出发，利 用图论与离散算法的特性构建分析网系统的算法逻辑。把矩阵计算转变为围绕特定数据 结构与逻辑算法的工作过程，并用相应的形式语言定义这些结构与逻辑，建立分析多时 序p e t r i 网的自动机模型。 利用针对不同问题的p e t r i 网的系统，对实际的问题加以求解。 关键词：多时序p e t r i 网；自动机模型；数据结构与算法；图论与离散算法 。i i 1 东北大学硕士学位论文 a u t o m a t am o d e lf o ra n a l y z i n g m u l t i t i m ep e t r in e t a b s t r a c t t h em a i nd e s t i n a t i o no fp e t r in e ti sa n a l y z i n gt h em o d e lo fs y s t e ms t r u c t u r ea n dd y n a m i c b e h a v i o r s ot h ed e s t i n a t i o no fp e t r in e ti st h er e l a t i o n s h i po ft h ec o n d i t i o n ，w h i c hm a y b e h a p p e n sa n dc h a n g e se a c ht i m ed u r i n gt h er u n n i n go fs y s t e m i ti ss oe a s yf o rp e t r in e t t o d i s p l a yt h ec o n d i t i o no fs y s t e mc h a n g i n ga n dt h es y s t e ma t t i t u d ea f t e rt h ec h a n g i n g f o l l o w i n gt h ed e e p l ya n a l y z i n gf o rt h eq u e s t i o na n dt h ei n c r e a s i n go fc o m p l e x i t yo f s y s t e ms t r u c t u r e ，s 0m a n ya s p e c t sh a v eb e e ne n t e r e di n t op e t r in e t t h en e wa s p e c t si n c l u d i n g c o n d i t i o nt i m e ，a n ds oo n i na l lt h o s e ，t h et i m ea s p e c th a ss om u c he f f e c to nt h ep e t r in e t t i m ea s p e c th a sc h a n g e dt h ep e t r in e tr u n n i n gw a y , s od ob a s i cc h a r a c t e ra n dr u n n i n g c o n d i t i o n s o ，a n a l y z i n gt h ef e a t u r eo ft h em u l t i - t i m ep e t r in e th a sb e e nd i f f i c u l t a tt h es a n l et i m e ， t h eo r i g i n a lw a yt oa n a l y z i n gt h ep e t r in e ti sd e p e n d i n go nt h ec a l c u l a t i o no fc o n v e r s i o n m a t r i xo fp e t r in e t a c c o r d i n gt h e d i f f e r e n tf e a t u r e ，b u i l d i n gt h e d i f f e r e n tf o r m u l aa n d e x p r e s s i o nc a l lg e tt h ea n s w e ro fd i f f e r e n tq u e s t i o nf i e l d b u tt h ew a yo f c a l c u l a t i o nm a t r i xi s d e e p l yd e p e n d e do nt h em a t r i xs t r u c t u r e w ea l lk n o w t h ec a l c u l a t i o no fm a t r i xn e e d ss om a n y m u l t i t u d e s ，a n dt h e r ei sa l w a y ss om a n yz e r oi nam a t r i x s om a n yc a l c u l a t i o n s 丽t 1 1z e r oa r e w a s t i n gt i m e ，e s p e c i a l l ym o r ef o l l o w i n gt h em a g n i f i c a t i o no ft h eq u e s t i o nf i e l d s ot h e e f f i c i e n c yo fa n a l y z i n gm a t r i xh a sb e e nd e c r e a s i n ga n dc a n n o t b ef i n i s h e db yc o m p u t e r s od i s c a r d i n gt h ec a l c u l a t i o no fm a t r i xi st h em a i nw a yo fi n c r e a s i n gt h ea n a l y z i n gt h e f e a t u r e w ec a l ls t a r tf r o mt h es t r u c t u r eo fn e ts y s t e m ，b yd i s c r e t ea l g o r i t h ma n dg r a p ht h e o r y t ob u i l d i n gt h el o g i c a la l g o r i t h mo fa n a l y z i n gt h en e ts y s t e m s ow ec h a n g et h em a t r i x c a l c u l a t i o n st ow o r k i n go ft h es p e c i a ld a t as t r u c t u r ea n dl o g i c a la l g o r i t h m a c c o r d i n gt ot h e f o r m u l al a n g u a g ea n ds t r u c t u r e ，t h em o d e lo fa u t o m a t af o rm u l t i t i m ep e t r in e tc a l lb eb u i l t k e y w o r d ：m u l t i - t i m ep e t r in e t ；a u t o m a t am o d e l ；d a t aa n ds t r u c t u r e ；g r a p ht h e o r ya n d d i s c r e t ea l g o r i t h m i i i f 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i 第1 章引言1 1 1 研究背景1 1 2 研究现状2 第2 章p e t r i 网与自动机一：3 2 1p e t r i 网简述：3 2 1 1p e t r i 网的形式描述：3 2 1 2p e t r i 网系统的扩展5 2 2 形式语言与自动机的简介6 2 2 1 形式语言与自动机- 7 2 2 2 文法与自动机的对应7 2 3 图与树8 2 3 1 图的定义8 2 3 2 树的定义9 第3 章可达集与不变量1 0 3 1p e t r i 网的可达集1 0 3 1 1 变迁的实施条件1 0 3 1 2 可达树和可达图的构造。1 1 3 1 3 构建分析可达集的自动机1 1 3 2p e t r i 网的不变量1 9 3 2 1 不变量的定义19 3 2 2 求解不变量的自动机模型2 0 第4 章竞争策略的自动机模型2 6 4 1 竞争策略的综述2 6 4 2 竞争策略的具体实现2 7 。4 2 1 基于优先级策略的实现2 7 i v 东北大学硕士学位论文目录 4 2 2 基于变迁实施时间策略的实现2 9 4 3 多策略相互作用下的自动机模拟3 0 4 3 1 变迁执行环境中的若干条件。3 0 4 3 2 局部环境中变迁状态的划分与运行逻辑3 1 4 3 3 多策略作用的自动机模型与形式化定义j 3 3 第5 章分析s p n 网的自动机模型3 6 5 1s p n 网简介3 6 5 1 1s p n 网的性质3 6 5 1 2s p n 网的定义3 7 5 1 3s p n 网的同构性j 3 7 5 2s p n 网的有界性3 8 5 3 解决随机转换系统的同构问题4 2 5 3 1 随机转换系统的同构4 2 5 3 2 分析随机转换系统同构的自动机4 3 5 4 状态转移最短路径问题、4 9 5 4 1 求解最短路径算法4 9 5 4 2 求解最短路径的自动机模型5 0 第6 章网系统的分解与压缩：5 5 6 1 网系统的分解与压缩。5 5 6 1 1 接近无关的分解5 5 6 1 2 时间数量级的分解5 6 6 2 时间数量级分解的自动机：。5 7 6 2 1 时间数量级分解的算法逻辑5 7 6 2 2 自动机的运行逻辑5 8 第7 章自动机模型的应用6 1 7 1 柔性制造系统中的应用6 1 7 2 1 柔性制造系统的设计。6 2 7 2 2 不变量的分析6 3 7 2 网络传输中的应用6 4 7 2 1 分析网络路由的延时问题6 4 v 东北大学硕士学位论文 目录 7 2 2 求解最短路径问题6 5 第8 章结论与展望6 7 8 1 结论6 7 8 2 展望6 8 参考文献6 9 致谢7 3 v i t 东北大学硕士学位论文第1 章引言 1 1 研究背景 第1 章引言 在分析与构建一个系统时，我们有很多种方法和工具来分析系统不同方面的 特写。这些方法和工具使我们更容易的分析系统某一方面的特写，为我们实际的 工作提供了很好的指导作用。如u m l 模型，f t a 等等。 在分析系统的动态特性的时候，通常选用p e t r i 网作为我们的方法工具。把 系统的状态和条件看作网系统的位置，把系统的变化和动作看作系统变迁。网系 统的位置和变迁都用相应的图形元素表示，图形元素之间的关系用有向边来表 示。随着我们分析系统的特性的增多、复杂性的提高，p e t r i 网系统引入了许多 新的元素。相应的也出现了不同类型的p e t r i 网的扩展，如p t 网、着色网、时 间网、随机网等等。 普通的网系统自身有很多复杂的特性，如状态的可达性、位置的有界性、 变迁的活性、初始状态的可逆性、标志之间的可达性、事件之间的同步距离和公 平性等。p e t r i 网模型的主要分析方法依赖于可达树、关联矩阵和状态方程、不 变量和分析化简规则。利用这些最基本的特性可以分析网系统大多说的复杂特 性。 对网系统分析的传统方法，主要是从根据网系统的结构出发，通过网系统中 变迁的发生促使系统中位置标识发生变化的信息，建立网系统的关联矩阵和状态 方程。利用计算网系统的关联矩阵和状态方程，根据计算出的向量结果可以分析 系统不同特性，即系统相应的变化情况。 我们都知道矩阵结构本身是一个很复杂的结构，对于有n 行m 列的矩阵它共 有1 1 m 个元素。在每次计算矩阵方程的时候，我们都要计算矩阵与向量之间的 相乘关系，对于一个聊个元素的向量，最终需要i x 肌历次的元素运算。这样的 计算模式对于行数和列数较小的矩阵，还是比较容易计算的，计算次数相对较小。 但对于实际的分析对象来说，通常系统相对复杂，对应的网系统拥有很多的状态 和变迁。随着网系统的复杂性越来越大，变迁和状态的数量的持续增多，矩阵运 算的次数越来越多。对于矩阵运算来说，它的运算次数为n m 所，其复杂度为 o ( n 3 ) 。随着次数n 的增长，计算次数的将以立方次数增长，从而使矩阵的计算 越来越难以实现。 _ 1 - 东北大学硕士学位论文第1 章引言 随着对工程实践的发展，我们逐渐抛弃了传统的手动计算p e t r i 网的方法。 实现分析p e t r i 网的计算机化是分析p e t r i 网的一个有效方法，同时也符合我们 当前数字化设计的主要趋势。但同时传统的矩阵计算方式也存在着自身的计算机 实现问题。当使用计算机来实现对p e t r i 网的分析时，关联矩阵算法复杂度的问 题越是明显。关联矩阵的计算机计算主要有两个方面，一方面是与数值为零的矩 阵元素的乘积；另一方面是矩阵行列数目的提高使相应的计算次数呈现立方级数 的增长。 由于关联矩阵本身多是稀疏矩阵，矩阵中很多的元素都是零元素。这样在计 算矩阵元素相乘时，有大量的非零元素与零元素相乘或是零元素之间的乘积运 算。而这样的乘积运算与非零元素之间的乘积运算要占用相同的计算机计算时 间，这些计算浪费了大量的计算资源同时也毫无意义。同时，关联矩阵自身的计 算效率也较低，我们知道对于以行m 列的矩阵，计算一次矩阵的乘法需要 ，z 所聊次运算。其计算复杂度为o ( n 3 ) ，随着次数n 的增长，计算次数将以立 方级数增长。同时在分析网系统的很多性质时，通常需要进行多次的运算，这样 的分析效率对于大型的网系统是很难以接受的。 我们可以从网系统的结构出发，以网系统中变迁的局部环境作为入手点。系 统变迁的局部环境中有变迁的前置节点和后置节点，前置节点表示变迁实施的条 件，后置节点表示变迁实施的结果。每个变迁的局部环境可以形成相互关联的序 列，将一系列的关联关系看作自动机的发生关系式。我们可以利用自动机的方式 分析网系统的特性。根据分析性质的不同，构建不同的关系发生式，按照不同的 算法逻辑构建不同的自动机模型。这样我们可以放弃计算网系统的关联矩阵的方 法，通过自动机的计算逻辑和发生式构建求解系统特性的最简过程。这样就回避 了大量的矩阵计算过程。 本文也正是此论点出发，针对p e t r i 网系统中几个不同的性质特征和特例问 题。通过构建分析不同网系统特性和求解问题的自动机模型，来验证自动机系统 替代关联矩阵的求解意义，对构建计算机化的求解分析方式起到指导性的作用。 1 2 研究现状 p e t r i 网分析的自动机化是目前对p e t r i 研究的一个新兴的研究方向。目前 国内外的学者针对这一论题展开了的研究较少。仅有的论文也主要是从形式语言 与自动机的理论出发来论证p e t r i 网的性质而不是建立分析模型。 2 t t 东北大硕士学位论文第2 章p e t r i 网与自动机 第2 章 2 1p e t ri 网简述 p e t r i 网与自动机 p e t r i 网的概念最早在1 9 6 2 年由c a r la d a mp e t r i 的博士论文中提出来。 p e t r i 网以研究模型系统的组织结构和动态行为为目标，它着眼于系统中可能发 生的各种状态变化以及变化之间的关系。p e t r i 网易于表示系统变化发生的条件 及变化发生后的系统状态。 2 1 1p e t ri 网的形式描述 个p n 的结构元素包括：位置( p l a c e ) 、变迁( t r a n s i t i o n ) 和弧( a r c ) 。位置用于 描述可能的系统局部状态( 条件或状况) ，例如，计算机和通信系统的队列、缓冲、 资源，工业流程中的生产设备等。变迁用于描述修改系统状态的事件，例如，计 算机和通信系统的信息处理、发送、资源的存取，或是工业流程中的加工过程、 运输过程等。弧使用两种方法规定局部状态和事件之间的关系：它们引述事件能 够发生的局部状态：由事件所引发的局部状态的转换。 在p e t r i 网模型中，标记( t o k e n ) 包含在位置中，它们在位置中的动态的变化表 示系统的不同状态。如果一个位置描述一个条件，它能包含一个标记或不包含标 记，当一个标记表现在这个位置中，条件为真；否则，为值。如果一个位置定义 一个状况，在这个位置中的标记个数用于规定这个状况。例如，在计算机和通信 系统中，标记可以用于表示处理的信息单元、资源单元和顾客、用户等对象实体。 2 1 1 1p e t ri 网的定义 我们首先给出网的一般定义，p e t r i 网系统的形式化定义可表示如下【l 】： 定义1 ：一个三元组n = ( s ，乃f ) 是一个p e t r i 网当且仅当 1 ) sut ( 网非空) 、： 2 ) sut = ( 二元性) ： 3 ) f 互( s xr ) u ( r xs ) ( 流关系仅在于s 与丁的元素关系) ： 4 ) a o m ( f ) uc 耐扩) = su t 没有孤立的元素。 在网中，f 的元素叫弧；a o m ( v ) = = 1 3 y ：g ，y ) f ) ；c d d p ) = x l j y ：，x ) f 3 - 东北大硕士学位论文第2 章p e t r i 网与自动机 。集合x = s u t 是网元素的集合。 在图形上，s 元素用一个圆圈表示，r 元素用一个四方形或是长方形表示， 或是为了节省空间，我们仅用一段黑线表示。在x 元素之间的流关系由带箭头 的弧表示，其图形如下： 图2 1p e t r i 网图例 f i g 2 1i n s t a n c eo fp e t r in e t 定义2 ：前置集和后置集 令n = ( s ，r ；f ) 是一个网系统，且x x ，那么 x - 移l ，z ) f ( x x 的前置集) 。 石。= 涉i g ，y ) f ( x x 的后置集) 。 定义3 ：子网 令l = g 。，互；e ) ，2 = $ ：，疋；e ) 是两个网。 n i 是：的子网，当且仅当墨cs ：，互c 疋且互= en ( 。互) u 亿xs 。) ) 一般情况下，要注意两和系统概念之间的区别。网的概念仅包括位置、变迁 和弧集合，而系统是指网和相关的初始标识。 2 1 1 2 位置变迁p t 系统 p t 系统的形式化定义如下【1 】： 一个六元组- - ( s ，丁：f ，k ，w ，m 。) 是一个p t 系统当且仅当： 1 ) 圆，丁；f ) 是一个网，s 元素是位置集合，丁元素是变迁集合。 2 ) k ：s n + u o 。 是位置容量函数： 3 ) w ：f n + 是弧权函数； 4 东北大硕士学位论文 第2 章p e t r i 网与自动机 4 ) m o ：s n 是初始标识( m a k i n g ) ，满足：v s s ：m o ( s ) k g ) 。 一个p e t r i 网模型的动态行为是内它的实施规则规定的。如果一个变迁的所 有输入位置( 这些位置连接到这个变迁，弧的方向从位置到变迁) 至少包含一个标 记，那么这个变迁可能实施( 相联系的事件可能发生) 。 对这种情况，这个变迁称为可实施。一个可实施变迁的实施导致从它所有输 入位置中都清除一个标记，在它的每一个输出位置( 这些位置连接到这个变迁， 弧的方向从变迁到位置) 中产生一个标记。当使用大于1 的弧权( w e i g h t ) 时，在 变迁每一个输入位置中都要包含至少等于连接弧权的标记个数，它才可实施；这 个变迁的实施，要根据相连接的弧权，在它每一个输出位置中产生相应标记个数。 变迁的实施是一个原子操作，在输入位置中清除标记和在输出位置中产生标记是 一个不可分割的完被操作。 应当注意，p n 模型的状态转换是局部的，它仅涉及一个变迁通过输入和输出 弧连接位置的状态变化。 2 1 2p e t ri 网系统的扩展 含时间因素的p e t r i 网是在原型p e t r i 网的基础上，定义一个从变迁集到某 种时间因素集合的映射。这种时间因素可以用一个实数( 有理数) 、实数区间( 有 理数区间) 或一个随机数表示。它们分别表示变迁发生所需要的时间，或变迁具 备条件发生后可能( 实际) 发生的时间区间。这样，就把网系统的运行轨迹投影 到统一的时间坐标上。 在网系统中加入时间因素，又确定为某些实际系统的模拟和分析带来了方 便。原型p e t r i 网照眼与逻辑层次的系统性能。含时间因素的p e t r i 网则可以对 系统在时间层次或随机品质方面的性能进行分析。 多时序p e t r i 网主要包括以下两类p e t r i 网： 1 ) 时间p e t r i 网i l 】： 时间p e t r i 网的形式化表述是一个五元组： = p ，t ；f ，m ，) ，是定义在变迁集上的时间区间函数，：丁一r 。亿u 砷) ) ，r o 表示非负 实数集。对于f t ，若，o ) = k ，纠，那么当变迁f 在标识m 有发生权限时，至 少要经过货个单位时间才能发生；如果在此期间没有别的变迁发生使f 失去发生 权，那么变迁f 最晚在个时间单位内必然发生。变迁的发生是瞬时的，即变迁 5 - 东北大硕士学位论文第2 章p e t r i 网与自动机 一旦发生，立刻导致标识的改变。 这表明时间p e t r i 网的运行是被放置在一个全局时钟坐标上进行考察的。 一般假设网系统的初始标识出现的时间为零。由于在各个可达标识下，有发生权 的变迁可能要经过一段时间才能发生，因此，不同的可达标识的出现时间就不同。 这样，真个系统的运行同时间紧密地联系在一起。 而对原型p e t r i 网的一些分析方法也可以用来对时间p e t r i 网进行分析， 但必须加上对时间因素的考察。 。 2 ) 时延p e t r i 网【1 】 时延p e t r i 网的形式化表述是一个五元组： = ，t ；f ，m ，d i ) d i 是定义在变迁集r 上的时间函数，即d i ：tjr 。对于f t ， 研( f ) = 口表示变迁f 的发生所需要o t 个时间单位，即当一个标识m 满足m t r 时，变迁f 立刻就可以发生，但要经过a 个时间单位，f 的发生才结束。 3 ) 随机p e t r i 网【l 】 随机p e t r i 网也是一类含有时间因素的p e t r i 网，不过它的各个变迁的时 延是一个随机变量。与确定值的时延p e t r i 网相比较，随机变量的引入使得可以 用p e t r i 网对不确定系统进行建模和分析。 2 2 形式语言与自动机的简介 语言学家乔姆斯基最初从产生语言的角度研究语言。1 9 5 6 年，通过抽象，他 将语言形式定义为由一个字母表中的字母组成的一些串的集合：对任何语言三， 有一个字母表，使得l 。可以在字母表上按照一定的规则定义一个文 法，该文法产生的所有句子组成的集合就是该文法产生的语占。 判断一个句子是否是某种语言的合法句子，需要判断该句子能够有语言对应 的文法产生出来，如果能，它就是合法的，否则，它就是非法的。1 9 5 9 年，乔 姆斯基根据产生语言的文法的产生式，又将语言划分成3 大类。 数学家科林从识别的角度研究语言，给出了语言的另一种描述。克林在研究 神经细胞中建立了自动机模型。他用这种模型来识别一个语言：对于按照一定的 识别规则构造的任一个自动机，该自动机就定义了一个语言。该语言出由自动机 能够识别的所有句子组成。 - 6 东北大硕士学位论文第2 章p e t r i 网与自动机 2 2 1 形式语言与自动机 语言的两种不同的定义方式进一步引起人们的研究兴趣。一个语言，可以采 取不同的描述方式：文法产生语言和自动机识别语言。由于是同一个语言，两种 方式应该是等价的，也就存在两种方式之间的等价的相互转换方法。 将形式语言和自动机的理论相结合，不仅确定了文法和自动机分别从产生和 识别角度定义语言，而且证明了文法与自动机的等价性。 2 2 1 1 文法的定义 文法g 团是一个四元组：g = 匹，y ，s ，e ) z o e ： 1 ) 是一个有限字符的集合，叫做字母表，它的元素称为字母表或是终 结符； 2 ) y 是一个有限字符的集合，叫做非终结符集合，它的元素称为变量或者 非终结符； 3 ) s 是一个特殊的非终结符，即s v ，称为文法的开始符号； 4 ) 尸是有序偶对 ，) 的集合，其中口是集合篷u y ) 上的字符串，但至少 包括一个非终结符；是集合匹uy ) 的元素。一般，将有序偶对0 ，) 记为口专，称为产生式。口称为产生式的左部，称为产生式的右部。 有限状态自动机的定义 2 1 ： 字母表上的有限状态接收机( f a s m ) 是一个五元式， f a s m = 妇，万帅qf ) ；g o e ： 1 ) o 是一个有限状态集合； 2 ) 是字母表，也就是输入带上的字符的集合； 3 ) q 。q 是开始状态 4 ) fcq 是接收状态集合； 5 ) 万是q 哼q 的状态转换函数，即艿( g ，x ) = q ，代表自动机在状态g 时，扫描字符z 后到达状态g 。 理论上有限状态自动机的状态转换函数的个数应该为i q i 宰i l 。因为对于q 中的每个状态，都应该定义扫描字母表上的每个字母的状态转换函数。 2 2 2 文法与自动机的对应 乔姆斯基得到了将形式语言与自动机联系起来得出了一个验证【2 】： 乔姆斯基4 型文法与4 种语言自动机是一一对应的关系。乔姆斯基根据转换 7 - 东北大硕士学位论文第2 章p e t r i 网与自动机 规则将文法分为4 类，每类文法的生成能力与相应的语言自动机的识别能力等 价，即4 种文法与4 种语言自动机对应。 表2 1 文法与自动机的对应 t a b l e2 1g r a m n l l t ra n da u t o m a t a 2 3 图与树 在完成自动机结构中时，经常要应用一些复杂的结构来完成与特定算法相互 符合的工作。应用较多的就是数据的组织结构的定义。 树和图是一种特殊的数据组织结构，利用这种结构可以很方便去构建一些高 级的算法。这些算法也正是实现自动机的基础。 2 3 1 图的定义 现实世界中，有许多现象可以抽象成图来表示。只有当这些现象抽象成图表 示以后，其表达和解决就变得清晰、直观。数学家欧拉解决著名的哥尼斯堡七桥 问题就是一个典型的代表。 直观地，图是由一些点和连接两点的边组成。例如，我们用点表示城市，如 果a 城市和b 城市之间的公路连接，则在表示a 城市的点和表示b 城市的点之 间用一条边连接起来。 定义：图的定义【4 1 设y 是一个非空的有穷集合，es v x v ，称g = 缈，e ) 为一个图。其中v 中 的元素称为顶点。矿称为顶点集；e 中的元素称为边，e 称为边的集合。这里定 义e v xv ，但对于v ( v ，v ：) e ，( v 。，v ：) 都被认为是连接顶点v 。和v ：的边，该 边没有方向。 定义：有向图 4 1 设v 是一个非空的有穷集合，e y y ，称g = 缈，e ) 为一个有向图。其中 v 中的元素称为顶点，v 称为顶点集；v “，1 ，：) e 称为从顶点y ，到顶点1 ，：的有 8 - 东北大硕士学位论文第2 章p e t r i 网与自动机 向边。顶点v 。称为前导，1 ，：称为后续。e 称为有向边的集合。 eg = 缈，e ) 是一个有向图。如果对于o i 七一1 1 ) ，均有“，v h ) e ， 则称，v l ，1 ，2 ，1 ，t 是有向图g 的一条长为k 的有向图。当v o = 1 ，i 时，v 0 ) v l ，v 2 ，v i 叫做一个有相回路或是有向圈。 2 3 2 树的定义 定义【4 】：设g = 缈，e ) 是一个有向图。当g 满足如下条件时，称g 为一棵树。： 1 ) 3 v v ，1 ，没有前导，1 ，且到树中其他顶点均有一条有向路，我们称此顶 点为g 的根。 2 ) 每个非根节点有且只有一个前导。 3 ) 每个顶点的后续按其拓扑关系从左向右排序。 通常在树中，我们可以称顶点为结点：顶点的前导为该结点的父节点，顶点 的后继为它的子节点。如果树中有一条从顶点1 ，。到顶点1 ，：处的路，则称1 ，是，：的 祖先，v ，是v ，的后代。无子节点的节点叫做叶子节点。非叶子顶点叫做中间结点。 树 l 图2 2 图与树的结构简图 f i g2 2g r a p ha n dt r e es t r u c t u r e 9 东北大学硕士学位论文 第3 章可达集与不变量 第3 章可达集与不变量 一般情况下，我们应该区分网与系统之间的区别。网的概念仅包括位置、变 迁和弧集合，而系统是指网和相关的初始标识。而初始标识是决定网系统的根本 因素之一，它赋予网系统以动态性。由此为起点，我们引入了可达集、不变量等 特性，它们能很方便的评价网系统的运行情况。 3 1p e t ri 网的可达集 构建网系统的可达集，以及建立在可达集之上的可达树或可达图是分析阿系 统的动态特性的主要手段之一。它反应了系统在整个运行过程中可能的状态，状 态的变化过程，以及最终所保持的状态。同时，网系统本身的其他性质如可逆性、 有界性、互斥性也有赖于通过可达集的结果来判断。 3 1 1 变迁的实施条件 定义3 1 可实施与实施【1 】 令= ，t ：f ，k ，w ，m 。) 是一个p t 系统： 1 ) 函数m ：s n 叫作的标识，当且仅当协s ：m g ) k g ) 。 2 ) 一个变迁t t 在下是可实施的，当且仅当： v s s ：g ，f ) m g ) k g ) 一w ( t ，s ) 3 ) 如果f t 在标识m 下的可实施的，那么r 可以实施并产生一个新的后续 标识 m ，m 可由下列方程给出：。 。 v s s ，m g ) = m g ) 一形g ，f ) + 肜o ，s ) 4 ) 系统标识m 经过t 的实施得到新的标识m ，可以表示成m t m 或者 ， m 啼m j 。 5 ) 4 r 吏用 m o 表示的最小标识集合满足： i m o 【m o ： i i 如果m l m o 且有f t 使m l p m 2 ，那么m 2 【m o 在一般情况下，【m 。 被称为的可达标识集。 定义3 2 实施序列【1 】 1 0 东北大学硕士学位论文第3 章可达集与不变量 令= ，t f ，k ，形，m 。) 是一个p t 系统，盯= m 。f 。m 。f 2 乙鸠是的一 个有限实施序列，当且仅当v f ，1 i 刀：m i - l i t ， m ，；d r 的长度h = 刀。f l t 2 f 疗 称为变迁实施序列。 3 1 2 可达树和可达图的构造 p t 系统的可达树构造算法如下： 1 ) 根结点，由m 。标注。 、 2 )一个标注m 的结点z 是一个叶结点心，当且仅当不存在f t ：f 在m 是 可实施的或者在从，到x 的路上存在一个结点y x ，但结点y 也是由m 标注的。 ” 3 )如果一个标注m 的结点x 不是一个叶结点，那么对于所有f t 使得在 m 下可实施的f 实施而产生一个新的结点y ，且在从x 到y 新产生的弧 上标注f 。y 结点标注的标识m 。可由m ：来计算，m ：满足于m p m i ， 即v s s ，m 沁) = m g ) 一形g ，f ) + 形( f ，s ) 。 m 的计算可区别为两种情 况： i 在从，到y 的路上，如果存在标注m ”的结点z y 且 v s s ：m ：g ) m 。g ) 。那么如果m ：g ) = m 。g ) ，, 贝t j m g ) = m 沁) ； 其他 i i 其他情况，m = m ： p t 系统的可达图构造算法如下： 令= ，r ：f ，k ，m 。) 是一个p t 系统的可达图，是由标识( 标记 值可能由w 表示) 为结点的图，其弧线由了元素标注。 可达图由下列算法构成： 1 ) 两个可达树的结点是等价的，当且仅当它们有相同的标注m 。 2 ) 可达图的结点是它的可达树结点的等价类。从结点y 到结点z 的弧线标注 为f ，当且仅当，砂y 且3 z z ，使得在可达树中从y 到z 有弧线t 。 3 1 3 构建分析可达集的自动机 通过可达集的算法定义，我们发现网系统的运行产生了一串可达集。如果我 们把每个变迁看作一个字符，那么网系统的运行就会产生一个特定的字符串集， 这就是这个网系统所产生的语言。因而，网系统的运行模式可以通过网系统的形 东北大学硕士学位论文第3 章可达集与不变量 式定义加以模拟。 例如：在图3 1 中，网系统的初始变迁是m 。= 0 , o ，0 ，0 ) ，网系统的模型可 以表示为：n = ，t ；f ) ，位置集合为p = 记，最，只，只) ，变迁集合为 t = 亿，疋，正，五 。 映射f 可以表示为一组发生式的结合，f = 以，厶，石，六) ，其中个元素具体 表示为： 石) 至m + - 1 ，1 ，0 ，o ； 似) 至m + - 1 ，0 ，1 ，l ； 六似) ：m + l ，一1 ，一1 ，0 ) ；厶( m f ：m + 0 ，0 ，0 ，一1 ； r 1 巾。 假设发生式 工， ，厂3 ，厂4 表示为对应的字母缸，b ，c ，d 。 p 】 图3 1p e t r i 嗍例图 f i g 3 1i n s t a n c eo f p e t dn e t 则有，从初始标识m 。= 1 ，o ，0 ，0 出发，位置置拥有标识。假设系统先发生变 迁疋，根据发生式有厶( 膨。) = 0 ，0 ，1 ，1 ) ，位置忍和只拥有标识。接着变迁五发生， 发生式为五似。) = 1 ，0 ，1 ，0 ) ，位置忍和只拥有标识。 这时网系统可以两条选择： 1 ) 继续刚才的发生路径五瓦，这样积累在只的标识将越来越多。同时系统 循环的按照发生序列疋瓦进行，产生了一个伍五) ”。 2 ) 如果位置只从新拥有标识时，系统选择变迁正发生。发生式的结果为 ( 膨：) = o ，1 ，1 ，o ) ，位置只和最拥有标识。b 和最又使瓦发生，系统表 又回到初始标识m o = 1 ，o ，0 ，0 ) ，这时的发生序列为互五。而且，这条路 径只执行了一次。 我们可以看到按照这样一个逻辑的网系统可达集可以用文法的形式表示为如 - 1 2 东北大学硕士学位论文第3 章可达集与不变量 f 几个表达式： 么专疋l 么b - - - 五五 即彳“b 肼或4 “ 伍l ) ”亿正) 肘或伍五y 而且在网系统的执行逻辑必须是： 1 ) 先执行-