Home > Theory Of Computation > Construct The Minimal DFA Which Accept All Integers Which Are Divisible By ‘6’

Construct The Minimal DFA Which Accept All Integers Which Are Divisible By ‘6’

Construct The Minimal DFA Which Accept All Integers Which Are Divisible By ‘6’

 

L={0,6,12,18,24……}

For Binary Numbers, The Input Symbols Were 0,1

i,e Σ={0,1}

 

But Here In This Problem. We Are Seeing Integer Number System.

Means

Decimal Number System

(0,1,2,3,4,5,6,7,8,9)

 

In Decimal Number System The Base Will Be 10, We All Know That.

 

Means 0-10, Any Number Can Come From 0 to 9 ( Characters (or) Alphabets)

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

Which One Is The Final State In The Table?

6 Is Divisible, So The Remainder Will Be 0, What Is 0? ,0 =q0,qIs My Final State.

The Entries.q0, qAre Same To Reduce The Size Of Table. I Have To Remove One Of Those States.

 

But I Cant Remove One Of Those States In This Table Because, q0

Is Final State And qIs Non- Final State

 

I Cant Merge Final & Non-Final States.

 

q1,qAre Same, I Can Merge Both.

q1=q4

q2,qAre Same, I Can Merge Both.

q2=q5

 

qIs Replaced In The Place Of q4

q2  Is Replaced In The Place Of q5

 

Observe If Still Any Two States Are Common In The New Table To Merge.

No, There Is No Common States In The Table.

 

q0, q3

Are Same But We Can’t Merge Final And Non- Final States.

 

Now You Have Table, You Can Create DFA.

 

CROSSCHECK

Example – 24 – Divisible By 6

If I Give ‘2’ To q0(Starting State) I’m Going To ‘q2‘ And If I Give ‘4’ To ‘q2‘ I’m Going To ‘q0‘ Final State.

Hence Diagram Is Correct.

Hence Diagram Is Correct.

 

Example – 48 – Divisible By 6

If I Give ‘4’ To ‘q0‘ I’m Going To ‘q1‘ And If I Give 8 To ‘q1‘ I’m Going To ‘q0‘ (Final State)

Hence The DFA Is Correct.

 

NOTE :- IF YOU KNOW HOW TO CREATE TRANSITION TABLE YOU CAN EASILY DRAW DFA.

 

 

 

Leave a Reply