Example of Algorithm we discussed in class:

2. Describe a (single-tape) Turing machine for each of the following languages. Please don't give a complete description of the transition table. Instead, give an algorithm at the same level of detail as in Nov 20 lecture. Clearly describe the tape movement and modifications to the tape cells. (a) {w e {a, b}* | w has odd length and its middle character is a} (b) {a^bmek | k = nm} (c) {an | n is a power of 2}