Question:

The following below 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 $ and move right. Otherwise exit loop.

2.2. Scan rightwards, past xs and #s to find y.

2.3. If y found, change it to # and move right. Otherwise reject.

2.4. Scan rightwards, past ys and %s to find z.

2.5. If z found, change it to % and move left. Otherwise reject.

2.6. Scan leftwards, past xs, ys, #s and %s to find $.

2.7. When finding the first $, 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.

List the first four elements of L(M) in lexicographic order (shortest first, then alphabetically if same length).