确定有限状态自动机

痛定思痛。 2022-03-18 11:44 409阅读 0赞

基础概念

### 定义 ###

确定有限状态自动机 ![/mathcal\{A\}][mathcal_A] 是由

*  一个非空有限状态的集合 Q
 *  一个输入字母表 Σ（非空有限字符的集合）
 *  一个转移函数（单值映射） ![/delta: Q /times /Sigma /rarr Q][delta_ Q _times _Sigma _rarr Q] （例如：![/delta /left( q,/sigma /right) = p, /left( p,q /in Q, /sigma /in /Sigma /right)][delta _left_ q_sigma _right_ _ p_ _left_ p_q _in Q_ _sigma _in _Sigma _right]）
 *  一个开始状态 ![s /in Q][s _in Q]
 *  一个接受状态（终结状态）的集合 ![F /sube Q][F _sube Q]

所组成的5-元组。因此一个DFA可以写成这样的形式：![/mathcal\{A\} = /left( Q,/Sigma,/delta,s,F /right)][mathcal_A_ _ _left_ Q_Sigma_delta_s_F _right] 。

### 非正式的语义 ###

确定有限状态自动机一个字符接一个字符的读入一个字符串 ![w /in /Sigma][w _in _Sigma] ，并根据给定的转移函数一步一步的转移至下一个状态。在读完该字符串后，如果该自动机停在一个属于F的接受状态，那么它就接受该字符串，反之则拒绝该字符串。

### 扩展转移函数 ###

为了能够对DFA的命题进行证明，需要一个数学上的正式的语义定义。

为此我们定义一个扩展的转移函数 ![/delta^\*: Q /times /Sigma^\* /rarr Q][delta_ Q _times _Sigma_ _rarr Q] 。

*  ![/delta^\* /left( q,w /right)][delta_ _left_ q_w _right] 是自动机从状态q顺序读入字符串w后达到的那个状态
 *  扩展转移函数递归的定义为：
    
     *  ![/delta^\* /left( q,/epsilon /right) = q][delta_ _left_ q_epsilon _right_ _ q]
     *  ![/delta^\* /left( q,u/sigma /right) = /delta(/delta^\*(q,u),/sigma), /forall u /in /Sigma^\*, /sigma /in /Sigma][delta_ _left_ q_u_sigma _right_ _ _delta_delta_q_u_sigma_ _forall u _in _Sigma_ _sigma _in _Sigma]

### 正式的语义 ###

对于一个确定有限状态自动机 ![/mathcal\{A\} = /left( Q,/Sigma,/delta,s,F /right)][mathcal_A_ _ _left_ Q_Sigma_delta_s_F _right] ，如果![/delta^\* /left( s,w /right) /in F][delta_ _left_ s_w _right_ _in F] ，我们就说该自动机接受字符串w，反之则表明该自动机拒绝字符串w。

被一个确定有限自动机接受的语言（或者叫“被识别的语言”）定义为：![/mathcal\{L\} ( /mathcal\{A\} ) = /\{ w /in /Sigma^\* | /mathcal\{A\}~][mathcal_L_ _ _mathcal_A_ _ _ _ w _in _Sigma_ _ _mathcal_A] 接受字符串![~w /\}][w]，也就是由所有被接受的字符串组成的集合。

### 利弊 ###

DFA 是最实际的计算模型，因为有平凡的线性时间、恒定空间的在线算法[模拟][Link 1]在输入流上的 DFA。给定两个 DFA 有有效算法找到识别它们所识别语言的并集、交集和补集 DFA。还有有效算法确定一个 DFA 是否接受任何字符串，一个 DFA 是否接受所有字符串，两个 DFA 是否识别同样的语言，和对特定正则语言找到有极小数目个状态的 DFA。

在另一方面，DFA 在可识别的语言上有严格的限制 — 很多简单的语言，包括需要多于恒定空间来解决的任何问题，不能被 DFA 识别。经典的 DFA 不能识别的简单语言的例子是括号语言，就是由正确配对的括号组成的语言，比如 (()())。由形如*anbn* 的字符串组成的语言，就是有限数目个 a，随后是相等数目个 b。可以证明没有 DFA 有足够状态来识别这种语言。

### 其它 ###

1.  能被确定有限状态自动机识别的语言是正则语言。
2.  确定有限状态自动机是非确定有限状态自动机的一种极限形式。
3.  确定有限状态自动机在计算能力上等价于非确定有限状态自动机。
4.  没有接受状态列表并没有指定开始状态的确定有限状态机叫做转移系统或半自动机。

## 例子 ##

下面是一个确定有限状态自动机的例子。

![350px-DFAexample.svg.png][]

![Image 1][]

![/mathcal\{A\}][mathcal_A] 的 状态图

确定有限状态自动机![/mathcal\{A\} = /left( Q,/Sigma,/delta,s,F /right)][mathcal_A_ _ _left_ Q_Sigma_delta_s_F _right]

*  *Q* = \{ *S*1,*S*2\}
 *  Σ = \{0,1\}
 *  *s* = *S*1
 *  *F* = \{ *S*1\}
 *  δ 由下面的状态转移表定义:

*  对应的转移函数为：
    
     *  δ(*S*1,0) = *S*2
     *  δ(*S*1,1) = *S*1
     *  δ(*S*2,0) = *S*1
     *  δ(*S*2,1) = *S*2

状态*S*1表示在输入的字符串中有偶数个0，而*S*2表示有奇数个0。在输入中1不改变自动机的状态。当读完输入的字符串的时候，状态将显示输入的字符串是否包含偶数个0。

![/mathcal\{A\}][mathcal_A]能识别的的语言是![/mathcal\{L\} ( /mathcal\{A\} ) = /\{ w | /\#\_0(w) /equiv 0~(mod~2) /\}][mathcal_L_ _ _mathcal_A_ _ _ _ w _ _0_w_ _equiv 0_mod_2_]。用正则表达式表示为：(1\* (01 \* 0) \* ) \* 。

## 封闭性及一些运算 ##

### 封闭性 ###

确定有限状态自动机的交，并，差，补，连接，替换，同态，逆同态等运算是封闭的，也就是说确定有限状态自动机通过这些运算产生的新的自动机也是确定有限状态自动机。

### 补运算 ###

![/mathcal\{A\}=(Q,/Sigma,/delta,s,F)][mathcal_A_Q_Sigma_delta_s_F] 是一个DFA，那么由补运算产生的新DFA定义为：![/bar/mathcal\{A\}=(Q,/Sigma,/delta,s,Q-F)][bar_mathcal_A_Q_Sigma_delta_s_Q-F] 。显然只要将 ![/mathcal\{A\}][mathcal_A] 中接受的状态设为不接受的状态，同时把不接受的状态设为接受的状态就得到![/bar/mathcal\{A\}][bar_mathcal_A] 。补运算的复杂度是：![O(/left| Q /right|)][O_left_ Q _right] 。

### 交运算和并运算 ###

有两个DFA，![/mathcal\{A\}\_1=(Q\_1,/Sigma,/delta\_1,s\_1,F\_1)][mathcal_A_1_Q_1_Sigma_delta_1_s_1_F_1] 和![/mathcal\{A\}\_2=(Q\_2,/Sigma,/delta\_2,s\_2,F\_2)][mathcal_A_2_Q_2_Sigma_delta_2_s_2_F_2] ，那么由这两个DFA创造出来的新的自动机定义为：![/mathcal\{B\}= (Q\_1 /times Q\_2,/Sigma,/delta\_/mathcal\{B\},(s\_1,s\_2),M)][mathcal_B_ _Q_1 _times Q_2_Sigma_delta_mathcal_B_s_1_s_2_M] 。其中![M /sube Q\_1 /times Q\_2][M _sube Q_1 _times Q_2] ，![/left( s\_1 , s\_2 /right)][left_ s_1 _ s_2 _right] 为![/mathcal\{B\}][mathcal_B] 的开始状态，![/delta\_/mathcal\{B\}][delta_mathcal_B] 为![/mathcal\{B\}][mathcal_B] 的转移函数，且作如下定义：![/forall q\_1 /in Q\_1,~q\_2 /in Q\_2,~/sigma /in /Sigma : /delta\_/mathcal\{B\}((q\_1,q\_2),/sigma) = (/delta\_1 (q\_1,/sigma),/delta\_2 (q\_2,/sigma) )][forall q_1 _in Q_1_q_2 _in Q_2_sigma _in _Sigma_ _delta_mathcal_B_q_1_q_2_sigma_ _ _delta_1 _q_1_sigma_delta_2 _q_2_sigma_]。

1.  当 ![M = F\_1 /times F\_2][M _ F_1 _times F_2] 时，由上述方法得到的![/mathcal\{B\}][mathcal_B] 就是DFA![/mathcal\{A\}\_1][mathcal_A_1] 和![/mathcal\{A\}\_2][mathcal_A_2] 的交运算，记作：![/mathcal\{B\} = /mathcal\{A\}\_1 /cap /mathcal\{A\}\_2][mathcal_B_ _ _mathcal_A_1 _cap _mathcal_A_2] 。也就是说对于读入的字符串w，当且仅当 ![/mathcal\{A\}\_1][mathcal_A_1] 和![/mathcal\{A\}\_2][mathcal_A_2] 同时接受w的时候![/mathcal\{B\}][mathcal_B] 接受w。
2.  当 ![M = Q\_1 /times F\_2 /bigcup F\_1 /times Q\_2][M _ Q_1 _times F_2 _bigcup F_1 _times Q_2] 时，由上述方法得到的![/mathcal\{B\}][mathcal_B] 就是DFA![/mathcal\{A\}\_1][mathcal_A_1] 和![/mathcal\{A\}\_2][mathcal_A_2] 的并运算，记作：![/mathcal\{B\} = /mathcal\{A\}\_1 /cup /mathcal\{A\}\_2][mathcal_B_ _ _mathcal_A_1 _cup _mathcal_A_2] 。也就是说对于读入的字符串w，只要 ![/mathcal\{A\}\_1][mathcal_A_1] 或![/mathcal\{A\}\_2][mathcal_A_2] 中至少有一个接受w，![/mathcal\{B\}][mathcal_B] 就接受w。

### 同态和逆同态运算 ###

一个同态函数 ![h: /Sigma^\* /rarr /Gamma^\*][h_ _Sigma_ _rarr _Gamma] 可以递归的定义为：

*  ![~h(/epsilon)=/epsilon][h_epsilon_epsilon]
 *  ![~h(u/sigma)=h(u)h(/sigma)][h_u_sigma_h_u_h_sigma]

于是则有 ![~h(uv)=h(u)h(v)][h_uv_h_u_h_v] 。（以上所述中![~/epsilon][epsilon] 为空字符，![~u,v /in /Sigma^\* , /sigma /in /Sigma][u_v _in _Sigma_ _ _sigma _in _Sigma]）

1.  ![/mathcal\{L\} /sube /Sigma^\* : h(/mathcal\{L\}) := /\{ h(w) ~| ~w /in /mathcal\{L\} /\}][mathcal_L_ _sube _Sigma_ h_mathcal_L_ _ h_w_ _ _w _in _mathcal_L_] ：对于接受语言L的DFA，只要将其中代表![~/delta(q,/sigma)][delta_q_sigma] 的边替换成一个序列![~h(/sigma)][h_sigma] 并在其中加入不属于原DFA状态的新状态，就产生了接受语言h(L)的DFA。
2.  ![/mathcal\{L\} /sube /Gamma^\* : h^\{-1\}(/mathcal\{L\}) := /\{ w ~| ~h(w) /in /mathcal\{L\} /\}][mathcal_L_ _sube _Gamma_ h_-1_mathcal_L_ _ w _ _h_w_ _in _mathcal_L_] ：定义一个![~Q,/Sigma,s,F][Q_Sigma_s_F] 都不变的新DFA，并定义新的转移函数为![~/delta'(q,/sigma) := /delta^\*(q,h(/sigma))][delta_q_sigma_ _delta_q_h_sigma] ，则![~(Q,/Sigma,/delta',s,F)][Q_Sigma_delta_s_F] 就是逆同态运算产生的新DFA。

此外替换运算和逆同态运算的方法近似。

**最小自动机**

### 等价类自动机 ###

对于一个正则语言，接受该语言的等价类自动机是一个![~(Q,/Sigma,/delta,s,F)][Q_Sigma_delta_s_F 1] 的5-元组。其定义如下：

*  Q是等价关系 ~L 的等价类的集合：![\[x\], x /in /Sigma^\*][x_ x _in _Sigma] 的集合
 *  ![~s=\[/epsilon\]][s_epsilon]
 *  ![F = /\{ \[x\] ~| ~x /in L /\}][F _ _ _x_ _ _x _in L]
 *  ![~/delta(\[x\],/sigma) = \[x/sigma\]][delta_x_sigma_ _ _x_sigma]

~L 被称为Nerode关系，是Myhill-Nerode定理的基础。简单的来说就是对于任意![~x,y,z /in /Sigma^\*][x_y_z _in _Sigma] ，如果![xz /in L /Leftrightarrow yz /in L][xz _in L _Leftrightarrow yz _in L] ，那么 x~Ly 。

### 唯一性 ###

对于任意给定的确定有限状态自动机都能找到一个与之计算能力等价的最小确定有限状态自动机，简称最小自动机。该最小自动机中状态的数量等于能识别相同语言的等价类自动机中等价关系的数量，我们可以称最小自动机和等价类自动机“实际上”是相等的，也就是同构。非正式的说法是：对于最小自动机上的任意状态都可以通过一个同构函数变换成等价类自动机上的一个状态。

能识别一个正则语言的等价类自动机是唯一的，因此能识别该语言的最小自动机也是唯一的。

### 算法 ###

定义一个非等价关系：![N := /\{(p,q) ~| ~p,q /in Q, /exists w /in /Sigma^\* : /delta^\*(p,w) /in F /leftrightarrow /delta^\*(q,w) /notin F /\}][N_ _p_q_ _ _p_q _in Q_ _exists w _in _Sigma_ _delta_p_w_ _in F _leftrightarrow _delta_q_w_ _notin F] ，如下步骤可以得到这个集合N：

1.  如果 ![p /in F, ~q /notin F][p _in F_ _q _notin F] ，就给所有的状态对(p,q)和(q,p)打上标记
2.  重复步骤3，直到所标记的状态对没有变化为止
3.  对于未标记的状态对(p,q)和σ，如果 ![~(/delta(p,/sigma),/delta(q,/sigma))][delta_p_sigma_delta_q_sigma] 被标记过了就把(p,q)也标记上
4.  以上所有标记了的状态对的集合就是非等价关系N

以下是由一个任意DFA转换到一个最小DFA的步骤：

1.  把所有不能从开始状态达到的状态删除
2.  通过上述标记算法计算非等价关系N
3.  一步一步将不属于N的状态对中的两个状态合成一个状态

这样就得到了接受相同语言的最小自动机。复杂度为 ![O(/left| Q /right| ^2 /left| /Sigma /right|)][O_left_ Q _right_ _2 _left_ _Sigma _right] 。

## 参见 ##

*  无环确定有限状态自动机
 *  非确定有限状态自动机
 *  图灵机
 *  读只右移图灵机

再分享一下我老师大神的人工智能教程吧。零基础！通俗易懂！风趣幽默！还带黄段子！希望你也加入到我们人工智能的队伍中来！[https://blog.csdn.net/jiangjunshow][https_blog.csdn.net_jiangjunshow]

[mathcal_A]: /images/20220318/9e370edc251740a28d9f6969c2fbb14f.png
[delta_ Q _times _Sigma _rarr Q]: http://upload.wikimedia.org/math/5/0/9/509af98ac38e7825bc55ba8382925792.png
[delta _left_ q_sigma _right_ _ p_ _left_ p_q _in Q_ _sigma _in _Sigma _right]: /images/20220318/1d3c508a5e384950afe1c5e8f1a88cf8.png
[s _in Q]: /images/20220318/36e17ebbf6a44a32bd8ab1042fe74d61.png
[F _sube Q]: /images/20220318/13d38df1a4ea4fb58b297859eaa043a6.png
[mathcal_A_ _ _left_ Q_Sigma_delta_s_F _right]: /images/20220318/2cc2ca18f7e440b8a12c97d8cda21a17.png
[w _in _Sigma]: /images/20220318/9dd7c2b096a547eb9b03963f36a6e266.png
[delta_ Q _times _Sigma_ _rarr Q]: /images/20220318/073ec0c5dae64a46b1ef725f7e703255.png
[delta_ _left_ q_w _right]: /images/20220318/2af61997db2a4f6880518703e72b5eba.png
[delta_ _left_ q_epsilon _right_ _ q]: /images/20220318/0b5c8600cdef4c1b97f7626d448a8ac4.png
[delta_ _left_ q_u_sigma _right_ _ _delta_delta_q_u_sigma_ _forall u _in _Sigma_ _sigma _in _Sigma]: /images/20220318/dbaa3474a6cc4f84af83152d70371a4c.png
[delta_ _left_ s_w _right_ _in F]: /images/20220318/e10e83e089664182808c30cd05ea87c3.png
[mathcal_L_ _ _mathcal_A_ _ _ _ w _in _Sigma_ _ _mathcal_A]: http://upload.wikimedia.org/math/0/6/6/066c9d9ee07c6964909f0d972459bad1.png
[w]: /images/20220318/c3f3d62891ff40e3b3e01b2411310758.png
[Link 1]: https://www.baidu.com/s?wd=%E6%A8%A1%E6%8B%9F&tn=24004469_oem_dg
[350px-DFAexample.svg.png]: /images/20220318/959e16c10f8f4ec786abeb728eb0ff9c.png
[Image 1]: 
[mathcal_L_ _ _mathcal_A_ _ _ _ w _ _0_w_ _equiv 0_mod_2_]: /images/20220318/bf6d6a2fbb564f4ba5db46f65255e6b4.png
[mathcal_A_Q_Sigma_delta_s_F]: http://upload.wikimedia.org/math/d/9/e/d9e9dcc3aa0ed8abffd191d8ac12ee53.png
[bar_mathcal_A_Q_Sigma_delta_s_Q-F]: http://upload.wikimedia.org/math/a/9/3/a9316a999fa6919a2dc32a38ab41d4b4.png
[bar_mathcal_A]: http://upload.wikimedia.org/math/8/9/7/89710f2dc6ee7995bf5533faaa7e1108.png
[O_left_ Q _right]: /images/20220318/7534afff4a1748379f6594627d089ee3.png
[mathcal_A_1_Q_1_Sigma_delta_1_s_1_F_1]: http://upload.wikimedia.org/math/a/2/2/a22fb6891def3d8d921dbb35953394a2.png
[mathcal_A_2_Q_2_Sigma_delta_2_s_2_F_2]: http://upload.wikimedia.org/math/1/d/b/1db06b4ce6490176ae61268850025b54.png
[mathcal_B_ _Q_1 _times Q_2_Sigma_delta_mathcal_B_s_1_s_2_M]: http://upload.wikimedia.org/math/2/6/d/26d5d81205e2f52aa02c183f3d1badc9.png
[M _sube Q_1 _times Q_2]: http://upload.wikimedia.org/math/d/7/a/d7aa29132aed79627825910cfd852050.png
[left_ s_1 _ s_2 _right]: http://upload.wikimedia.org/math/a/c/a/acaa5e044437797fd6b26bc30f041dc0.png
[mathcal_B]: /images/20220318/d1f3f79a45a5490db6a98971ce76a11d.png
[delta_mathcal_B]: http://upload.wikimedia.org/math/b/7/e/b7e3a8a17d007aa6a377cfd477fa78fd.png
[forall q_1 _in Q_1_q_2 _in Q_2_sigma _in _Sigma_ _delta_mathcal_B_q_1_q_2_sigma_ _ _delta_1 _q_1_sigma_delta_2 _q_2_sigma_]: /images/20220318/7c56bdcb207049e49048f6c399cd5d6c.png
[M _ F_1 _times F_2]: http://upload.wikimedia.org/math/b/d/9/bd9ee706933c56f000a6b1e48a37772c.png
[mathcal_A_1]: http://upload.wikimedia.org/math/6/0/3/603c752ca2fec9ceb0c488ccc04e39d7.png
[mathcal_A_2]: http://upload.wikimedia.org/math/4/2/3/4230ccc4d82cf96eabd35414a2a95233.png
[mathcal_B_ _ _mathcal_A_1 _cap _mathcal_A_2]: http://upload.wikimedia.org/math/3/d/6/3d61f962231559b00c8f4e482f46e982.png
[M _ Q_1 _times F_2 _bigcup F_1 _times Q_2]: http://upload.wikimedia.org/math/4/0/4/404f97e34c61287c8cc8e45ffdefea28.png
[mathcal_B_ _ _mathcal_A_1 _cup _mathcal_A_2]: http://upload.wikimedia.org/math/e/5/6/e563c0bd18eca6bcc1ac4f8027ed4258.png
[O_left_ Q_1 _right_ _left_ Q_2 _right_ _left_ _Sigma _right]: /images/20220318/5ed5d70f93a84eafb33d8ea55aaa0b67.png
[h_ _Sigma_ _rarr _Gamma]: /images/20220318/36f20044e5cc48bfb963c4d6e0913d72.png
[h_epsilon_epsilon]: /images/20220318/6893dea49f8f40cf9e83a5cde49df69a.png
[h_u_sigma_h_u_h_sigma]: /images/20220318/d80dea41fc334a96985d5c497d1ff8b6.png
[h_uv_h_u_h_v]: http://upload.wikimedia.org/math/4/4/d/44d0c973fd5e5868e0205710b712563b.png
[epsilon]: http://upload.wikimedia.org/math/a/a/a/aaa992c1313ba067044c7fb9f0a26e23.png
[u_v _in _Sigma_ _ _sigma _in _Sigma]: /images/20220318/7a42bfc5e937494dac1794d6199e4ac0.png
[mathcal_L_ _sube _Sigma_ h_mathcal_L_ _ h_w_ _ _w _in _mathcal_L_]: http://upload.wikimedia.org/math/c/5/d/c5dafcf5f8770456797dae7196ebd5ad.png
[delta_q_sigma]: http://upload.wikimedia.org/math/1/c/5/1c51343edd82ed7fd07207177aa1ae6d.png
[h_sigma]: /images/20220318/5ae0e0cc985f4c4693867ff4095203b9.png
[mathcal_L_ _sube _Gamma_ h_-1_mathcal_L_ _ w _ _h_w_ _in _mathcal_L_]: http://upload.wikimedia.org/math/4/0/5/405164f3c34b8d6c5bf08759a32828e3.png
[Q_Sigma_s_F]: http://upload.wikimedia.org/math/2/b/b/2bb690af83ad8fd2e4d9de58fe1cf0a2.png
[delta_q_sigma_ _delta_q_h_sigma]: http://upload.wikimedia.org/math/f/c/b/fcb1031fa958e52c85979bade14a14c5.png
[Q_Sigma_delta_s_F]: /images/20220318/58625735f3eb4455b1a317932ba795e3.png
[Q_Sigma_delta_s_F 1]: /images/20220318/cfed65a3fa274810953355accedc19d9.png
[x_ x _in _Sigma]: /images/20220318/4a9507adb9a04ab181dfbde20532418d.png
[s_epsilon]: /images/20220318/d3434cb5406b47f19c2fce7649efc01b.png
[F _ _ _x_ _ _x _in L]: /images/20220318/3b4ef9b6782946af8a91a7c522721feb.png
[delta_x_sigma_ _ _x_sigma]: /images/20220318/e179d604fc5743e59e278c56e8e64516.png
[x_y_z _in _Sigma]: http://upload.wikimedia.org/math/5/8/d/58dd41bacbd406179a330b2f12a8ce3e.png
[xz _in L _Leftrightarrow yz _in L]: /images/20220318/9b61c004c7a54ce09cea02970f43bab1.png
[N_ _p_q_ _ _p_q _in Q_ _exists w _in _Sigma_ _delta_p_w_ _in F _leftrightarrow _delta_q_w_ _notin F]: /images/20220318/481c3b2f2e92448fb8f23deac760c17c.png
[p _in F_ _q _notin F]: /images/20220318/ea3180bf2ca943e9a6a5b04b692c9324.png
[delta_p_sigma_delta_q_sigma]: /images/20220318/4e9a6518563d44ada5a877ab4a2f4ee0.png
[O_left_ Q _right_ _2 _left_ _Sigma _right]: /images/20220318/8e38decf58a34170a894b70922ac6ed3.png
[https_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485