3. Finite State Machines (18 points) (1) (4 points) Give a finite state machine M1 such that (2) (4 points) Give a finite state machine M2 such that it recognizes the set of all bit strings that start and end with the same symbol. In other words: L(Ma)-{yxy | x is any bit string and y ? {0, 1)) (3) Consider the finite state machines M3 and M4 given below (a) (1 point) List all strings of length 4 or less that are accepted by M3 (b) (3 points) What is L(M3)? (c) (1 point) List all strings of length 4 or less that are accepted by M4. (d) (3 points) What is L(M4)? start M3 start M4 0 do 91 do I1 0 0 0 0,1 93 (4) (6 points) Give a finite state machine M5 such that L(M5) w w is a binary number that is not divisible by 2) Hint: Try listing binary numbers divisible by 2 and look for a pattern