计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (12): 50-52.DOI: 10.3778/j.issn.1002-8331.2010.12.013

• 研究、探讨 • 上一篇    下一篇

正规语言闭包运算的Petri网构造方法

苏 平1,2,束德勤2,范 昊2   

  1. 1.山东大学 计算机科学与技术学院,济南 250100
    2.山东农业大学 信息科学与技术学院,山东 泰安 271018
  • 收稿日期:2009-11-02 修回日期:2010-02-08 出版日期:2010-04-21 发布日期:2010-04-21
  • 通讯作者: 苏 平

Kleene-closure operation constructing method about regular language with Petri net

SU Ping1,2,SHU De-qin2,FAN Hao2   

  1. 1.School of Computer Science and Technology,Shandong University,Jinan 250100,China
    2.College of Information Science and Engineering,Shandong Agricultural University,Tai’an,Shandong 271018,China
  • Received:2009-11-02 Revised:2010-02-08 Online:2010-04-21 Published:2010-04-21
  • Contact: SU Ping

摘要: Petri网语言与Chomsky文法体系之间的关系已有了一些结论,已经证明正规语言是Petri网语言的一个子类。相关文献中给出了一种Petri网子类——恰当终结的标准Petri网,并且已经证明恰当终结的标准Petri网语言与正规语言的等价性。在此基础上,研究了正规表达式中Kleene闭包运算“*”的Petri网构造方法,分别给出了Kleene闭包运算“*”的ε-空标注和无ε-空标注Petri网模型的构造方法。该构造方法可由产生正规语言L的网模型直接得到产生正规语言L*的网模型。证明了对于恰当终结的标准Petri网,正规语言闭包运算“*”的构造是封闭的。

Abstract: Some brilliant conclusions have been made about the relations between Petri net languages and Chomsky grammar system.Standard properly end Petri net,a kind of subclass of Petri nets is defined.This subclass of Petri nets’ language is equal to regular language.Based on this kind of Petri net,constructing methods of kleene closure operations with and without an empty label in regular expressions are presented respectively.It is also proved that a standard properly end Petri net language of Kleene closure operations is close.

中图分类号: