栈结构的增广Petri网模型

摘要

增广Petri网(如抑止弧Petri网)的模拟能力相当于图灵机,堆栈是一种常见的数据结构,运用增广Petri网的强大模拟能力,通过用一个变迁序列表示入栈字符串,另一个变迁序列表示出栈字符串,可以建立堆栈结构的模型SEPN。利用SEPN模型和映射函数,给出了产生几种上下文无关语言的有限长子集的增广Petri网模型,这几种语言是不能由一般的Petri网产生的。