Problem 1

Using JFLAP, construct a Turing Machine that reads a string of a's and b's, erases the string, and halts with the tape head pointing to the cell that used to contain the first input symbol, where this cell contains 1 if the input string has odd length, and □ otherwise. Here's the catch: Your machine should never reach any cell of the tape that is to the left of the cell initially containing the first input character. In other words, we're going to pretend that JFLAP uses a 1-way infinite tape like our Turing Machine definition requires. You'll have to enforce this yourselves, so watch closely as you run the machine! Note: this differs from the previous homework, because you have to erase the input and leave the tape head pointing to the initial cell.

Turn in a screen capture of your JFLAP window.

Problem 2

Using JFLAP, construct a machine with Σ = {a,b} that replaces the input string w with the string Xw. Note the same rules apply here: Your machine should never reach any cell of the tape that is to the left of the cell initially containing the first input character.

Turn in a screen capture of your JFLAP window.

Problem 3

Write down the 5-tuple for the machine you constructed for part 2.

Problem 4

Give a modified version of the "Mystery Algorithm" from the class notes that produces a TM that decides $L(M)$, where $M$ is the input DFA, rather than semi-deciding it, like the algorithm in the notes does.