Class 19 - CONSTRUCTION OF FINITE AUTOMATA (FA)

7. Constrict a DFA which accept number ( integer) divisible by 3 or (multiple of 3) .

Solution:

Here for CONSTRUCTION OF FINITE AUTOMATA (FA) input strings are combination of a and b and string having 0 - 9  number  i.e 10 numbers because any number divisible by 3 the resulting number must be between 0 - 9.

For CONSTRUCTION OF FINITE AUTOMATA (FA) we will take different cases of input string and trace it. In this case No of group = No of state.

Let we have three groups
Group1: 0,3,6,9
Group2: 2,5,8
Group3: 1,4,7

Group1 is divisible by 3.
Group2 & Group3 is not divisible by 3.

Here we have two states such as q0 , q1, q3. where q0 is final state.


let we start

Case I: Input string = If we take Group1 such as (0,3,6,9) which is divisible by 3 initially then.

Case II: Input string = If we take Group2 and Group3 such as ( 2,5,8 / 1,4,7 ) which is divisible by 3 initially then.

Formal Definition :

Q = { q0 , q1 , q2 }

Σ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }

q0 = q0   Initial state

F = { q0 }

δ = 

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE II we get final graph.