词法分析——有限状态自动机（FA）

举个例子

词法分析——有限状态自动机（FA）
在上图中，

$\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就可以被接受。

再举个例子

词法分析——有限状态自动机（FA）
转移函数：
$\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的实现

词法分析——有限状态自动机（FA）
DFA其实是一个有向图，我们在这里用邻接矩阵对其进行了表示，并且终结符一般画上圈

词法分析——有限状态自动机（FA）

举个例子

再举个例子

NFA 和 DFA 的小结

DFA的实现

相关推荐