确定有限状态自动机(deterministic finite automaton)DFA

google找了一点资料，做个记录。

维基百科定义：在计算理论中，确定有限状态自动机或确定有限自动机（英语：deterministic finite automaton, DFA）是一个能实现状态转移的自动机。对于一个给定的属于该自动机的状态和一个属于该自动机字母表{\displaystyle \Sigma }Σ的字符，它都能根据事先给定的转移函数转移到下一个状态（这个状态可以是先前那个状态，比如我用自动机实现认单词，如单词boost，o出来之后还可以是o，也就是可以回到原来的state）。

定义

确定有限状态自动机

是由

• 一个非空有限的状态集合

  

• 一个输入字母表

  

  （非空有限的字符集合）
• 一个转移函数

  

  （例如：

  

  ）
• 一个开始状态

  

• 一个接受状态的集合

  

所组成的5-元组。因此一个DFA可以写成这样的形式：

。

举个例子：图片来自google