摘要
参照有限状态自动机图形表示方式的思想方法,研究了标准下推自动机的图形表示——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.
出处
《计算机科学》
CSCD
北大核心
2006年第3期271-274,共4页
Computer Science
关键词
状态转换图
标准下推自动机
化简
行为等价
状态等价
State transition diagram, Normal form of pushdown automata, Simplification, Behavior equivalence, State equivalence