ANSWERS TO EXERCISES ON ABSTRACT MACHINES



 1. (a) State transitions A -> A -> B -> A ->  A ->  A -> B -> B -> B -> B  

    (b) Any string ending with 0 (and plenty of others, such as 110101).

    (c) See Lecture note slide on reduction from NFSA to FSA.




             0  1
             ----
      empty  0  0
          B  0  3
          A  2  1
         AB  2  3


     

     

    
 2.










 3.