CLASS 14 : CONSTRUCTION OF FINITE AUTOMATA (FA)

2. Construct a DFA which accept a string of 0's and 1's contain 3 consecutive 0's. Example (000, 1000, 00001, 10001, 11000, 111000 etc.)

Solution : 

 In this question we are talking about three consecutive 0's so we will take for states such as (q0, q1, q2, q3)

Let we understand with different cases by using different input strings for CONSTRUCTION OF FINITE AUTOMATA (FA) :

Case I : Input String = 000

Case II : Input String = 1000

Case III : Input String = 101000

Case IV : Input String = 101001000

Case IV : Input String = 1010010001   OR    10100100010

Formal Definition :

Q = {q0, q1, q2, q3}

Σ = {0,1}

q0 = q0

F = {q0}

δ = Transition Table

For CONSTRUCTION OF FINITE AUTOMATA (FA) we had seen different cases and finally construct a machine. In CASE V we get final graph.