Program to build a DFA to accept strings that start and end with same character | Function for the state Q1 ; Condition to check end of string ; State transitions ' a ' takes to q1 , and ' b ' takes to q2 ; Function for the state Q2 ; Condition to check end of string ; State transitions ' a ' takes to q1 , and ' b ' takes to q2 ; Function for the state Q3 ; Condition to check end of string ; State transitions ' a ' takes to q4 , and ' b ' takes to q3 ; Function for the state Q4 ; Condition to check end of string ; State transitions ' a ' takes to q4 , and ' b ' takes to q3 ; Function for the state Q0 ; Condition to check end of string ; State transitions ' a ' takes to q1 , and ' b ' takes to q3 ; Driver Code ; Since q0 is the starting state Send the string to q0
def q1 ( s , i ) : NEW_LINE INDENT if ( i == len ( s ) ) : NEW_LINE INDENT print ( " Yes " ) ; NEW_LINE return ; NEW_LINE DEDENT if ( s [ i ] == ' a ' ) : NEW_LINE INDENT q1 ( s , i + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT q2 ( s , i + 1 ) ; NEW_LINE DEDENT DEDENT def q2 ( s , i ) : NEW_LINE INDENT if ( i == len ( s ) ) : NEW_LINE INDENT print ( " No " ) ; NEW_LINE return ; NEW_LINE DEDENT if ( s [ i ] == ' a ' ) : NEW_LINE INDENT q1 ( 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 if ( i == len ( s ) ) : NEW_LINE INDENT print ( " Yes " ) ; NEW_LINE return ; NEW_LINE DEDENT if ( s [ i ] == ' a ' ) : NEW_LINE INDENT q4 ( s , i + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT q3 ( s , i + 1 ) ; NEW_LINE DEDENT DEDENT def q4 ( s , i ) : NEW_LINE INDENT if ( i == s . length ( ) ) : NEW_LINE INDENT print ( " No " ) ; NEW_LINE return ; NEW_LINE DEDENT if ( s [ i ] == ' a ' ) : NEW_LINE INDENT q4 ( 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 if ( i == len ( s ) ) : NEW_LINE INDENT print ( " No " ) ; NEW_LINE return ; NEW_LINE DEDENT if ( s [ i ] == ' a ' ) : NEW_LINE INDENT q1 ( s , i + 1 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT q3 ( s , i + 1 ) ; NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s = " abbaabb " ; NEW_LINE q0 ( s , 0 ) ; NEW_LINE DEDENT