1. (25 points) Turing Machine Design: Design a Turing machine Mi that operates on inputs that...
1. (25 points) Turing Machine Design: Design a Turing machine Mi that operates on inputs that are strings in 10, 1). Design Mi so that it recognizes the following language: fw E (0.1)l w ends in 10 or 111) a. Provide a high-level English prose description for the actions of Mi b. Provide an implementation-level description of M. c. List the parts of the formal 7-tuple for M d. Draw a detailed pictorial state diagram for M1 e. List the sequence of configurations (instantaneous descriptions) that Mi enters for each of these two inputs: i. 101 (Which Mi should reject). ii. 111 (Which My should accept).