下推自动机

<aside>

Untitled

</aside>

今天考试，我今天才第一次编辑这个notion page[doge]

<aside>

有限状态自动机 FA 识别正则语言 RG

→ 无法记录串的具体数目A→wB，尽管无穷语言

下推自动机 PDA 识别 上下文无关语言 CFG

→ 记录左右两个串之间的对应关系 A→wAb, 进而通过A的层级记录了wb之间的相互关系对数→ 无穷容量的栈 PDA

</aside>

Push-Down Automation

• 停机

  1. 串扫描结束
  2. 缺失出入栈规则

  • 可接受串

    如果扫描结束，栈为空，就接受

• 形式化描述

  • 栈

    栈底$Z_0$ + 指令/规则

    $$ <x,D,V> $$

    x 扫描串当前字符

    D 栈顶符号

    V 替代符号串

  • 入栈扩展

    $$ <x,D,A_1A_2\cdots> $$

    逆序压入，A1为栈顶

  • 接受栈底

    $$ <\epsilon,Z_0,\epsilon> $$

  • 状态转移 =》 多态PDA

    $$ <q,x,D,q^\prime,V> $$

    当前状态q，因为读入x且栈顶为D，转化为状态q’ 并弹出D压入V

    通过增加状态规避空串

    <aside>

    用Z代表任意的栈顶符号

    </aside>

  • 不确定

    $$ <q,\epsilon,D,q^\prime,V> $$

    状态q随时可以转化，不依赖于输入x，提供一个路径到达期望状态

$$ M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F) $$

Q 状态集合 Sigma 字母表，Gamma 栈内符号集合

delta规则

$q_0 \in Q$开始状态，Z0栈底符号，$F\in Q$接受状态

$$ L(M)=\{w\mid (q_0,w,Z_0)=>^*(q,\epsilon , \epsilon),q\in Q\} $$

将串转化为空船和空栈，PDA以空栈方式接受

$$ F(M)=\{w\mid (q_0,w,Z_0)=>^(q^\prime \in F,\epsilon,\sigma\in\Gamma^)\} $$

将串扫描结束后，PDA处于终态，不关心栈内是否有剩余

• 两者等价

• 广义PDA

  $$ \delta :Q\times(\Sigma \cup\{\epsilon\})\times\red{\Gamma^+}\to Q\times \Gamma^* $$

  广义PDA 的栈顶可以为多个符号（从Gamma 到Gamma的正闭包）