形式语言与自动机之语言识别机器——下推自动机

下推自动机的物理模型

• 下推自动机(pushdown automaton，PDA)

  M= (Q，∑，Γ，δ，q0，Z0，F)

  Q——状态的非空有穷集合。"q∈Q，q称为M的一个状态(state)；

  ∑——输入字母表(input alphabet)。要求M的输入字符串都是∑上的字符串；

  Γ——栈符号表(stack alphabet)。"A∈Γ，叫做一个栈符号；

  • Z0——Z0∈Γ叫做开始符号(start symbol)，是M启动时候栈内惟一的一个符号。所以，习惯地称其为栈底符号；
  • q0——q0∈Q，是M的开始状态(initial state)，也可叫做初始状态或者启动状态；
  • F——FíQ，是M的终止状态(final state)集合，简称为终态集。"q∈F，q称为M的终止状态，也可称为接受状态(accept state)，简称为终态。
  • δ——状态转移函数(transition function)，有时候又叫做状态转换函数或者移动函数。

    那如何来设计PDA呢，我们来看一个例子：

    • 例1：接受语言L={w2wT| w∈{0,1}*}的PDA的设计。
    • 先设计产生L的CFG G1：

      G1：S?2|0S0|1S1

      • 再将此文法转化成GNF：

        G2：S?2|0SA|1SB

        A?0

        B?1

        • 句子0102010的最左派生和我们希望相应的PDA M的动作。

        • 派生

          M应该完成的动作

          ST0SA

          从q0启动，读入0，将S弹出栈，将SA压入栈，状态不变

          T01SBA

          在状态q0，读入1，将S弹出栈，将SB压入栈，状态不变

          T010SABA

          在状态q0，读入0，将S弹出栈，将SA压入栈，状态不变

          T0102ABA

          在状态q0，读入2，将S弹出栈，将ε压入栈，状态不变

          T01020BA

          在状态q0，读入0，将A弹出栈，将ε压入栈，状态不变

          T010201A

          在状态q0，读入1，将B弹出栈，将ε压入栈，状态不变

          T0102010

          在状态q0，读入0，将A弹出栈，将ε压入栈，状态不变

          M1=({q0}，{0，1，2}，{S，A，B}，δ1，q0，S，Φ)。其中：

          δ1(q0，0，S)={(q0，SA)}

          δ1(q0，1，S)={(q0，SB)}

          δ1(q0，2，S)={(q0，ε)}

          δ1(q0，0，A)={(q0，ε)}

          δ1(q0，1，B)={(q0，ε)}

          此时有：N(M1)=L。

          M2=({q0,q1},{0,1,2},{S,A,B,Z0},δ2,q0,Z0,{q1})

          δ2(q0，0，Z0)={(q0，SAZ0)}

          δ2(q0，1，Z0)={(q0，SBZ0)}

          δ2(q0，2，Z0)={(q1，ε)}

          δ2(q0，0，S)={(q0，SA)}

          δ2(q0，1，S)={(q0，SB)}

          δ2(q0，2，S)={(q0，ε)}

          δ2(q0，0，A)={(q0，ε)}

          δ2(q0，1，B)={(q0，ε)}

          δ2(q0，ε，Z0)={(q1，ε)}

          此时有：N(M2)=L(M2)=L。

          M2=({q0,q1},{0,1,2},{S,A,B,Z0},δ2,q0,Z0,{q1})

          δ2(q0，0，Z0)={(q0，SAZ0)}

          δ2(q0，1，Z0)={(q0，SBZ0)}

          δ2(q0，2，Z0)={(q1，ε)}

          δ2(q0，0，S)={(q0，SA)}

          δ2(q0，1，S)={(q0，SB)}

          δ2(q0，2，S)={(q0，ε)}

          δ2(q0，0，A)={(q0，ε)}

          δ2(q0，1，B)={(q0，ε)}

          δ2(q0，ε，Z0)={(q1，ε)}

          此时有：N(M2)=L(M2)=L。