Monday, July 22, 2019
Home > Theory Of Computation > DFA Example : Direct Calculation Of Number Of States

# DFA Example : Direct Calculation Of Number Of States

Direct Calculation Of Number Of States – Let’s See The Technique With Which We Can Get No. Of States Very Easily

This Is The ‘ Short Cut ‘

And

Short Cut’s Are Very Important To Solve Problem Quickly.

This Helps In Getting Minimal DFA Using This Technique We Can Directly Know The Number Of States Of DFA.

If You Observed The Previous Problems I Solved, To Get The No Of States I Solved Problem, I Have Drawn A Transition Table.

If I Find Any Common ‘ States ‘ I Removed Those And Using The Table I Have Drawn DFA And I Came To Know The No. Of States.

The Questions Given Before Are Like Mod 3, Mod 4, Mod 5 But What If The Question Is Mod 120.

You’ll Take 120 Possible Remainders(0-120)

You Need To Draw Transition Table, Then You Need To See The No. Of Common States, You Need To Merge The Common States.

“This Takes Lot Of Time” To Solve One Problem.

Lets See A Problem

Count The Number Of States In Minimal FA That Accepts All The Binary Strings Who’s Integer Equivalent Is Congruent To

For Small Values Like Mod 3, Mod 4, Mod 5, Mod 6, Mod 7.It Is Very Easy To Find States Using The Above Method( And I Did It In Previous Problems)

19 Mod 120,

3 Mod 36?

You Can’t Solve These Problem Using Above Method.

I Have A Technique To Solve Big Numbers ‘ Short Cut ‘

FORMULA Of SHORTCUT (OR) TECHNIQUE

If Σ={0,1} // Input Symbol

This Technique Works For Only Σ={0,1} // Input Symbols

L= Binary String

Its Integer Equivalent ≅ r(mod n)

Binary To Integer Equivalent Conversion

If Question Is To Find No. Of States.

## 1.If ‘n’ Is Odd Number Then-No. Of States Will Be Equal To ‘n’

Example- Mod 5  (Odd)

In These States Will Not Merge, I Mean States Will Not Be Common.

If Your ‘n’ Is Odd , The No Of States Will Be ‘n’ Only.

5,7,9,11,13,15,17,19,21……. // Odd

## 2. If ‘n’ Is Even The Count The Number Of Times You Can Divide n By ‘2’ Until You Got The Odd Number Quotient Then NOS=Count+Odd Quotient.

Example:-

1) 16/2=8/1

2) 8/2=4/1

3) 4/2=2/1

4) 2/2=1/1

Then NOS=Count+Odd Quotient

(4 times)+ 1=5

## Examples

• ≅ 2 (Mod 6)  // 6 is even

6/2=3

NOS=1+3=4

• ≅ 4 (Mod 16) //  16 is even

16/2=8/2,4/2,2/2=1

NOS=1+4=5

• ≅ 3 (Mod 9) // 9 is odd

NOS=9

• ≅ 5 (Mod 10) // 10 is even

10/2=5

NOS=1+5=6

• ≅ 8 (Mod 12) // 12 is even

6/2=3

NOS=2+3=5

• ≅ 8 (Mod 32) // 32 is even

32/2=16/2,8/2,4/2,2/2,1

NOS=5+1=6

• ≅ 10 (Mod 72) // 72 is even

72/2=36/2,18/2,9

NOS=3+9=12

• ≅ 19 (Mod 120) // 120 is even

120/2=60/2,30/2,15/2

NOS=3+15=18

• ≅  (3 Mod 36) // 36 is even

36/2=18/2,9

NOS=2+9=11