Question

确定的有穷自动机和不确定的有穷自动机有什么区别

编译原理中 确定的有穷自动机和不确定的有穷自动机有什么区别？

Answer 1

一、转换状态不同

1、确定的有穷自动机：当一个状态面对一个输入符号的时候，所转换到的是一个唯一确定的状态。

2、不确定的有穷自动机：当一个状态面对一个输入符号的时候，它所转换到的可能不只一个状态，可以是一个状态集合。

二、特点不同

1、确定的有穷自动机：系统具有一系列离散的输入输出信息和有穷数目的内部状态。

2、不确定的有穷自动机：允许在每一步上读头的内部状态可在几个状态中任取，即 δ 之值为内部状态之集合。

三、映射不同

1、确定的有穷自动机：将S×Σ映射到S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态。

2、不确定的有穷自动机：将S×Σ映射到2S的转换函数。s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合。

参考资料来源：百度百科-不确定型有穷自动机

参考资料来源：百度百科-确定型有穷自动机

Answer 2

　　确定的有穷自动机就是说当一个状态面对一个输入符号的时候，它所转换到的是一个唯一确定的状态；
　　而不确定的有穷自动机是说当一个状态面对一个输入符号的时候，它所转换到的可能不只一个状态，可以是一个状态集合。
　　这就是两者的主要区别。
　　还有就是DFA的开始状态是唯一的，而NFA的开始状态是一个开始状态集。

Answer 3

确定的有穷自动机就是说当一个状态面对一个输入符号的时候，它所转换到的是一个唯一确定的状态；而不确定的有穷自动机是说当一个状态面对一个输入符号的时候，它所转换到的可能不只一个状态，可以是一个状态集合。这就是两者的主要区别。还有就是DFA的开始状态是唯一的，而NFA的开始状态是一个开始状态集。