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

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

作　　者：苏平[1,2] 束德勤[2] 范昊[2] 

机构地区：[1]山东大学计算机科学与技术学院,济南250100 [2]山东农业大学信息科学与技术学院,山东泰安271018

出　　处：《计算机工程与应用》2010年第12期50-52,59,共4页Computer Engineering and Applications

基　　金：国家自然科学基金重大研究计划No.90718011;国家自然科学基金No.60673053~~

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

关 键 词：PETRI网 正规语言 闭包运算 Petri网构造方法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]