Program to build a DFA that checks if a string ends with "01" or "10" | End position is checked using the string length value . q0 is the starting state . q1 and q2 are intermediate states . q3 and q4 are final states . ; state transitions 0 takes to q1 , 1 takes to q3 ; state transitions 0 takes to q4 , 1 takes to q2 ; state transitions 0 takes to q4 , 1 takes to q2 ; state transitions 0 takes to q1 , 1 takes to q3 ; state transitions 0 takes to q1 , 1 takes to q2 ; Driver Code ; all state transitions are printed . if string is accpetable , YES is printed . else NO is printed
def q1 ( s , i ) : NEW_LINE INDENT print ( " q1 - > " , end = " " ) ; NEW_LINE if ( i == len ( s ) ) : NEW_LINE INDENT print ( " NO " ) ; NEW_LINE return ; NEW_LINE DEDENT if ( s [ i ] == '0' ) : NEW_LINE INDENT q1 ( s , i + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT q3 ( s , i + 1 ) ; NEW_LINE DEDENT DEDENT def q2 ( s , i ) : NEW_LINE INDENT print ( " q2 - > " , end = " " ) ; NEW_LINE if ( i == len ( s ) ) : NEW_LINE INDENT print ( " NO " ) ; NEW_LINE return ; NEW_LINE DEDENT if ( s [ i ] == '0' ) : NEW_LINE INDENT q4 ( s , i + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT q2 ( s , i + 1 ) ; NEW_LINE DEDENT DEDENT def q3 ( s , i ) : NEW_LINE INDENT print ( " q3 - > " , end = " " ) ; NEW_LINE if ( i == len ( s ) ) : NEW_LINE INDENT print ( " YES " ) ; NEW_LINE return ; NEW_LINE DEDENT if ( s [ i ] == '0' ) : NEW_LINE INDENT q4 ( s , i + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT q2 ( s , i + 1 ) ; NEW_LINE DEDENT DEDENT def q4 ( s , i ) : NEW_LINE INDENT print ( " q4 - > " , end = " " ) ; NEW_LINE if ( i == len ( s ) ) : NEW_LINE INDENT print ( " YES " ) ; NEW_LINE return ; NEW_LINE DEDENT if ( s [ i ] == '0' ) : NEW_LINE INDENT q1 ( s , i + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT q3 ( s , i + 1 ) ; NEW_LINE DEDENT DEDENT def q0 ( s , i ) : NEW_LINE INDENT print ( " q0 - > " , end = " " ) ; NEW_LINE if ( i == len ( s ) ) : NEW_LINE INDENT print ( " NO " ) ; NEW_LINE return ; NEW_LINE DEDENT if ( s [ i ] == '0' ) : NEW_LINE INDENT q1 ( s , i + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT q2 ( s , i + 1 ) ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = "010101" ; NEW_LINE print ( " State ▁ transitions ▁ are " , end = " ▁ " ) ; NEW_LINE q0 ( s , 0 ) ; NEW_LINE DEDENT