A model that is studied in theoretical computer science is the finite state automaton. This is a machine that reads input from a tape, one character at a time, and based on what it reads it moves from where it currently is to one of several other internal states. For instance, a machine that is built to recognize the pattern 000 in an input string of 0 's and 1's can be designed as follows. State \(A\) is a start state, where we go if we have not seen a 0 yet, or have just seen a 1 so that the machine must try to look anew for the pattern. State \(B\) is a state we go to if we have seen a single 0 , state \(C\) is a state we go to if we have seen two 0 's in a row, and similarly state \(D\) is for three 0 's in a row. The machine stops and returns a success message if it reaches state \(D\); otherwise, if it does not before the input string runs out, then it returns an unsuccessful message.

(a) If the automaton described above is given the input string \(1,0,0,1,0,1,0,0,0\), what sequence of states does it occupy?

(b) Assuming that input strings are fed in such that characters are equally likely to be 0 or 1 , independently of previous characters, argue that the sequence of automaton states forms a Markov chain, and find its transition matrix.