CompSci 18S - Spring 2007 - Turing Machines

For group work, please turn in one sheet of paper with all the names of those who participated in your group.

We will use JFLAP to solve these problems. See below for info on JFLAP and how to get a zip file of these problems.

Problem

Turing machines are the heart of computer science. Alan Turing invented the Turing machine in 1936 (24 years old). He defined it in on paper and showed how to use it to solve problems. There were no computers for years still. Turing machines are similar to finite automaton in that there is an initial (or start) state (an arrow into it), and one or more states can be final states (indicated by two circles). With finite automata, the input is scanned just once and a decision is made whether or not to accept. However, Turing machines can write to the tape and also move over the input many times, using directions ((L)eft, (R)ight or (S)tay put). Thus, transitions are different to represent this additional information. A transition is labeled with three items. The first item is the character in the input processed (this is the same as for the finite automata). The second item is the character to write to the tape (to replace the first item). The third item is the direction to move (L, R or S). If the first or second item is left blank, that is the same as reading or writing a blank symbol. Turing machines are also different in that they can compute values, have an input and a corresponding output. For example, consider the Turing machine shown below that takes as input a string of a's and b's and outputs the same string with each "aa" replaced by "ab". Note that "aaa" would be replaced by "aba", "aaaa" would be replaced with "abab".

Problems

1. Load the file turingmachine1.jff for the Turing machine above. List five strings and their corresponding output. Run the Turing machine on these strings.

2. Write a Turing machine for the following problem. f(w) = v, where w is a string of a's, and v is a string of a's such that the number of a's in v is twice the number of a's from w. There are no other symbols in the strings. For example, f(a) = aa, f(aa) = aaaa, and f(aaa) = aaaaaa.

   Draw a picture of it to turn in.

3. Load the file turingmachine2.jff. This Turing machine doesn't work correctly. It is suppose to compute the following, f(v)=w where w is a string of a's and b's, and v is w with c added between every pair of a's. For example, f(aaba) = acaba, f(aaabaa) = acacabaca, and f(ababba) = ababba (here no c's were added because there are no adjacent a's).

   Here is a picture of this Turing machine.
   

   
   

   Determine why this Turing machine does not work and fix it so it works correctly.

4. Turing machines can have two tapes also. In this case it looks at both current symbols on the two tapes, then writes to both of the tapes, then moves on each tape (can move different directions). Load the file turingmachine3.jff of a 2-tape Turing machine..

   What is the output of this Turing machine for the strings: 1, 11, 111, 1111, 11111 (put the input string on tape 1 to start, leave tape 2 blank, the output will be on tape 2.). Give a description of what it computes.

   Here is a picture of this Turing machine.
   

   
   

How to use JFLAP with Turing machines

The Turing machines above are all here in a zip file called jflapturingmachines.zip

• Start JFLAP and select Turing machine to create a new Turing machine, or Open to open a file. In the editor, there are four buttons . The second button is for creating states. Click on it, and then click anywhere on the canvas to create a state. The second button (the arrow pointing up and to the right) is for creating transitions. Click on a state (and hold the mouse button down), then release on a second state. You will be prompted for the transition's label, and then the labeled transition will be created. The first button is for "fixing things up". After selecting it you can click on a state and move it to a different position, or you can right click on a state and select initial or final state. You can also add a label to annotate your states.

  To test it on input strings. First select "Input", then "Step" to trace through one string. To see the output for several inputs, select "Multiple Run (Transducer)."