Search code examples
automatadfa

Deterministic Finite Automata divisibility problem

Design a DFA that accepts the string given by L = { w has number of 'a' divisible by 3 and number of 'b' divisible by 2 over the alphabet {a,b} }

Solution

  • Realize that we should have 3 * 2 = 6 states in the DFA. Why? Because one has 3 choices for the number of a's (0 or 1 or 2) [think in terms of remainders] and 2 choices for number of b's (0 or 1 similarly).

    Let us name the states axby which means I have found x number of a's and y number of b's till now. For example, if we are in a2b0 and we encounter an a, then we go to a0b0 (hope you see why?). Similarly a1b1 ---b---> a1b0 and a1b1 ---a---> a2b1. Needless to say a0b0 is the accepting state.

    Now, all you have to do is draw the states and keep joining them. I have drawn them on a paper here.

    Answer