基本图灵机的Petri网建模研究

Vol.5,No.21,July2009,pp.5760-5762

ISSN1009-3044

E-mail:eduf@cccc.net.cn

第5卷第21期(2009年7月)http://www.dnzs.net.cnTel:+86-551-569096356909

基本图灵机的Petri网建模研究

赵东旭，乐晓波（长沙理工大学计算机与通信工程学院，湖南长沙410076）

摘要：该文采用Petri网这种系统描述和分析工具对基本图灵机进行了建模与分析。首先介绍了基本图灵机和Petri网的基本概念与定义，然后给出了一个利用Petri网对基本图灵机进行建模的有效算法，研究了用Petri网为基本图灵机建模的一般方法，说明了该方法的优越性，并最终以一个建模实例验证了该方法的有效性和可行性。关键词：Petri网；基本图灵机；形式语言；自动机中图分类号：TP301

文献标识码：A

文章编号：1009-3044(2009)21-5760-03

ResearchofPetrinetmodelofbasicTuringMachineZHAODong-xu,YUEXiao-bo

(CollegeofComputerandCommunicationEngineering,ChangshaUniversityofScienceandTechnology,Changsha410076,China)Abstract:Inthepaper,PetrinetatooltodescribeandanalyzesystemswasappliedtoconstructbasicTuringMachinemodelandmakeanalysistobasicTuringMachine.ConceptionanddefinitionofbasicTuringmachineandPetrinetwereintroducedfirstly.Thenaarith-meticofhowtoconstructPetriNetmodelofbasicTuringMachinewasgivenandthecommonmethodofconstructingbasicTuringma-chinebyPetrinetwasdiscussed.Inthefollowing,advantageofthismethodwasexplained.Feasibilityandvalidityofthismethodwereshowedbyanexampleintheendofthispaper.

Keywords:Petrinet;basicturingmachine;formallanguage;automaton

Petri网[1]是一种系统描述和分析的工具，在许多领域都得到了应用。目前，利用Petri网与形式语言与自动机[2]相结合进行研究已有一些研究基础。文献[3]通过Pumping引理的Petri网描述给出了Petri网语言属性的一组判定条件；文献[4-5]提出了拟行为有限状态机的有关概念，用Petri网为状态机建模；文献[6]利用Petri网为词法分析器建模。文献[7]研究了Petri网为语法分析器建模的方法。本文在图灵机理论的基础上，利用Petri网为图灵机建模，为基本图灵机的理论研究及其应用提供了一种行之有效的分析方

法。

1基本图灵机及Petri网

1.1基本图灵机

图灵机是一种抽象的计算模型。图灵机基本模型有一个有穷控制器，一条输入带和一个带头，输入带被分成许多单元，带头在每个时刻扫视带上的一个单元。该带有一个最左单元，向右则是无限的。带的每个单元正好可容纳有穷个带符号中的一个。开始时，最左边n个单元（n≥0，是一有穷数）放着取自带符集的一个字符串，其余无穷多单元放空白符。空白符是特殊带符号，但不是输入符号。在一个动作中，图灵机根据带头扫视的符号和有穷控制器的状态，执行如下操作：

①改变状态。

②在被扫视的带单元上打印一个符号，以代替原有的符号。③将带头向左或向右移动一个单元。

形式上，一个图灵机（TM）记成一个七元组：M＝（Q，Σ，Γ，δ，q0，B，F），其中：Q是状态的有穷集合；Σ是输入符号集；Γ是允许使用的带符号的有穷集合；δ是下一动作函数，它是从Q×Σ到Q×Σ×｛L，R｝的映射，δ对某些自变量可以没有定义；q0是初始状态，q0∈Q；B是空白符，B∈Γ；F是终结状态的集合。在每一时刻，机器所处状态，带子上已写符号的所有格子以及机器当前扫视的格子位置，统称为机器的格局。图灵机从初始格局出发，按程序一步步把初始格局改造为格局的序列。此过程可能无继续下去，也可能遇到指令表中没有列出的状态、符号组合或进入结束状态而停机。在结束状态下停机所达到的格局是最终格局，此最终格局就包含机器的计算结果。

1.2Petri网

Petri网是对离散并行系统的数学表示。Petri网的结构：1)Petri网的元素

a)库所（Place）：用圆形节点表示；

b)变迁（Transition）：用方形节点表示；

c)有向弧（Connection）：是库所和变迁之间的有向弧；

收稿日期：2009-04-17

基金项目：2008年度湖南省自然科学基金项目（08JJ3124）

作者简介：赵东旭（1983-），女，湖南怀化靖州人，长沙理工大学在读硕士生，研究方向：Petri网、人工神经网络；乐晓波（1957-），男，

陕西西安人，长沙理工大学教授，主要研究方向：Petri网、人工智能、并行算法。

5760人工智能及识别技术本栏目责任编辑：唐一东

第5卷第21期(2009年7月)

d)令牌（Token）：是库所中的动态对象，可以从一个库所移动到另一个库所。2)Petri网的规则

a)有向弧是有方向的；

b)两个库所或变迁之间不允许有弧；c)库所可以拥有任意数量的令牌；3)行为

如果一个变迁的每个输入库所（inputplace）都拥有令牌，该变迁即为被允许(enable)。一个变迁被允许时，变迁将发生(fire)，输入库所(inputplace)的令牌被消耗，同时为输出库所(outputplace)产生令牌。

a)变迁的发生是原子的。

b)有两个变迁都被允许的可能，但是一次只能发生一个变迁。

c)如果出现一个变迁，其输入库所的个数与输出库所的个数不相等，令牌的个数将发生变化。d)Petri网络是静态的。

e)Petri网的状态由令牌在库所的分布决定。4)Petri网流程建模

一个流程[8-9]的状态是由在场所中的令牌建模的，状态的变迁是由变迁建模的。令牌表示事物（人，货物，机器），信息，条件，或对象的状态；库所代表库所，通道或地理位置；变迁代表事件，转化或传输。一个流程有当前状态，可达状态，不可达状态。

1.3基本图灵机和Petri网的关系

图灵机的运行具有流动性和状态可确定性，符合用Petri网进行描述的条件。利用Petri网这一具有描述并发、异步、动态等事件能力的图形与数学工具来给基本图灵机建模，可充分展现基本图灵机的运行过程，使得对基本图灵机的认识和分析变得简便和明确。

2基本图灵机的Petri网建模

在这里，将给出利用Petri网为基本图灵机建模的算法。下面将首先根据基本图灵机给出相应Petri网的严格定义，然后再给出该算法的执行步骤。

定义四员组PNM={P,T,f,M0}当且仅当满足下列条件时称为基本图灵机M＝（Q，Σ，Γ，δ，q0，B，F）的Petri网：

1)P={q|埚q∈Q,(q,b,L)∨(q,b,R)∈δ,b∈Σ}+q0，P为描述图灵机状态的库所集,q0为描述基本图灵机运行前状态的库所。2)T={t（a）|埚t(a)∈δ,t(a)=δ(q,a)=(q,b,L)∨t(a)=δ(q,a)=(q,b,R),a,b∈Σ}，T为描述图灵机带头移动的变迁集。

3)f={(q1,v)，(v,q2)|埚δ(q1,a)=(q2,b,L)+δ(q1,a)=(q2,b,R),a,b∈Σ,q1,q2∈Q,∧(q1≠q2)}+{(q1,v)|埚δ(q1,a)=(q1,b,L)∨δ(q1,a)=(q1,b,R),a,b∈Σ,q1∈Q}，f表示库所与变迁之间的弧度集。一个括号代表一条弧，其中括号中的第一个元素指向弧尾，括号中的第二个元素指向弧头。

4)M0(q0)=1,P'=P-{q0};坌p∈P'，M0(p)=0;M0描述初始状态下各个库所中令牌的分布情况，若库所中无令牌则它的M0为0，有令牌则M0为1。根据基本图灵机的运行条件，初始化为基本图灵机运行前状态的库所有令牌，其他库所无令牌。

算法：

step1M0(q0)=1,P'=P-{q0};p∈P',M0(p)=0;f=Φ,P=Φ,T=Φ;

step2取t∈T,t=δ(q1,a)=(q2,b,L)∨t=δ(q1,a)=(q2,b,R)，T=T+{t},如果q1≠q2,P=P+{q1,q2}，f=f+{(q1,v)，(v,q2)}否则P=P+{q1},f=f+{(q1,v)}；

step3δ=δ-{t},如果δ=Φ算法结束，否则转step2。算法描述如图1所示。

3仿真实例

实例：设有上下文无关语言L={anbn|n>=1},一个图灵机M接受语言L。图灵机M=（Q，Σ，Γ，δ，q0，B，F），其中Q={q0，q1，q2，q3，q4}Γ={a，b}

Σ={a，b，I，J，B}

F={q4}

δ函数定义如下：

δ（q0，a）=（q1，I，R），δ（q2，a）=（q2，a，L）δ（q0，J）=（q3，J，R），δ（q2，I）=（q0，I，R）δ（q1，a）=（q1，a，R），δ（q2，J）=（q2，J，L）δ（q1，b）=（q2，J，L），δ（q3，J）=（q3，J，R）δ（q1，J）=（q1，J，R），δ（q3，B）=（q4，B，R）

实例中的图灵机按照算法利用visualobjectnet++2.0a这个Petri网仿真平台建模生成的PNM如图2所示。

图1基本图灵机Petri网建模流程图

4结束语

本文通过介绍基本图灵机及Petri网的基本理论，讨论了利用Petri网为基本图灵机建模的可行性，进一步研究了用Petri网对基本图灵机建模的一般方法，给出了基本图灵机Petri网建模的算法步骤，并通过一个例子说明了利用该方法为基本图灵机建模的有效性。关于其他图灵机的Petri网建模方法可在此方法的基础之上进行拓展得到。

本栏目责任编辑：唐一东人工智能及识别技术5761

ComputerKnowledgeandTechnology电脑知识与技术第5卷第21期(2009年7月)

参考文献：

[1]吴哲辉.Petri网导论[M].北京:机械工业出版社,2006.

[2]王柏.形式语言与自动机[M].北京：北京邮电大学出版社，2002.

[3]蒋昌俊，刘关俊.Petri网语言的Pumping引理[J].计算机学报,2006,29(02):274-278.

[4]姜春英，房立金，赵明扬.基于有限状态机与Petri网的系统分析与设计[J]，计算

机工程，2007，33(18):245-248.

[5]何建伟，姚淑珍.基于Petri网的状态机变迁的形式化方法研究[J]，系统仿真学

报，2007，19(A1):65-68.

[6]汪琳.基于Petri网的词法分析器的研究[J].长沙理工大学学报，2004,11(02):57-62.

[7]汪琳.基于Petri网建模的语法分析的研究[J].长沙交通学院学报，2004,09(06):

57-63.

[8]Bouabana-Tebibel,T.Belmesk,M.FormalizationofUMLObjectDynamicsand

Behavior[C].//2004IEEEInternationalConferenceonSystems,ManandCybernet-图2实例的PNM

ics,IEEE,2004.

[9]ZHAOYu,FANYu-shun,BAIXin-xin.TowardsFormalVerificationofUMLDiagramsbasedonGraphTransformation[C].//Proceed-ingsof2004IEEEInternationalConferenceonE-CommerceTechnologyforDynamicE-Business,IEEE,2004.

（上接第5756页）

movah，9；显示参数

；显示字符ASCII码加1incal

；字符颜色属性值加1incbl

；字符个数加1inccl

；调用显示中断int10h

；跳转到开头jmp100h

4结束语

虽然我们现在很少用到机器语言，但是了解机器语言必会大大加深对计算机原理的理解，对病毒、计算机安全等的认识也能提

高到一个新的层次。

参考文献：

[1][2][3][4][5][6][7][8]

沈美明,温冬禅.IBMPC汇编语言程序设计[M].北京:清华大学出版社,1998.王爽.汇编语言[M].2版.北京:清华大学出版社,2008.PetzoldC.编码的奥秘[M].北京:机械工业出版社,2000.叶平.电脑史话[M].北京:北京大学出版社,1999.

杜宜同.利用Debug命令浅析微机的工作原理[J].电脑知识与技术:技术论坛,2005(7).电脑报编辑部.电脑报1994年合订本(上册)[M].重庆:西南师范大学出版社,1995.尼亚克.我是沃兹[M].北京:北京师范大学出版社,2007.

刘云楚.CASL语言精解[M].北京:北京航空航天大学出版社,1999.

5762人工智能及识别技术本栏目责任编辑：唐一东