Program to build a DFA that checks if a string ends with "01" or "10" | CPP Program to DFA that accepts string ending with 01 or 10. ; Various states of DFA machine are defined using functions . ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void q1 ( string , int ) ; void q2 ( string , int ) ; void q3 ( string , int ) ; void q4 ( string , int ) ; void q1 ( string s , int i ) { cout << " q1 - > " ; if ( i == s . length ( ) ) { cout << " NO ▁ STRNEWLINE " ; return ; } if ( s [ i ] == '0' ) q1 ( s , i + 1 ) ; else q3 ( s , i + 1 ) ; } void q2 ( string s , int i ) { cout << " q2 - > " ; if ( i == s . length ( ) ) { cout << " NO ▁ STRNEWLINE " ; return ; } if ( s [ i ] == '0' ) q4 ( s , i + 1 ) ; else q2 ( s , i + 1 ) ; } void q3 ( string s , int i ) { cout << " q3 - > " ; if ( i == s . length ( ) ) { cout << " YES ▁ STRNEWLINE " ; return ; } if ( s [ i ] == '0' ) q4 ( s , i + 1 ) ; else q2 ( s , i + 1 ) ; } void q4 ( string s , int i ) { cout << " q4 - > " ; if ( i == s . length ( ) ) { cout << " YES ▁ STRNEWLINE " ; return ; } if ( s [ i ] == '0' ) q1 ( s , i + 1 ) ; else q3 ( s , i + 1 ) ; } void q0 ( string s , int i ) { cout << " q0 - > " ; if ( i == s . length ( ) ) { cout << " NO ▁ STRNEWLINE " ; return ; } if ( s [ i ] == '0' ) q1 ( s , i + 1 ) ; else q2 ( s , i + 1 ) ; } int main ( ) { string s = "010101" ; cout << " State ▁ transitions ▁ are ▁ " ; q0 ( s , 0 ) ; }