Build a DFA to accept Binary strings that starts or ends with "01" | Function for transition state A ; State transition to B if the character is 0 ; State transition to D if the character is 1 ; Function for transition state B ; Check if the string has ended ; State transition to C if the character is 1 ; State transition to D if the character is 0 ; Function for transition state C ; Function for transition state D ; State transition to D if the character is 1 ; State transition to E if the character is 0 ; Function for transition state E ; State transition to E if the character is 0 ; State transition to F if the character is 1 ; Function for transition state F ; State transition to D if the character is 1 ; State transition to E if the character is 0 ; Driver code
def checkstateA ( n ) : NEW_LINE INDENT if ( n [ 0 ] == '0' ) : NEW_LINE INDENT stateB ( n [ 1 : ] ) NEW_LINE DEDENT else : NEW_LINE INDENT stateD ( n [ 1 : ] ) NEW_LINE DEDENT DEDENT def stateB ( n ) : NEW_LINE INDENT if ( len ( n ) == 0 ) : NEW_LINE INDENT print ( " string ▁ not ▁ accepted " ) NEW_LINE DEDENT else : NEW_LINE INDENT if ( n [ 0 ] == '1' ) : NEW_LINE INDENT stateC ( n [ 1 : ] ) NEW_LINE DEDENT else : NEW_LINE INDENT stateD ( n [ 1 : ] ) NEW_LINE DEDENT DEDENT DEDENT def stateC ( n ) : NEW_LINE INDENT print ( " String ▁ accepted " ) NEW_LINE DEDENT def stateD ( n ) : NEW_LINE INDENT if ( len ( n ) == 0 ) : NEW_LINE INDENT print ( " string ▁ not ▁ accepted " ) NEW_LINE DEDENT else : NEW_LINE INDENT if ( n [ 0 ] == '1' ) : NEW_LINE INDENT stateD ( n [ 1 : ] ) NEW_LINE DEDENT else : NEW_LINE INDENT stateE ( n [ 1 : ] ) NEW_LINE DEDENT DEDENT DEDENT def stateE ( n ) : NEW_LINE INDENT if ( len ( n ) == 0 ) : NEW_LINE INDENT print ( " string ▁ not ▁ accepted " ) NEW_LINE DEDENT else : NEW_LINE INDENT if ( n [ 0 ] == '0' ) : NEW_LINE INDENT stateE ( n [ 1 : ] ) NEW_LINE DEDENT else : NEW_LINE INDENT stateF ( n [ 1 : ] ) NEW_LINE DEDENT DEDENT DEDENT def stateF ( n ) : NEW_LINE INDENT if ( len ( n ) == 0 ) : NEW_LINE INDENT print ( " string ▁ accepred " ) NEW_LINE DEDENT else : NEW_LINE INDENT if ( n [ 0 ] == '1' ) : NEW_LINE INDENT stateD ( n [ 1 : ] ) NEW_LINE DEDENT else : NEW_LINE INDENT stateE ( n [ 1 : ] ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = "0100101" NEW_LINE checkstateA ( n ) NEW_LINE DEDENT