dpda子类之等价性判定问题

§一.定义及简介定义1.1 设M为dpda,若M只有一个状态,则M为S_0-机,S_0-机由空堆栈所接受的语言称为S_0-语言。S_0-机M若没有∈-rule则称之为S-机,相应的有S-语言。定义1.2 一个dpda M=(Q,∑,Γ,δ,q_0,Z_0,F),若Q=Q_0∪Q_1∪……∪Q_m;Q_i∩Q_j=φi≠j;且对q,q′∈Q,δ(q,α,A)=(q′,α)α∈∑∪{∈},α∈Γ