设计确定性有限自动机（集合1）-yiteyi-C++库

先决条件—— 设计有限自动机在本文中，我们将看到确定性有限自动机（DFA）的一些设计。

null

问题1： 为{a，b}上的字符串集构造DFA，使得字符串的长度| w |=2，即字符串的长度正好为2。

解释—— 所需的语言如下：

L = {aa, ab, ba, bb}

该语言的状态转换图如下所示：

图片[1]-设计确定性有限自动机（集合1）-yiteyi-C++库

在这里状态A表示长度为零（0）的所有字符串的集合，状态B表示长度为一（1）的所有字符串的集合，状态C表示长度为二（2）的所有字符串的集合。状态C是最终状态，D是死状态，这是因为在获得任何字母表作为输入后，它永远不会进入最终状态。

Number of states: n+2
Where n is |w|=n

上述自动机将接受长度正好为2的所有字符串。当字符串长度为1时，它将从状态A变为状态B。当字符串长度为2时，它将从状态B变为状态C。当字符串长度大于2时，它将从状态C变为状态D（死状态），然后从状态D变为状态D。

                     #check string in                   
                     #in state A                   
                     def                               checkStateA(n):                   
                             
                                         #if length of                   
                                         #string is one                   
                                         #print not accepted                   
                                         if                               (                               len                               (n)                               =                               =                               1                               ):                   
                                         print                               (                               "string not accepted"                               )                   
                                         else                               :                   
                                         #pass string to stateB to                   
                                         #to check further transitions                   
                                         if                               (n[                               0                               ]                               =                               =                               'a'                               or                               n[                               0                               ]                               =                               =                               'b'                               ):                   
                                         stateB(n[                               1                               :])                   
                             
                             
                     def                               stateB(n):                   
                                         #here if length                   
                                         #is not 1 print#string not accepted                   
                                         if                               (                               len                               (n)!                               =                               1                               ):                   
                                         print                               (                               "string not accepted"                               )                   
                                         else                               :                   
                                         #else pass string                   
                                         #to state c                   
                                         stateC(n[                               1                               :])                   
                     def                               stateC(n):                   
                                         #here if length                   
                                         #becomes zero                   
                                         #print accepted                   
                                         #else not accepted                   
                                         if                               (                               len                               (n)                               =                               =                               0                               ):                   
                                         print                               (                               "string accepted"                               )                   
                                         else                               :                   
                                         print                               (                               "string not accepted"                               )                   
                             
                             
                     #take input                   
                     n                               =                               input                               ()                   
                     checkStateA(n)                   

问题2： 为{a，b}上的字符串集构造DFA，使字符串的长度|w |>=2，即字符串的长度至少应为2。

解释—— 所需的语言如下：

L = {aa, ab, ba, bb, aaa, aab, aba, abb........}

该语言的状态转换图如下所示：

图片[2]-设计确定性有限自动机（集合1）-yiteyi-C++库

在这里状态A表示长度为零（0）的所有支柱的集合，状态B表示长度为一（1）的所有支柱的集合，状态C表示长度为二（2）的所有支柱的集合。

Number of states: n+1
Where n is |w|>=n

上述自动机将接受长度至少为2的所有字符串。当字符串的长度为1时，它将从状态A变为状态B。当字符串的长度为2时，它将从状态B变为状态C。最后，当字符串的长度大于2时，它将从状态C变为状态C。

                     #check string in                   
                     #in state A                   
                     def                               checkStateA(n):                   
                             
                                         #if length of                   
                                         #string is one                   
                                         #print not accepted                   
                                         if                               (                               len                               (n)                               =                               =                               1                               ):                   
                                         print                               (                               "string not accepted"                               )                   
                                         else                               :                   
                                         #pass string to stateB to                   
                                         #to check further transitions                   
                                         if                               (n[                               0                               ]                               =                               =                               'a'                               or                               n[                               0                               ]                               =                               =                               'b'                               ):                   
                                         stateB(n[                               1                               :])                   
                             
                             
                     def                               stateB(n):                   
                             
                                         #here if length                   
                                         #is less than 1                   
                                         #printstring not accepted                   
                                         if                               (                               len                               (n)<                               1                               ):                   
                                         print                               (                               "string not accepted"                               )                   
                                         else                               :                   
                             
                                         #else pass string                   
                                         #to state c                   
                                         stateC(n[                               1                               :])                   
                             
                             
                     def                               stateC(n):                   
                                         #here if length of string                   
                                         #is greater than equal to zero                   
                                         #print accepted                   
                                         #else not accepted                   
                                         if                               (                               len                               (n)>                               =                               0                               ):                   
                                         print                               (                               "string accepted"                               )                   
                                         else                               :                   
                                         print                               (                               "string not accepted"                               )                   
                             
                             
                     #take input                   
                     n                               =                               input                               ()                   
                     checkStateA(n)                   

问题3： 为{a，b}上的字符串集构造DFA，使得字符串的长度|w |<=2，即字符串的长度为atmost 2。

解释—— 所需的语言如下：

L = {?, aa, ab, ba, bb}

该语言的状态转换图如下所示：

图片[3]-设计确定性有限自动机（集合1）-yiteyi-C++库

在这里状态A表示长度为零（0）的所有sting的集合，状态B表示长度为一（1）的所有sting的集合，状态C表示长度为二（2）的所有sting的集合，状态A、B、C是最终状态，D是死状态，因为在获得任何字母作为输入后，它永远不会进入最终状态。

Number of states: n+2
Where n is |w|<=n

上述自动机将接受所有长度不超过2的字符串。当字符串的长度为1时，它将从状态A变为状态B。当字符串的长度为2时，它将从状态B变为状态C。最后，当字符串的长度大于2时，它将从状态C变为状态D（死状态）。

                     #check string in                   
                     #in state A                   
                     def                               checkStateA(n):                   
                             
                                         #if only two transition occurs                   
                                         #then print string accepted                   
                             
                                         if                               (n[                               0                               ]                               =                               =                               'a'                               or                               n[                               0                               ]                               =                               =                               'b'                               ):                   
                                         stateB(n[                               1                               :])                   
                             
                             
                     def                               stateB(n):                   
                             
                                         #if length is 0                   
                                         #print accepted                   
                                         if                               (                               len                               (n)                               =                               =                               0                               ):                   
                                         print                               (                               "string accepted"                               )                   
                                         else                               :                   
                                         stateC(n[                               1                               :])                   
                             
                             
                     def                               stateC(n):                   
                                         #if length is 0                   
                                         #print accepted                   
                                         #else not accepted                   
                                         if                               (                               len                               (n)                               =                               =                               0                               ):                   
                                         print                               (                               "string sccepted"                               )                   
                                         else                               :                   
                                         print                               (                               "string not accepted"                               )                   
                             
                             
                     #take input                   
                     n                               =                               input                               ()                   
                     checkStateA(n)                   

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章