Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Using JFLAP, construct a Turing Machine that reads a string of a's and b's, erases the string, and prints either a 1 or 0 in the cell that used to contain the first character of the input string: 1 if the string has odd length, 0 if the string has even length. 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!

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 3x

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