Question

Automata Theory and Formal Languages

Instructions:

Draw the DFA (Deterministic Finite Automaton) of the following:

1. DFA for binary number divisible by 2
2. DFA for binary number divisible by 3
3. DFA in which set of all strings can be accepted which start with a
4. DFA in which set of all strings can be accepted which contains ‘a’

Answer 1

DFA for binary number divisible by 2

Consider input :

{0, 01, 10, 11, 100, 101, 110........}

States : q0, q1

Inputs are strings of 0,1

The state q0 is final state and q1 is non-final state. State q0 will be representing all the numbers that are divisible by 2, that is {0, 10, 100, 110…..}.
State q1 will be representing all the numbers that are not divisible by 2, that is {01, 11, 101, ……}

Whenever the number is not divisible by 2 then it will go from state q0 to q1. When the number is divisible by 2, then it will go from state q1 to q0 or if it was initially in q0 then it will accept it.

DFA for binary number divisible by 3

When a number is divided by 3, there are only 3 possibilities. The remainder can be either 0, 1 or 2. Here, state 0 represents that the remainder when the number is divided by 3 is 0. State 1 represents that the remainder when the number is divided by 3 is 1 and similarly state 2 represents that the remainder when the number is divided by 3 is 2. So if a string reaches state 0 in the end, it is accepted otherwise rejected.

DFA in which set of all strings can be accepted which start with a.

DFA in which set of all strings can be accepted which contains ‘a’

L1 = {a, aa, ab, ba, ..............}

DFA, states ‘X’ and ‘Y’ are the initial and final state respectively, it accepts all the strings containing ‘a’ as the substring. Here as we see that on getting input as ‘b’ it remains in the state of ‘X’ itself but on getting ‘a’ as the input it transit to final state ‘Y’ and hence such string is accepted by above DFA.