下推自动机简介

PDA的基本结构

下推自动机是一种实现上下文无关语法的方法，与我们为常规语法设计 DFA 的方式类似。DFA 可以记住有限量的信息，但 PDA 可以记住无限量的信息。

基本上，下推自动机是 -

“有限状态机”+“堆栈”

下推自动机具有三个组成部分 -

  • 输入磁带，
  • 控制单元，以及
  • 无限大小的堆栈。

栈头扫描栈顶符号。

堆栈执行两个操作 -

  • 推- 在顶部添加一个新符号。

  • Pop - 顶部符号被读取并删除。

PDA 可能会也可能不会读取输入符号，但它必须在每次转换中读取堆栈的顶部。

掌上电脑

PDA 可以正式描述为 7 元组 (Q, Σ, S, δ, q 0 , I, F) -

  • Q是有限的状态数

  • Σ是输入字母表

  • S是堆栈符号

  • δ是过渡函数：Q × (Σ ∪ {ε}) × S × Q × S*

  • q 0是初始状态 (q 0 ∈ Q)

  • I是初始栈顶符号 (I ∈ S)

  • F是接受状态的集合 (F ∈ Q)

下图显示了 PDA 从状态 q 1到状态 q 2的转换，标记为 a,b → c -

PDA 中的过渡

这意味着在状态q 1，如果我们遇到输入字符串'a'并且堆栈顶部符号是'b'，那么我们弹出'b'，将'c'压入堆栈顶部并移动到状态q 2。

与 PDA 相关的术语

瞬时描述

PDA 的瞬时描述 (ID) 由三元组 (q, w, s) 表示，其中

  • q是状态

  • w是未消耗的输入

  • s是堆栈内容

十字转门符号

“十字转门”符号用于连接表示 PDA 的一次或多次移动的 ID 对。转换过程由十字转门符号“⊢”表示。

考虑一个 PDA (Q, Σ, S, δ, q 0 , I, F)。转换可以通过以下十字转门符号在数学上表示 -

(p, aw, Tβ) ⊢ (q, w, αb)

这意味着在从状态p转换到状态q时，输入符号'a'被消耗，并且堆栈顶部'T'被新字符串'α'替换。

注意- 如果我们想要 PDA 移动零次或多次，我们必须使用符号 (⊢*)。