举个例子
在上图中，
$\Sigma$表示自动机可以识别的所有的不同的字符的集合。$\Sigma = \{a,b\}$
S 是状态集，在这里只有三种状态，所以 S = {0, 1, 2}
$q_0$是初始状态，我们一般约定只有一个单向箭头的边指向的节点是起始状态。$q_0 = \{0\}$
F 是终结状态，或者说是接收状态，在图中表示为双圈。 F = {2}
$$ \lbrace (q_0, a) -> q_1, (q_0, b) -> q_0, (q_1, a) -> q_2, (q_1, b) -> q_1, (q_2, a) -> q_2, (q_2, b) -> q_2 \rbrace $$
是所有的映射构成的一个集合。
那么什么样的串可以被接受？接受的意思就是处于起始状态，给定一个输入串S，根据转移函数δ进行状态转移，最后到达了F终结状态，这样的串S就可以被接受。
再举个例子
转移函数：
$$ \lbrace (q_0, a) -> \lbrace q_0, q_1\rbrace, $$
$$ (q_0, b) -> \lbrace q_1\rbrace, $$
$$ (q_1, b) -> \lbrace q_0, q_1\rbrace \rbrace $$
对于某一种状态，当输入一个字符后，转移到下一个状态不能确定。如上式中的第一个和第三个集合，我们称这样的状态机是非确定状态自动机（NFA）。如果转移函数所有的结果都是确定的，是单集合元素，就像第一个例子一样，这样的状态机就是确实有限状态自动机（DFA）。
NFA 和 DFA 在接受的时候有很大的差别
如该例中，$q_0$状态在a状态后可以得到$q_0$或$q_1$两种状态，如果是$q_0$那就不能进入终结状态F，不能被接受，而选择$q_1$时就可以进入终结状态。所以我们对NFA定义，只要在多种走法中最终有一种走法可以被接受就是可以被接受。所以该例可以被接受。
一般对于这种是否可以接受的判断，我们常常会先将 NFA 转化为 DFA 再进行判断
NFA 和 DFA 的小结
确定状态有限自动机 DFA
- 对任意的字符，最多有一个状态可以转移
非确定的有限状态自动机 NFA
- 对任意的字符，有多余一个状态可以转移
DFA的实现
DFA其实是一个有向图，我们在这里用邻接矩阵对其进行了表示，并且终结符一般画上圈
