什么是下推自动机(pushdown automata)？

下推自动机本质上是一种有限自动机，具有称为堆栈的辅助数据结构（额外内存），这有助于下推自动机识别上下文无关语言。下推自动机用于机器可计算的理论。它们比有限状态机能力更强，但比图灵机能力更低。

下推自动机有三个组件：

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

堆栈由有限的符号列表组成。符号可以添加到列表中或从列表中删除，但只能在列表的一端。可以添加和删除项目的列表的末尾称为堆栈的顶部。列表通常被视为符号的垂直“堆栈”，在顶部添加和删除项目。

在堆栈顶部添加符号称为将一个符号推到堆栈上，删除符号称为从堆栈中弹出一项。在其计算的每个步骤中，下推自动机能够在其堆栈上执行若干推送和弹出操作（除了可能从自动机正在处理的输入字符串中读取asymbol之外）。

下推自动机可分为以下类型：

• 确定性下推自动机
• 不确定下推自动机

确定性下推自动机可以识别所有确定性上下文无关语言，而非确定性下推自动机可以识别全部上下文无关语言。

关于下推自动机，您需要了解什么

• 下推自动机（PDA）是一种采用堆栈的自动机。
• 它具有用于存储长字母序列的附加堆栈。
• 可以为类型2语法构造下推自动机。
• 通过到达：空堆栈和最终状态接受输入字母表。
• 非确定性下推自动机（NDPA）比确定性下推自动机（DPDA）具有更大的性能。
• 可以为上下文无关语法构造下推自动机。
• 并非每个非确定性下推自动机都被转换为其等价的确定性下推自动机。

什么是有限自动机(finite automata)？

有限自动机（FA）是一种简单的理想化机器，用于识别从某些字符集（或字母表）获取的输入中的模式。有限自动机的主要功能是接受或拒绝输入，这取决于FAA定义的模式是否出现在输入中。它有一组用于从一个状态移动到另一个状态的状态和规则，但取决于应用的输入符号。基本上，它是数字计算机的抽象模型。

有限自动机由以下部分组成：

• 有限状态集
• 输入符号集
• 初始状态
• 最终状态集
• 过渡函数

有限自动机有两种类型：

• 确定性有限自动机（DFA）
• 非确定性有限自动机（NFA）

关于下推自动机，您需要了解什么

• 有限自动机（FA）是一种简单的理想化机器，用于识别来自某个字符集的输入中的模式。
• 它没有存储输入字母长序列的能力或空间。
• 可以为类型3语法构造有限自动机。
• 通过达到“最终状态”接受输入字母表。
• 非确定性有限自动机（NFA）具有和确定性有限自动仪（DFA）相同的能力。
• 可以为正则语言构造有限自动机。
• 每一个非确定性有限自动机都被转化为一个等价的确定性有限自动机。

下推自动机(pushdown automata)和有限自动机(finite automata)的区别