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.