下推自动机

下推自动机(Pushdown Automaton, PDA)是一种带有栈存储器组件的有限自动机；

它比有限自动机更强大，因为栈提供了无限存储能力；

构造PDA可识别一类CFL，CFG和PDA对CFL的表达上是等价的；二者可以互相转化；

形式定义

一个PDA可由六元组定义

其中：

  • 有限状态集: 全体状态构成的集合
  • 输入字母表: 所有可能的输入字母；
  • 栈字母表: 所有可能进栈的输入字母；
  • 转移函数
  • 初始状态: 状态机的初始状态；
  • 终态集: 为状态机最终接受的状态；

工作原理

  1. PDA假设从初始状态开始，开始符为, 栈底符，输入指针指向输入串的第一个符号；
  2. 任意时刻，假设下推栈的栈顶符号,当前的输入符号为，PDA可以：
    • 读取输入符号
    • 查看栈顶符号
    • 改变状态
    • 修改栈（压入或弹出符号）

转移函数

称自动机接受单词流 若存在状态序列和字符串序列,满足

接受一个单词流意味着序列中每个状态转移都是合法的；

转移函数的形式为：

对于一个自动机内部的合法的状态转移(transition)，可被描述为根据当前状态读取(read)输入后，决定弹出(pop)栈的元素，并选择进栈(push-in)的元素，进入下一个状态的过程，简记为a,b->t;

  • 当前状态
  • 输入符号a（可以是）
  • 栈顶符号b
  • 新状态
  • 要压入栈的符号串c

PDA有两种接受方式：

  1. 终态接受：当输入串读完且PDA处于终态时接受
  2. 空栈接受：当输入串读完且栈为空时接受

确定性PDA

如果PDA的转移函数满足：

  1. 对于每个状态、输入符号和栈顶符号，最多有一个转移
  2. 对于每个状态和栈顶符号，如果有转移，则不能有其他转移

则称该PDA为确定性的(DPDA)。

示例

识别语言的PDA：

  1. 状态集：
  2. 输入字母表：
  3. 栈字母表：
  4. 初始状态：
  5. 初始栈符号：
  6. 终态集：

转移函数：