Home > Theory Of Computation > Construct Minimal Finite Automata That Accepts All Strings Of 0’s And 1’s Such That i) η0|w|≅0 (mod 3) ii) η0|w|≅0 (mod 4)

# Construct Minimal Finite Automata That Accepts All Strings Of 0’s And 1’s Such That i) η0|w|≅0 (mod 3) ii) η0|w|≅0 (mod 4)

Construct Minimal FA That Accepts All Strings Of 0’s And 1’s Such That i) η0|w|≅0 (mod 3) ii) η0|w|≅0 (mod 4)

Σ={0,1}

## i) η0|w|≅0 (mod 3) // η0 Is No. Of Zero’s, |w| Is In The String, If I Divide With ‘3’, I’ll Get Remainder ‘0’.

Means,

The No. Of 0’s In The String,If I Divide Those String’s With ‘3’ I’ll Get Remainder ‘0’

I’ll Take A String 11111, It It Contains Zero Number Of 0’s.

0 % 3 = 0 (0 Mod 3)=0

Remember

In Mod Operation You’ll Get Remainder.

In Division Operation You’ll Get Qutition.

We Are Doing Mod Operation There.

Mod Operation

11011 // We Have Only One Zero In This String.

1%3=1(1 Mod 3)=1

We Got ‘1’ But We Should Get Remainder ‘0’

Means 0 Num Of Zero’s

3 Number Of Zero’s

6 Number Of Zero’s

9 Number Of Zero’s

0,3,6,9,12…..

If I Divide These With 3, I’ll Get Remainder As ‘0’

η0|w|≅0 (mod 3)

L= {ε,1111,000,11011011011……}  // ε=0,means 0/3=0, 1111= no zero’s,000=3 zero’s,means 3/3 =0

### ε

(ii) η0|w|≅1 (mod 4)

If I Count No. Of Zero’s In A String And If I Divide That String With ‘4’, I Should Get Remainder As ‘1’.

Count No.Of Zero’s In The String And Divide It With ‘4’

5/4=1

9/4=1

13/4=1

17/4=1

L={0,00000,11001110010…….}