Consider the deterministic finite automaton M with states S = {so, $1,..., 87}, start state so, single accepting state s6, and alphabet = {0, 1}. The following table describes the transition function T: SX S. State SO $1 82 $3 S4 85 86 S7 01 S7 $1 82 87 87 $3 83 $4 S5 $4 $3 $6 $5 $4 S7 S7 i. Draw the transition diagram for M. ii. Let U = {101001101, 101100}. For each u EU describe the run for input u to M. Does M accept u? iii. Describe the language recognised by M. (b) Construct a finite-state machine which accepts a string w of 0s and 1s if and only if w contains the substring 1010. Activate W