dfa与ndfa_DFA和NDFA之间的区别| 目录

﹏ヽ暗。殇╰゛Y 2023-03-05 09:57 33阅读 0赞

dfa与ndfa

DFA stands for Deterministic Finite Automata and NDFA stands for Non-Deterministic Finite Automata.

DFA代表确定性有限自动机，而NDFA代表非确定性有限自动机。

**Read more:** [Deterministic Finite Automata (DFA)][Deterministic Finite Automata _DFA]

**阅读更多：** [确定性有限自动机(DFA)][Deterministic Finite Automata _DFA]

## DFA和NDFA之间的区别 **(**Difference between DFA and NDFA**)** ##

<table> 
 <tbody> 
  <tr> 
   <th>DFA</th> 
   <th>NDFA</th> 
  </tr> 
  <tr> 
   <td>It stands for deterministic finite automata.</td> 
   <td>It stands for non-deterministic finite automata.</td> 
  </tr> 
  <tr> 
   <td>The transition takes place from a state to a single particular state for each input symbol.</td> 
   <td>For each input symbol, the transition can be to multiple next states.</td> 
  </tr> 
  <tr> 
   <td>There are no empty string transitions in DFA.</td> 
   <td>Empty string transitions are also permitted.</td> 
  </tr> 
  <tr> 
   <td>Backtracking is allowed in DFA.</td> 
   <td>In NDFA, it is not always possible to backtrack.</td> 
  </tr> 
  <tr> 
   <td>DFA requires more space.</td> 
   <td>NDFA requires less space.</td> 
  </tr> 
  <tr> 
   <td>There no such randomness as the transition can be determined in DFA.</td> 
   <td>There is much more randomness as the transition from one state to other cannot be determined in this.</td> 
  </tr> 
  <tr> 
   <td><b>Ex: δ: Q × ∑ → Q</b></td> 
   <td><b>Ex: δ: Q × ∑ → 2<sup>Q</sup></b></td> 
  </tr> 
  <tr> 
   <td> 
    <div style="text-align: center;"> 
     <img src="http://imgconvert.csdnimg.cn/aHR0cHM6Ly93d3cuaW5jbHVkZWhlbHAuY29tL3RvYy9pbWFnZXMvZGZhLTEuanBn?x-oss-process=image/format,png" alt="TOC  | DFA" style="outline: none;"> 
    </div></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <th> DFA </th> 
   <th> 国家发改委 </th> 
  </tr> 
  <tr> 
   <td> 它代表确定性有限自动机。 </td> 
   <td> 它代表非确定性有限自动机。 </td> 
  </tr> 
  <tr> 
   <td> 对于每个输入符号，从状态转换到单个特定状态。 </td> 
   <td> 对于每个输入符号，过渡可以是多个下一个状态。 </td> 
  </tr> 
  <tr> 
   <td> DFA中没有空字符串过渡。 </td> 
   <td> 也允许空字符串过渡。 </td> 
  </tr> 
  <tr> 
   <td> DFA中允许回溯。 </td> 
   <td> 在NDFA中，并非总是可以回溯。 </td> 
  </tr> 
  <tr> 
   <td> DFA需要更多空间。 </td> 
   <td> NDFA需要更少的空间。 </td> 
  </tr> 
  <tr> 
   <td> 没有这种随机性，因为可以在DFA中确定过渡。 </td> 
   <td> 由于不能确定从一种状态到另一种状态的转变，因此存在更多的随机性。 </td> 
  </tr> 
  <tr> 
   <td> <b>例：δ：Q×∑→Q</b> </td> 
   <td> <b>例：δ：Q×∑→2 <sup>Q</sup></b> </td> 
  </tr> 
  <tr> 
   <td> 
    <div style="text-align: center;"> 
     <img src="http://imgconvert.csdnimg.cn/aHR0cHM6Ly93d3cuaW5jbHVkZWhlbHAuY29tL3RvYy9pbWFnZXMvZGZhLTEuanBn?x-oss-process=image/format,png" alt="目录| DFA" style="outline: none;"> 
    </div></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

> 翻译自: [https://www.includehelp.com/toc/DFA-vs-NDFA.aspx][https_www.includehelp.com_toc_DFA-vs-NDFA.aspx]

dfa与ndfa

[Deterministic Finite Automata _DFA]: https://www.includehelp.com/toc/deterministic-finite-automata-dfa.aspx
[https_www.includehelp.com_toc_DFA-vs-NDFA.aspx]: https://www.includehelp.com/toc/DFA-vs-NDFA.aspx