Wednesday, June 26, 2019
Home > Theory Of Computation > DFA Example : Construct Minimal Finite Automata That Accepts All Strings Of 0’s & 1’s Such That a) |w|≅0 (mod 2), b) |w|≅1 (mod 2), c) |w|≅2 (mod 3)

DFA Example : Construct Minimal Finite Automata That Accepts All Strings Of 0’s & 1’s Such That a) |w|≅0 (mod 2), b) |w|≅1 (mod 2), c) |w|≅2 (mod 3)

Construct Minimal Finite Automata That Accepts All Strings Of 0’s & 1’s Such That a) |w|≅0 (mod 2), b) |w|≅1 (mod 2), c) |w|≅2 (mod 3)

|w|= Length Of ‘w’ String

a) |w|≅0 (mod 2)

Means If I Divide Length Of String With ‘2’ I Should Get Remainder ‘1’

‘ε’ Is Length ‘0’ String, If I Divide 0 With 2 I’ll Get ‘0’

Next

2(0’s & 1’s) Mod 2 =0, 4(0’s & 1’s) Mod 2=0

8(0 & 1’s) Mod 2=0, 10(0 & 1’s) Mod 2=0

(ε,2,4,6,8,10…….}

 

(ε,2,4,6,8,10…….} // 2 Divisible

Means

L={ε,10,11,1010,110101,……} // 10 – 2 , 11 – 2 , 1010 – 4 , 110101 – 6 ………}

 

b) |w|≅1 (mod 2)

If I Divide Length Of The String With ‘2’ I Should Get Remainder ‘1’

What Are The Possible String Length’s..?

(ε) 0 Mod 2 = 0

1 Mod 2 = 1

2 Mod 2 = 0

3 Mod 2 = 1(Remainder)

4 Mod 2 = 0

5 Mod 2 = 1

L={1,0,101,010,01010….} // (1,3,5,9,11,13….) // 1 = Length 1 , 0 = Length 1, 101 = Length 3, 010= Length 3, 01010 = Length 5.

c) |w|≅2 (mod 3)

If I Divide Length Of The String With 3, I Should Get Remainder As 2.

Possible String Lengths=(2,5,8,11…….)

L={00,01,11,10,01010,01010101……} // 00,01,11,10 Are Of 2 Lengths, 01010 Is Length 5

 

2 thoughts on “DFA Example : Construct Minimal Finite Automata That Accepts All Strings Of 0’s & 1’s Such That a) |w|≅0 (mod 2), b) |w|≅1 (mod 2), c) |w|≅2 (mod 3)

Leave a Reply