举个例子展开目录
在上图中,
$\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 其实是一个有向图,我们在这里用邻接矩阵对其进行了表示,并且终结符一般画上圈