先决条件—— 设计有限自动机 ，前一篇文章： 设计确定性有限自动机（集合1） 在本文中，我们将看到确定性有限自动机（DFA）的一些设计。
问题1： 为{a，b}上的字符串集构造一个DFA，使得字符串的长度| w |可被2整除，即| w | mod 2=0。
解释—— 所需的语言如下：
L = {?, aa, ab, ba, bb, aaaa, bbbb, ............}
该语言的状态转换图如下所示：
![图片[1]-设计确定性有限自动机（集合2）-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_TOC3.png)
这里，状态A表示长度为偶数（0，2，4，…）的所有字符串的集合，状态B表示长度为奇数（1，3，5，…）的所有字符串的集合。
Number of states: n If |W| mod n = 0
def stateA(n): if ( len (n) = = 0 ): print ( "Accepted" ) else : #on any input call function stateB if (n[ 0 ] = = '0' or n[ 0 ] = = '1' ): stateB(n[ 1 :]) def stateB(n): if ( len (n) = = 0 ): print ( "Not Accepted" ) else : #on any input call function stateA if (n[ 0 ] = = '0' or n[ 0 ] = = '1' ): stateA(n[ 1 :]) #take input n = input () #call stateA #to check the input stateA(n) |
上述自动机将接受所有长度可被2整除的字符串。当字符串的长度为1时，它将从状态A变为状态B。当字符串的长度为2时，它将从状态B变为状态A，依此类推。状态A是最终状态，即它接受长度可被2整除的所有字符串。
问题2： 为{a，b}上的字符串集构造一个DFA，使得字符串| w |的长度不可被2整除，即| w | mod 2=1。
解释—— 所需的语言如下：
L = {a, b, aaa, aab, aba, abb, aaaaa, bbbb, .......}
该语言的状态转换图如下所示：
![图片[2]-设计确定性有限自动机（集合2）-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_TOC4-1.png)
这里，状态A表示长度为偶数（0，2，4，…）的所有字符串的集合，状态B表示长度为奇数（1，3，5，…）的所有字符串的集合。
def stateA(n): if ( len (n) = = 0 ): print ( "Not Accepted" ) else : #on any input call function stateB if (n[ 0 ] = = '0' or n[ 0 ] = = '1' ): stateB(n[ 1 :]) def stateB(n): if ( len (n) = = 0 ): print ( "Accepted" ) else : #on any input call function stateA if (n[ 0 ] = = '0' or n[ 0 ] = = '1' ): stateA(n[ 1 :]) #take input n = input () #call stateA #to check the input stateA(n) |
上述自动机将接受所有长度不能被2整除的字符串。当字符串的长度为1时，它将从状态A变为状态B。当字符串的长度为2时，它将从状态B变为状态A，依此类推。状态B是最终状态，即它接受长度不可被2整除的所有字符串。
问题3： 为{a，b}上的字符串集构造一个DFA，使得字符串的长度| w |可被3整除，即| w | mod 3=0。
解释—— 所需的语言如下：
L = {?, aaa, aab, aba, abb, aaaaaa, bbbbbb, .......}
该语言的状态转换图如下所示：
![图片[3]-设计确定性有限自动机（集合2）-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_TOC5.png)
这里，状态A表示字符串长度除以3后余数为零（0）的集合，状态B表示字符串长度除以3后余数为一（1）的集合，状态C表示字符串长度除以3后余数为二（2）的集合。
Number of states: n If |W| mod n = 0
def stateA(n): if ( len (n) = = 0 ): print ( "Accepted" ) else : #on any input call function stateB if (n[ 0 ] = = '0' or n[ 0 ] = = '1' ): stateB(n[ 1 :]) def stateB(n): if ( len (n) = = 0 ): print ( "Not Accepted" ) else : #on any input call function stateC if (n[ 0 ] = = '0' or n[ 0 ] = = '1' ): stateC(n[ 1 :]) def stateC(n): if ( len (n) = = 0 ): print ( "Not Accepted" ) else : #on any input call function stateA if (n[ 0 ] = = '0' or n[ 0 ] = = '1' ): stateA(n[ 1 :]) #take input n = input () #call stateA #to check the input stateA(n) |
上述自动机将接受所有长度可被3整除的字符串。当字符串的长度为1时，它将从状态A变为状态B。当字符串的长度为2时，它将从状态B变为状态C。当字符串的长度为3时，它将从状态C变为状态A（最终状态）。状态A是最终状态，即它接受长度可被3整除的所有字符串。
问题4： 为{a，b}上的字符串集构造一个DFA，使得字符串| w |的长度不可被3整除，即| w | mod 3=1。
解释—— 所需的语言如下：
L = {a, b, aa, ab, ba, bb, aaaa, bbbb, ........}
该语言的状态转换图如下所示：
![图片[4]-设计确定性有限自动机（集合2）-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_TOC6.png)
这里，状态A表示字符串长度除以3后余数为零（0）的集合，状态B表示字符串长度除以3后余数为一（1）的集合，状态C表示字符串长度除以3后余数为二（2）的集合。
def stateA(n): if ( len (n) = = 0 ): print ( "Not Accepted" ) else : #on any input call function stateB if (n[ 0 ] = = '0' or n[ 0 ] = = '1' ): stateB(n[ 1 :]) def stateB(n): if ( len (n) = = 0 ): print ( "Accepted" ) else : #on any input call function stateC if (n[ 0 ] = = '0' or n[ 0 ] = = '1' ): stateC(n[ 1 :]) def stateC(n): if ( len (n) = = 0 ): print ( "Not Accepted" ) else : #on any input call function stateA if (n[ 0 ] = = '0' or n[ 0 ] = = '1' ): stateA(n[ 1 :]) #take input n = input () #call stateA #to check the input stateA(n) |
上述自动机将接受所有长度不能被3整除的字符串。当字符串的长度为1时，它将从状态A变为状态B。当字符串的长度为2时，它将从状态B变为状态C。当字符串的长度为3时，它将从状态C变为状态A。状态B和C是最终状态，即它接受所有长度不可被3整除的字符串。
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
