Wednesday, June 26, 2019
Home > Theory Of Computation > DFA Example : Construct The Minimal Finite Automata That Accepts All Base 8 Numbers Which Are Divisible By ‘6’

DFA Example : Construct The Minimal Finite Automata That Accepts All Base 8 Numbers Which Are Divisible By ‘6’

Construct The Minimal Finite Automata That Accepts All Base 8 Numbers Which Are Divisible By ‘6’

(Binary Means Base 2, i.e Σ(0,1) Input Symbols Will Be 2 Only 0 & 1)

(Integer Means Base 10,i.e (0,1,2,3,4,5,6,7,8,9) Input Symbols Will Be 10 Only 0&1&2&3&4&5&6&7&8&9)

 

Here Given Input Symbols Are Base ‘8’, It Means OCTAT.

My Input Symbols Are Σ={0,1,2,3,4,5,6,7}

 

Example :- (22)8

= (2×81+2×80)10

=(16+2)10

=(18)

 

After Conversion Into Decimal (22)Is Divisible By ‘6’

Possible Remainders For ‘6’

Question Is Divisible By ‘6’

Means Remainder Should Be ‘0’

For ‘0’ We Gave ‘q0‘As State ,  ‘q0‘ Is Final State.

 

q1= q4

q2=q5

 

q1& qAre Same, I’ll Merge Both.

q1= q4

q& q

Are Same, I’ll Merge Both.

q2=q5

 

No Commons States In This Table.

MAKE DFA USING THIS TABLE.

DFA Is Ready.

Now Take Any Number Which Has Base 8, Which Is Divisible By ‘6’

Example:- (22)8

If I Give ‘2’ To ‘q0‘ , I’ll Go To ‘q2

If I Give ‘2’ To ‘q2‘, I’ll Go To ‘q0‘(Final State)

Hence Satisfied.

 

TYPES OF PROBLEMS WE SOLVED TILL NOW.

  1. BINARY(INPUT SYMBOL) – (0,1)
  2. INTEGER (INPUT SYMBOL) – (0,9)
  3. BASE 8, OCTAT (INPUT SYMBOL) – (0-7)

Leave a Reply