Monday, July 22, 2019
Home > Theory Of Computation > DFA Example : Construct Minimal Deterministic Finite Automata(FA) Σ={0,1} Such That a) String Start With 0 And Length Is Divisible By 3 b) String Start With 010 And Length Is Equal To 3(Mod 5)

DFA Example : Construct Minimal Deterministic Finite Automata(FA) Σ={0,1} Such That a) String Start With 0 And Length Is Divisible By 3 b) String Start With 010 And Length Is Equal To 3(Mod 5)

Construct Minimal Deterministic Finite Automata(FA) Σ={0,1} Such That a) String Start With 0 And Length Is Divisible By 3 b) String Start With 010 And Length Is Equal To 3(Mod 5)

a) String Start With 0 And Length Is Divisible By 3

Given Σ={0,1}

String Start With 0 And Length Is Divisible By 3.

L={011,001,010,010000,010101010…..} // 011 Is Length 3, 001 Is Length 3, 010 Is The Length 3, 010101010 Is Length 9.

b) String Start With 010 And Length Is Equal To 3(Mod 5)

There String Should Start With 010 And Length Is Equal To 3(Mod 5)

If I Divide Length With Mod 5, I Should Get Remainder As ‘3’

L={010,010,01000,01000010,…..} // 010 Is Length 3, 010 Is Length 3,01000 Is Length 5,01000010 Is Length 8.

 

If I Have Length ‘3’ And If I Do Mod 5, I’ll Get ‘3’

If I Have Length ‘8’ And If I Do Mod 5 I’ll Get ‘3’

If I Have Length ’13’ And If I Do Mod 5 I’ll Get ‘3’

If I Have Length ’18’ And If I Do Mod 5 I’ll Get ’13’

The Difference Between String lengths Is ‘5’

 

 

 

 

Leave a Reply