自动机PDA验收

Pushdown自动机可以使用以下两种方法来接受一种语言:
1.按最终状态接受:如果PDA在读取整个输入后以零次或多次移动进入任何最终状态,则称PDA通过最终状态接受其输入。
令P =(Q,∑,Γ,δ,q0,Z,F)为PDA。最终状态可接受的语言可以定义为:

L(PDA) = {w | (q0, w, Z) ?* (p, ε, ε), q ∈ F}

2.通过空堆栈接受:从某些PDA的初始配置读取输入字符串时,PDA堆栈将变空。
令P =(Q,∑,Γ,δ,q0,Z,F)为PDA。空堆栈可接受的语言可以定义为:
N(PDA) = {w | (q0, w, Z) ?* (p, ε, ε), q ∈ Q}

最终状态和空堆栈的接受程度相等
  • 如果对于某些PDA P1,L = N(P1),则存在PDA P2,使得L = L(P2)。这意味着空堆栈PDA接受的语言也将被最终状态PDA接受。
  • 如果某些PDA P1的语言为L = L(P1),则存在PDA P2,使得L = N(P2)。这意味着最终状态PDA接受的语言也可以被空堆栈PDA接受。
例:
构造一个PDA,该PDA通过空堆栈接受{0,1}上的语言L,该堆栈接受所有0和1的字符串,其中0的数目是1的数目的两倍。
解:
设计此PDA分为两部分:
  • 如果1在任何0之前
  • 如果0在任何1之前。
【自动机PDA验收】我们将设计第一部分,即1出现在0之前。逻辑是读取单个1并将两个1压入堆栈。此后在读取两个0时,从堆栈中弹出两个1。 δ可以是
δ(q0, 1, Z) = (q0, 11, Z)Here Z represents that stack is empty δ(q0, 0, 1) = (q0, ε)

现在,考虑第二部分,即0是否在1之前。逻辑是先读取0,然后将其压入堆栈,然后将状态从q0更改为q1。 [请注意,状态q1表示已读取第一个0,而仍未读取第二个0]。
在q1中,如果遇到1,则POP0。在q1中,如果读取0,则只需读取第二个0,然后继续。 δ将是:
δ(q0, 0, Z) = (q1, 0Z) δ(q1, 0, 0) = (q1, 0) δ(q1, 0, Z) = (q0, ε)(indicate that one 0 and one 1 is already read, so simply read the second 0) δ(q1, 1, 0) = (q1, ε)

现在,总结给定L的完整PDA为:
δ(q0, 1, Z) = (q0, 11Z) δ(q0, 0, 1) = (q1, ε) δ(q0, 0, Z) = (q1, 0Z) δ(q1, 0, 0) = (q1, 0) δ(q1, 0, Z) = (q0, ε) δ(q0, ε, Z) = (q0, ε)ACCEPT state

    推荐阅读