什么是理论计算机科学（TOC）中的下推自动机？

一个下推自动机 (PDA) 是一种以类似于为正则语法设计确定性有限自动机 (DFA) 的方式实现上下文无关文法 (CFG) 的方法。

DFA 可以记住有限量的信息，但 PDA 可以记住无限量的信息。

基本上，PDA 如下所示：

"有限状态机 + 堆栈"

PDA 有三个组成部分，如下所示：

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

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

PDA 可以正式描述为 7 元组

(Q, ∑,S, δ,q0,I,F)

• Q 是有限数量的状态。
• ∑ 是输入字母表。
• S 是堆栈符号。
• δ 是转换函数：QX(∑U{e})XSXQ
• q0 是初始状态 (q0 属于 Q)。
• I 是初始状态顶部符号。
• F 是一个接受状态集 (F 属于 Q)。

该图显示了 PDA 从状态 q1 到状态 q2 的转换，标记为 a,b->c

在状态 q1，如果遇到输入字符串 'a' 并且堆栈的顶部符号为 'b'，那么我们将弹出 'b'，将 'c' 推入堆栈顶部，并移动到状态 q2。

Bhanu Priya

更新于： 2023-10-07

30K+ 次浏览

启动您的职业生涯

通过完成课程获得认证

开始