1. (10) The following is a high level description for a Turing machine M. List the first four elements of L(M) in lexicographic order (shortest first, then alphabetically if same length) 1. Move right. 2. Loop: 2.1. If the current symbol is x, change it to S and move right. Otherwise exit loop. 2.2. Scan rightwards, pasta's and #'s to find y. 2.3. If y found, change it to # and move right. Otherwise reject. 2.4. Scan rightwards, past y's and 90's to find z. 2.5. If z found, change it to % and move left. Otherwise reject. 2.6. Scan leftwards, past x's, y's, #'s and 96's to find $. 2.7. When finding the first S, move right, and go back to 2.1. 3. If the current symbol is #, more right. Otherwise reject. 4. Scan rightwards, past #'s and %'s, to find the blank symbol. 5. When finding the first blank symbol, move right and accept