下推自动机的状态转换图与下推自动机的化简  

State Transition Diagram of Pushdown Automata and Simplification of Pushdown Automata

作　　者：张继军[1] 吴哲辉[2] 

机构地区：[1]山东农业大学信息学院,泰安271018 [2]山东科技大学信息学院,青岛266510

出　　处：《计算机科学》2006年第3期271-274,共4页Computer Science

摘　　要：参照有限状态自动机图形表示方式的思想方法,研究了标准下推自动机的图形表示——PAD 状态转换图,证明了下推自动机与标准下推自动机的等价性。给出了对标准下推自动机进行化简的原则,并给出了化简算法,实现了下推自动机的化简。According to the method of finite automation diagram description, the diagram description of normal form of pushdown automata, the PAD state transition diagram is discussed. It is proofed that pushdown automat is equipollence with normal form of pushdown automata. The rules that normal form of pushdown automata is simplified and the algorithm of simplification are given. The simplification of pushdown automata is implemented.

关 键 词：状态转换图 标准下推自动机 化简 行为等价 状态等价 

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