下推自动机：
下推自动机 (PDA) 是具有附加堆栈存储的有限状态机。除了输入符号和当前状态之外，附加堆栈用于决定转换。
有限自动机：
有限自动机是任何机器的数学模型，我们可以通过它计算每个输入符号上的状态转换。有限自动机中的每个转换都取决于输入符号和当前转换状态。
让我们看看下推自动机和有限自动机的区别：
| 编号 | 下推自动机 | 有限自动机 |
|---|---|---|
| 1 | 对于Type-2语法，可以设计下推自动机。 | 对于 Type-3 语法，可以设计有限自动机。 |
| 2 | 非确定性下推自动机比确定性下推自动机更强大。 | 非确定性有限自动机具有与确定性有限自动机相同的能力。 |
| 3 | 不是每个非确定性下推自动机都转换成其等效的确定性下推自动机。 | 每个非确定性有限自动机都被转换为一个等价的确定性有限自动机 |
| 4 | 上下文无关语言可以被下推自动机识别。 | 正则语言可以被有限自动机识别。 |
| 5 | 下推自动机具有用于存储长字母序列的附加堆栈。 | 有限自动机没有任何空间来存储输入字母。 |
| 6 | 它通过上升到空堆栈和最终状态来接受输入字母。 | 它通过进入最终状态来接受输入字母。 |
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/264534.html