EXERCISES ON ABSTRACT MACHINES



 1. (a) Show that the string 011001111 is in the language recognized by the 
        following nondeterministic FSA.




    (b) Find a set of strings that is not in the language recognized by
        the FSA. 

    (c) Give a deterministic FSA that recognizes the same language.

 2. Draw a Turing machine that halts if and only if the input consists of
    just 1's, and the number of 1's is even.

 3. Draw a Turing machine that halts if and only if the input is an
    alternating sequence of 1's and 2's.

There are additional exercises in "Notes on Formal Languages".