In: Computer Science
construct a DFA to check if a string containing a,b and no.of a's is divisible by 5 and no.of b's is divisible by 7
So basically to design a DFA, we first need to decide what will be the states.
Here, I've chosen states qij which denotes a state where ( number of a's ) % 5 = i and ( number of b's ) % 7= j
So basically we move from one state to another according to the character being considered.
The logic for moving from qi6 to qi0 when b is encountered is simple as, that if a number mod 7 is 6 that means adding 1 more, will make it divisible by 7 and resulting in 0 as remainder.
Similar is the reason for q6j to q0j when an a is encountered.
q00 is the finalstate as only there, the number of a's are divisible by 5 and number of b's are divisible by 7.
Another than that, it is a normal DFA and all conditions are understandable.