锐客网

  1. 首页 > 睿知 > it技术 > >

自动机PDA验收

自动机教程自动机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

    推荐阅读


    上一篇：自动机Greibach范式（GNF）

    下一篇：自动机CFG到PDA的转换