CS1103 Programming Assignment Unit 3 - Create a tape for a Turing machine using a doubly-linked list

Introduction

In the blog, A tape for a Turing Machine is created using a doubly-linked list. To test the Tape class, one can run the programs TestTape.java, TestTapeGUI.java, and TestTuringMachine.java.

1. Programs

Cell.java

package turing;

/**
 * Represents one cell on a Turing Machine tape.
 */
public class Cell {
    public char content;  // The character in this cell.
    public Cell next;     // Pointer to the cell to the right of this one.
    public Cell prev;     // Pointer to the cell to the left of this one.
}

Tape.java

package turing;

/**
 * A class named Tape to represent Turing machine tapes.
 * A Turing machine tape can be represented by a doubly-linked list
 * where each cell has a pointer to the previous cell (to its left) and to the next cell (to its right).
 * The pointers will allow the machine to advance from one cell to
 * the next cell on the left or to the next cell on the right.
 */
public class Tape {
    //  an instance variable of type Cell that points to the current cell
    private Cell currentCell;

    /**
     * a constructor that creates a tape that initially consists of a single cell
     */
    public Tape() {
        // create a new cell that contain a blank space
        Cell newCell = new Cell();
        newCell.content = ' ';
        newCell.next = null;
        newCell.prev = null;

        // let the current cell pointer point to the newCell
        this.currentCell = newCell;
    }

    /**
     * returns the pointer that points to the current cell
     *
     * @return
     */
    public Cell getCurrentCell() {
        return currentCell;
    }

    /**
     * returns the char from the current cell
     */
    public char getContent() {
        return currentCell.content;
    }

    /**
     * changes the char in the current cell to the specified value
     *
     * @param ch
     */
    public void setContent(char ch) {
        currentCell.content = ch;
    }

    /**
     * Moves the current cell one position to the left along the tape.
     * If the current cell is the leftmost cell that exists,
     * then a new cell must be created and added to the tape at the left of the current cell,
     * and then the current cell pointer can be moved to point to the new cell.
     * The content of the new cell should be a blank space
     */
    public void moveLeft() {
        if (currentCell.prev == null) { // if the current cell is the leftmost cell that exists
            Cell newCell = new Cell(); // create a new cell
            newCell.content = ' '; // The content of the new cell should be a blank space
            newCell.prev = null;
            newCell.next = currentCell; // add the new cell to the tape at the left of the current cell
            currentCell.prev = newCell;
        }
        currentCell = currentCell.prev; // Moves the current cell one position to the left along the tape
    }

    /**
     * Moves the current cell one position to the right along the tape.
     * Note that if the current cell is the rightmost cell that exists,
     * then a new cell must be created and added to the tape at the right of the current cell,
     * and then the current cell pointer can be moved to point to the new cell.
     * The content of the new cell should be a blank space.
     */
    public void moveRight() {
        if (currentCell.next == null) { // if the current cell is the rightmost cell that exists
            Cell newCell = new Cell(); // create a new cell
            newCell.content = ' '; // The content of the new cell should be a blank space
            newCell.next = null;
            newCell.prev = currentCell; // add the new cell to the tape at the right of the current cell
            currentCell.next = newCell;
        }
        currentCell = currentCell.next; // Moves the current cell one position to the right along the tape
    }

    /**
     * Moves the current cell one position to the right along the tape.
     * Note that if the current cell is the rightmost cell that exists,
     * then a new cell must be created and added to the tape at the right of the current cell,
     * and then the current cell pointer can be moved to point to the new cell.
     * The content of the new cell should be a blank space.
     */
    public void moveRightInQuiz() {
        if (currentCell.next == null) { // if the current cell is the rightmost cell that exists
            Cell newCell = new Cell(); // create a new cell
            newCell.content = ' '; // The content of the new cell should be a blank space
            newCell.next = null;
            newCell.prev = currentCell; // add the new cell to the tape at the right of the current cell
            currentCell.next = newCell;
            currentCell = currentCell.next; // Moves the current cell one position to the right along the tape
        }
    }

    /**
     * returns a String consisting of the chars from all the cells on the tape,
     * read from left to right, except that leading or trailing blank characters should be discarded.
     * The current cell pointer should not be moved by this method; it should point to the
     * same cell after the method is called as it did before.
     * You can create a different pointer to move along the tape and get the full contents.
     *
     * @return a String consisting of the chars from all the cells on the tape
     */
    public String getTapeContents() {
        // return "" if there are no cells
        if ((currentCell.next == null) && (currentCell.prev == null)) return "";

        // Concatenate chars on the tape and convert them into strings for output
        StringBuilder stringBuilder = new StringBuilder();

        // Concatenate the currentCell's content
        stringBuilder.append(currentCell.content);

        // Concatenate the contents of all preceding cells
        Cell cell = currentCell.prev;
        while (cell != null) {
            stringBuilder.insert(0, cell.content);
            cell = cell.prev;
        }

        // Concatenate the contents of all following cells
        cell = currentCell.next;
        while (cell != null) {
            stringBuilder.append(cell.content);
            cell = cell.next;
        }
        return stringBuilder.toString().trim();
    }
}

TestTape.java

package turing;

/**
 * A test program for the Tape class that calls most of the methods in that class.
 *
 * The output from this program should be:  Tape Conents:  Hello World
 *                                          Final position at the W
 *
 */
public class TestTape {
    public static void main(String[] args) {
        Tape tape = new Tape();

        for (int i = 0; i < "World".length(); i++) {
            tape.setContent("World".charAt(i));
            System.out.println("The position at the " + tape.getContent());
            tape.moveRight();
            System.out.println("The position at the " + tape.getContent());
        }

        System.out.println();

        for (int i = 0; i < "Hello World".length(); i++) {
            tape.moveLeft();
            System.out.println("The position at the " + tape.getContent());
        }

        System.out.println();

        for (int i = 0; i < "Hello".length(); i++) {
            tape.setContent("Hello".charAt(i));
            System.out.println("The position at the " + tape.getContent());
            tape.moveRight();
            System.out.println("The position at the " + tape.getContent());
        }

        System.out.println("Tape Conents: " + tape.getTapeContents());

        tape.moveRight(); // move the position from ' ' to 'W'
        System.out.println("Final position at the " + tape.getContent());
    }
}

TestTapeGUI.java

package turing;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

/**
 * A test program for the Tape class that creates a window containing
 * a graphical representation of the tape with an arrow pointing to
 * the current cell.  There are buttons for moving the current cell to
 * the left and to the right.  A text-input box shows the content of
 * the current cell.  This box can be edited, and there is a "Set" button
 * that copies the contents of the cell (actually just the first character)
 * to the current cell.
 */
public class TestTapeGUI extends JPanel {

    public static void main(String[] args) {
        JFrame window = new JFrame("Test Tape");
        window.setContentPane(new TestTapeGUI("Test"));
        window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        window.pack();
        window.setLocation(100, 100);
        window.setVisible(true);
    }

    private Tape tape;
    private TapePanel tapePanel;
    private JButton moveLeftButton, moveRightButton, setContentButton;
    private JTextField contentInput;

    private class TapePanel extends JPanel {
        public void paintComponent(Graphics g) {
            super.paintComponent(g);
            int mid = getWidth() / 2;
            g.drawLine(0, 30, getWidth(), 30);
            g.drawLine(0, 60, getWidth(), 60);
            g.drawLine(mid, 70, mid, 110);
            g.drawLine(mid, 70, mid + 15, 85);
            g.drawLine(mid, 70, mid - 15, 85);
            int ct = (mid / 30) + 1;
            for (int i = 0; i <= ct; i++) {
                g.drawLine(mid + 30 * i - 15, 30, mid + 30 * i - 15, 59);
                g.drawString("" + tape.getContent(), mid + 30 * i - 8, 53);
                tape.moveRight();
            }
            for (int i = 0; i <= ct; i++)
                tape.moveLeft();
            for (int i = 1; i <= ct; i++) {
                g.drawLine(mid - 30 * i - 15, 30, mid - 30 * i - 15, 59);
                tape.moveLeft();
                g.drawString("" + tape.getContent(), mid - 30 * i - 8, 53);
            }
            for (int i = 1; i <= ct; i++)
                tape.moveRight();
        }
    }

    private class ButtonListener implements ActionListener {
        public void actionPerformed(ActionEvent evt) {
            if (evt.getSource() == moveLeftButton)
                tape.moveLeft();
            else if (evt.getSource() == moveRightButton)
                tape.moveRight();
            else {
                String content = contentInput.getText();
                if (content.length() == 0)
                    tape.setContent(' ');
                else
                    tape.setContent(content.charAt(0));
            }
            contentInput.setText("" + tape.getContent());
            contentInput.selectAll();
            contentInput.requestFocus();
            tapePanel.repaint();
        }
    }

    public TestTapeGUI(String initialContent) {
        tape = new Tape();
        if (initialContent != null && initialContent.length() > 0) {
            for (int i = 0; i < initialContent.length(); i++) {
                tape.setContent(initialContent.charAt(i));
                tape.moveRight();
            }
            tape.moveLeft();  // move back over last character written
        }
        ButtonListener listener = new ButtonListener();
        tapePanel = new TapePanel();
        tapePanel.setPreferredSize(new Dimension(500, 130));
        tapePanel.setFont(new Font("Serif", Font.PLAIN, 24));
        tapePanel.setBackground(new Color(180, 180, 255));
        tapePanel.setBorder(BorderFactory.createLineBorder(Color.BLUE, 2));
        moveLeftButton = new JButton("Left");
        moveLeftButton.addActionListener(listener);
        moveRightButton = new JButton("Right");
        moveRightButton.addActionListener(listener);
        setContentButton = new JButton("Set");
        setContentButton.addActionListener(listener);
        contentInput = new JTextField(1);
        contentInput.setText("" + tape.getContent());
        contentInput.setFont(new Font("Serif", Font.PLAIN, 18));
        contentInput.addActionListener(listener);
        JPanel bottom = new JPanel();
        bottom.add(moveLeftButton);
        bottom.add(moveRightButton);
        bottom.add(Box.createHorizontalStrut(15));
        bottom.add(new JLabel("Content:"));
        bottom.add(contentInput);
        bottom.add(setContentButton);
        setLayout(new BorderLayout());
        add(tapePanel, BorderLayout.CENTER);
        add(bottom, BorderLayout.SOUTH);
    }
}

Expressions.java

package turing;

/**
 * A class for experimenting with expression trees.  This class includes 
 * a nested abstract class and several subclasses that represent nodes in
 * an expression tree.  It also includes several methods that work with these
 * classes.
 */
public class Expressions {
	
	/**
	 * The main routine tests some of the things that are defined in this class.
	 */
	public static void main(String[] args) {
		System.out.println("Testing expression creation and evaluation...\n");
		ExpNode e1 = new BinOpNode('+', new VariableNode(), new ConstNode(3));
		ExpNode e2 = new BinOpNode('*', new ConstNode(2), new VariableNode());
		ExpNode e3 = new BinOpNode('-', e1, e2);
		ExpNode e4 = new BinOpNode('/', e1, new ConstNode(-3));
		System.out.println("For x = 3:");
		System.out.println("   " + e1 + " = " + e1.value(3));
		System.out.println("   " + e2 + " = " + e2.value(3));
		System.out.println("   " + e3 + " = " + e3.value(3));
		System.out.println("   " + e4 + " = " + e4.value(3));
		System.out.println("\nTesting copying...");
		System.out.println("   copy of " + e1 + " gives " + copy(e1));
		System.out.println("   copy of " + e2 + " gives " + copy(e2));
		System.out.println("   copy of " + e3 + " gives " + copy(e3));
		System.out.println("   copy of " + e4 + " gives " + copy(e4));
		ExpNode e3copy = copy(e3);  // make a copy of e3, where e3.left is e1
		((BinOpNode)e1).left = new ConstNode(17);  // make a modification to e1
		System.out.println("   modified e3: " + e3 + "; copy should be unmodified: " + e3copy);
		System.out.println("\nChecking test data...");
		double[][] dt = makeTestData();
		for (int i = 0; i < dt.length; i++) {
			System.out.println("   x = " + dt[i][0] + "; y = " + dt[i][1]);
		}
	}
	
	/**
	 * Given an ExpNode that is the root of an expression tree, this method
	 * makes a full copy of the tree.  The tree that is returned is constructed
	 * entirely of freshly made nodes.  (That is, there are no pointers back
	 * into the old copy.)
	 */
	static ExpNode copy(ExpNode root) {
		if (root instanceof ConstNode)
			return new ConstNode(((ConstNode)root).number);
		else if (root instanceof VariableNode)
			return new VariableNode();
		else {
			BinOpNode node = (BinOpNode)root;
			// Note that left and right operand trees have to be COPIED, 
			// not just referenced.
			return new BinOpNode(node.op, copy(node.left), copy(node.right));
		}
	}
	
	/**
	 * Returns an n-by-2 array containing sample input/output pairs. If the
	 * return value is called data, then data[i][0] is the i-th input (or x)
	 * value and data[i][1] is the corresponding output (or y) value.
	 * (This method is currently unused, except to test it.)
	 */
	static double[][] makeTestData() {
		double[][] data = new double[21][2];
		double xmax = 5;
		double xmin = -5;
		double dx = (xmax - xmin) / (data.length - 1);
		for (int i = 0; i < data.length; i++) {
			double x = xmin + dx * i;
			double y = 2.5*x*x*x - x*x/3 + 3*x;
			data[i][0] = x;
			data[i][1] = y;
		}
		return data;
	}
	
	
	//------------------- Definitions of Expression node classes ---------
	
	/**
	 * An abstract class that represents a general node in an expression
	 * tree.  Every such node must be able to compute its own value at
	 * a given input value, x.  Also, nodes should override the standard
	 * toString() method to return a fully parameterized string representation
	 * of the expression.
	 */
	static abstract class ExpNode {
		abstract double value(double x);
		// toString method should also be defined in each subclass
	}
	
	/**
	 * A node in an expression tree that represents a constant numerical value.
	 */
	static class ConstNode extends ExpNode {
		double number;  // the number in this node.
		ConstNode(double number) {
			this.number = number;
		}
		double value(double x) {
			return number;
		}
		public String toString() {
			if (number < 0)
				return "(" + number + ")"; // add parentheses around negative number
			else
				return "" + number;  // just convert the number to a string
		}
	}
	
	/**
	 * A node in an expression tree that represents the variable x.
	 */
	static class VariableNode extends ExpNode {
		VariableNode() {
		}
		double value(double x) {
			return x;
		}
		public String toString() {
			return "x";
		}
	}
	
	/**
	 * A node in an expression tree that represents one of the
	 * binary operators +, -, *, or /.
	 */
	static class BinOpNode extends ExpNode {
		char op;  // the operator, which must be '+', '-', '*', or '/'
		ExpNode left, right;  // the expression trees for the left and right operands.
		BinOpNode(char op, ExpNode left, ExpNode right) {
			if (op != '+' && op != '-' && op != '*' && op != '/')
				throw new IllegalArgumentException("'" + op + "' is not a legal operator.");
			this.op = op;
			this.left = left;
			this.right = right;
		}
		double value(double x) {
			double a = left.value(x);  // value of the left operand expression tree
			double b = right.value(x); // value of the right operand expression tree
			switch (op) {
			case '+': return a + b;
			case '-': return a - b;
			case '*': return a * b;
			default:  return a / b;
			}
		}
		public String toString() {
			return "(" + left.toString() + op + right.toString() + ")";
		}
	}

}

Rule.java

package turing;


/**
 * Represents one of the rules of a Turing Machine.
 * The rule applies when the machine's state is equal to currentState and
 * the character in the current cell on the tape is equal to currentContent.
 * The rule says that the machine will change to state newState, will
 * write newContent into the current cell on the tape, and will then move
 * eitehr to the left or to the right on the tape, depending on whether
 * the value of moveLeft is true or false.
 */
public class Rule {

    public int currentState;
    public char currentContent;
    public int newState;
    public char newContent;
    public boolean moveLeft;

    /**
     * Create a rule with default values for the instance variables.
     */
    public Rule() {
    }

    /**
     * Create a rule with specified values for the instance variables.
     */
    public Rule(int currentState, char currentContent, int newState, char newContent, boolean moveLeft) {
        this.currentState = currentState;
        this.currentContent = currentContent;
        this.newState = newState;
        this.newContent = newContent;
        this.moveLeft = moveLeft;
    }
}

TuringMachine.java

package turing;

import java.util.ArrayList;

/**
 * This class represents Turing machines.  A Turing machine is a simple
 * computing device that moves moves back and forth along a Tape
 * (see {@link Tape}), reading and writing characters.  The machine
 * has a state, which is represented as an integer.  It also has
 * a program, which consists of a list of rules (@see {@link Rule}).
 */
public class TuringMachine {

    private ArrayList<Rule> rules = new ArrayList<Rule>();  // This machine's program.

    /**
     * Adds one rule to the machine's program.
     *
     * @param rule A non-null rule to be added to the program.  A null
     *             value will not cause an immediate error, but will produce NullPointExceptions
     *             when run() method is called.
     */
    public void addRule(Rule rule) {
        rules.add(rule);
    }

    /**
     * A convenience method for adding an entire array of rules to this machine's program.
     * This method simply calls {@link #addRule(Rule)} for each rule.
     *
     * @param rules The array of rules that are to be added to the program.
     *              Each rule should be non-null.
     */
    public void addRules(Rule[] rules) {
        for (Rule rule : rules)
            addRule(rule);
    }

    /**
     * Run this Turing machine on a given Tape.  The machine starts in state
     * zero and continues as long as the state is greater than or equal to
     * zero.  At each step of the computation, it finds the applicable rule
     * in its program (the one whose currentState variable matches the machine's
     * current state and whose currentContent value matches the content of
     * the current Cell on the tape), and it executes the action part of the
     * rule (by setting the state of the machine to the rule's newState
     * variable, and setting the content of the current Cell to the rule's
     * newContent variable, and moving either left or right, depending on the
     * value of the rule's moveLeft variable.  (See {@link Rule}.)
     * Note that it is possible for this method to run forever, if the
     * state of the machine never becomes negative.
     *
     * @param tape The tape on which this machine will run.  The position of
     *             the current cell on the tape and the content of all the cells on the
     *             tape when this method is called constitute the input to the machine's
     *             computation.
     * @return the content of the tape at the end of the computation.  The return
     * value is obtained by calling {@link Tape#getTapeContents()}.
     * @throws IllegalStateException if at any point during the computation,
     *                               no applicable rule can be found.  This is taken to indicate a bug in the
     *                               machine's program.
     */
    public String run(Tape tape) throws IllegalStateException {
        int currentState = 0;
        while (currentState >= 0) {
            char currentContent = tape.getContent();
            Rule applicableRule = null;
            for (Rule rule : rules) {
                if (rule.currentContent == currentContent && rule.currentState == currentState) {
                    applicableRule = rule;
                    break;
                }
            }
            if (applicableRule == null)
                throw new IllegalStateException("Cannot find an applicable rule; tape contents = "
                        + tape.getTapeContents());
            currentState = applicableRule.newState;
            tape.setContent(applicableRule.newContent);
            if (applicableRule.moveLeft)
                tape.moveLeft();
            else
                tape.moveRight();
//			System.out.println(applicableRule.currentState + " "+ applicableRule.currentContent 
//					+ " " +applicableRule.newState + " " +applicableRule.newContent 
//					+ " " +applicableRule.moveLeft);  // for testing.
        }
        return tape.getTapeContents();
    }
}

TestTuringMachine.java

package turing;


/**
 * A test program for the TuringMachine class.  It creates three machines and runs them.
 * The output from the program indictes the expected behavior.
 */
public class TestTuringMachine {

    public static void main(String[] args) {

        TuringMachine writeMachine = new TuringMachine();

        writeMachine.addRules(new Rule[]{  // writes Hello on the tape then halts
                new Rule(0, ' ', 1, 'H', false),
                new Rule(1, ' ', 2, 'e', false),
                new Rule(2, ' ', 3, 'l', false),
                new Rule(3, ' ', 4, 'l', false),
                new Rule(4, ' ', -1, 'o', false)
        });

        System.out.println("Running machine #1.  Output should be:  Hello");
        String writeMachineOutput = writeMachine.run(new Tape());
        System.out.println("Actual output is:                       " + writeMachineOutput);

        TuringMachine badMachine = new TuringMachine();
        badMachine.addRules(new Rule[]{  // writes ERROR on the tape then fails
                new Rule(0, ' ', 1, 'R', true),
                new Rule(1, ' ', 2, 'O', true),
                new Rule(2, ' ', 3, 'R', true),
                new Rule(3, ' ', 4, 'R', true),
                new Rule(4, ' ', 5, 'E', true) // no rule for state 5!
        });

        System.out.println("\nRunning machine #2.  Should throw an IllegalStateExcpetion.");
        try {
            badMachine.run(new Tape());
            System.out.println("No Error was thrown.");
        } catch (IllegalStateException e) {
            System.out.println("Caught Illegal Argument Exception, with error message:");
            System.out.println(e.getMessage());
        }

        String input = "aababbbababbabbaba";  // a string of a's and b's for input to the copy machine
        Tape tape = new Tape();
        for (int i = 0; i < input.length(); i++) {
            tape.setContent(input.charAt(i));
            tape.moveRight();
        }
        tape.moveLeft();  // now, input is written on the tape, with the machine on the rightmost character

        TuringMachine copyMachine = new TuringMachine();  // copies a string of a's and b's;
        // machine must start on leftmost char in the string
        copyMachine.addRules(new Rule[]{
                new Rule(0, 'a', 1, 'x', true),  // rules for copying an a
                new Rule(1, 'a', 1, 'a', true),
                new Rule(1, 'b', 1, 'b', true),
                new Rule(1, ' ', 2, ' ', true),
                new Rule(2, 'a', 2, 'a', true),
                new Rule(2, 'b', 2, 'b', true),
                new Rule(2, ' ', 3, 'a', false),
                new Rule(3, 'a', 3, 'a', false),
                new Rule(3, 'b', 3, 'b', false),
                new Rule(3, ' ', 3, ' ', false),
                new Rule(3, 'x', 0, 'x', true),
                new Rule(3, 'y', 0, 'y', true),

                new Rule(0, 'b', 4, 'y', true),  // rules for copying a b
                new Rule(4, 'a', 4, 'a', true),
                new Rule(4, 'b', 4, 'b', true),
                new Rule(4, ' ', 5, ' ', true),
                new Rule(5, 'a', 5, 'a', true),
                new Rule(5, 'b', 5, 'b', true),
                new Rule(5, ' ', 7, 'b', false),
                new Rule(7, 'a', 7, 'a', false),
                new Rule(7, 'b', 7, 'b', false),
                new Rule(7, ' ', 7, ' ', false),
                new Rule(7, 'x', 0, 'x', true),
                new Rule(7, 'y', 0, 'y', true),

                new Rule(0, ' ', 8, ' ', false),  // rules that change x and y back to a and b, then halt
                new Rule(8, 'x', 8, 'a', false),
                new Rule(8, 'y', 8, 'b', false),
                new Rule(8, ' ', -1, ' ', true)
        });

        System.out.println("\nRunning machine #3.  Output should be: " + input + " " + input);
        String copyMachineOutput = copyMachine.run(tape);
        System.out.println("Actual output is:                      " + copyMachineOutput);

    }
}

2. Outputs

The outputs of TestTape.java:

Tape Conents:  Hello World
Final position at the W

Process finished with exit code 0

The outputs of TestTapeGUI.java:

The outputs of TestTuringMachine.java:

Running machine #1.  Output should be:  Hello
Actual output is:                       Hello

Running machine #2.  Should throw an IllegalStateExcpetion.
Caught Illegal Argument Exception, with error message:
Cannot find an applicable rule; tape contents = ERROR

Running machine #3.  Output should be: aababbbababbabbaba aababbbababbabbaba
Actual output is:                      aababbbababbabbaba aababbbababbabbaba

Process finished with exit code 0

Word count: 3741

References

1.UoPeople. (2020). Lab 5: Tape for a Turing Machine (Doubly-linked List).
https://my.uopeople.edu/mod/page/view.php?id=279538

​

---

This is the ending, thanks for reading.

---