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