跳转至

Pushdown Automata(堆栈自动机，PDA)

定义

PDA=NFA+stack

Definition

PDA 可以被以下6个变量表示，\(P=(K,\sum,\Gamma,\Delta,s,F)\)

  • \(\Gamma\):stack alphabet
  • \(\Delta\): \((K\times (\sum\cup\{e\})\times \Gamma^*)\times(K\times \Gamma^*)\)
    • 第一个\(K\)：current state
    • \(\sum\cup\{e\}\)：读取的字符（可为空）
    • \(\Gamma^*\): 从栈中pop out一个string
    • 第二个\(K\): next state
    • \(\Gamma^*\)：push string进栈

Example

((p,a,123),(q,45))代表在p状态读入a，且栈顶为123的时候（1在顶），pop 123，状态转移到b，push 45。

  • \(\sum\): alphabet
  • F: final state
  • s: initial state
  • K: state sets （后面四个与NFA相同含义）

由于PDA多了一个栈结构，描述PDA的一个状态要用一个三元组\((p,x,\alpha)\)，分别表示（当前状态，剩余字符串，当前栈状态） 类似，移动过程也被写作

\((p,x\alpha)\vdash_p (q,y,\beta)\) (\(\vdash_p^*\)概念也和前文相同)

而一个PDA 接受一个字符串当且仅当移动的最终状态为

\((q,e,e),q\in F\) (这里要求栈为空，状态为最终状态)

我们称被PDA \(P\) 接受的language为\(L(P)\)

Danger

PDA的automata部分为NFA，无法用DFA代替

PDA与CFG转换

CFG to PDA

对于一个CFG:\((V,\sum,S,R)\)，如何找到对应的P:\((K,\sum,\Gamma,\Delta,s,F)\)使得P能accept的language：

CFG to PDA

转换方式如下：

  • \(K=\{s,f\}\)
  • \(F=\{f\}\)
  • \(\Gamma = V\)
  • \(\Delta =\{\)
    • \(((s,e,e),(f,S))\)
    • \(((s,e,e),(f,S))\ for\ each (A,u)\in R\)

    • \(((s,a,a),(f,e))\ for\ each A\in \sum\)

      \(\}\)

把CFG放到栈里面，总有一种方法能生成一个完整的CFL字符串，然后和外面匹配成功，进入final state且栈为空，（注意此处是每次中间符号在栈顶的时候进行代换，由于此为非确定图灵机，我们可以相信其总会代换出正确的一条路）

PDA to CFG

直接转换较为复杂，我们需要有种方法，从PDA转化成simple PDA,简单PDA的定义如下：

Definition

如果一个P:\((K,\sum,\Gamma,\Delta,s,F)\)，满足以下所有条件则其为简单PDA：

  • \(|F|=1\)
  • 对所有转换\(((p,a,\alpha),(q,\beta))\in \Delta\) 满足一下两个条件之一：
    • \(\alpha = e\ \And\ |\beta|=1\) (Push 一个字符)
    • \(|\alpha|= i\ \And\ \beta = e\) (Pop 一个字符)

那怎么进行这种转换呢？方法如下：

PDA to simple PDA

  • if \(|F|\ge 1\)
    • 创造一个新的final state f
    • 将所有最终状态跳转到到它那，即新增\(((q,e,e),(f,e))\ for\ q\in F\)
  • if \(|\alpha|\geq 1\ and\ |\beta|\geq 1\) (既pop又push)
    • 创造中间状态r
    • 删去\(((p,a,\alpha),(q,\beta))\)
    • 添加\(((p,a,\alpha),(r,e)),((r,e,e),(q,\beta))\)
  • if \(|\alpha|\gt 1\ and\ \beta=e\qquad \alpha=c_1c_2...c_k\)
    • 创造状态\(r_1r_2....r_{k-1}\)
    • 删去\(((p,a,x),(q,e))\)
    • 变为\(((p,a,c_1),(r_1,e)),((r_1,e,c_2),(r_2,e)),...,((r_{k-1},e,c_k),(q,e))\) 一个一个push慢慢push进去
  • if \(|\beta|\gt 1\ and\ \alpha=e\qquad \beta=c_1c_2...c_k\)
    • 和上一点方法雷同，所以不重复
  • if \(\beta=e\ \And\ \alpha=1\)
    • 创造新状态r,选一个字符\(b\in\Gamma\)
    • 添加 \(((p,a,e),(r,b)),((r,e,b),(q,e))\),先push再pop

然后就要从simple PDA 变换到CFG，方法如下：

simple PDA to CFG

设P为\((K,\sum,\Gamma,\Delta,s,\{f\})\)，构造\(G:(V,\sum,S,R)\)

对\(\forall p,q\in K\) 构造 \(A_{pq}\) 为中间符号

使得\(A_{pq}\Rightarrow^*\omega\) 当且仅当 \(\omega\in\{u\in\sum^*:(p,u,e)\vdash^*(q,e,e)\}\)

即从(p，空栈)出发，读进字符串u之后，会去到(q，空栈)。

对于该公式我们可以得到两条推论（由于考试不会考这类的构造，所以我们只要知道推论就好了。），即对于从（p，空栈）出发到（q，空栈）的过程，大致可以分为两种情况：

  • 在中间某个状态r时候变成空栈，则此时\(A_{pq}\)可分解为\(A_{pr}A_{rq}\)
  • 在中间没有空栈的情况时，所以p状态push进去的字符a，必然为q状态前最后一个pop的字符（最底端的字符），所以在这种情况下，有如下式子：
    • \(\forall p,q\in K\qquad \forall((p,a,e),(p',\alpha)),((q',b,\alpha),(q,e))\in \Delta\)，则，\(A_{pq}\)可分解为\(aA_{p'q'}b\)