MENU

词法分析——有限状态自动机(FA)

October 11, 2018 • Read: 160 • 编译原理

举个例子


在上图中,

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

Archives Tip
QR Code for this page
Tipping QR Code