Lab 11 - Turing Machine

In this assignment you will design a Turing Machine in C++.

Programming Syntax

The programming syntax for the Turing machine consists of the following format:

# Setup
START_STATE_NAME,ACCEPT_STATE_NAME,REJECT_STATE_NAME

# Transition Rules
CURRENT_STATE,INPUT,NEW_STATE,OUTPUT,MOVE_DIRECTION

State names can be any valid ASCII string without whitespace characters.
INPUT and OUTPUT can be any valid ASCII character, with _ representing a blank.
MOVE_DIRECTION can be R for Right, L for Left, or S for Stay.

Example Program

A program for the machine that accepts strings that consist of 0's and 1's sorted correctly (00011, 0000, 111, 0111, 01, etc..) might look like this:

# Setup
start,accept,reject

# Start Rules
start,0,zero,0,R
start,1,one,1,R

# What happens after we've seen a 0
zero,0,zero,0,R
zero,1,one,1,R
zero,_,accept,_,R

# What happens after we've seen a 1
one,1,one,1,R
one,0,reject,0,R
one,_,accept,_,R

Program Output

When you launch the program, it should prompt you for the path to the rules file, then prompt you for an input string, then process the string through the machine described by the rules file.

At each step, it should print the step number and machine configuration, in the format:

u<state>v

Where <state> is the name of the state (including the angle brackets) and uv is the string, and the read/write head points to the first character of v. (For more information about the configuration string format, refer to pages 168-172 of your text)

At the conclusion of the run, it should print ACCEPT or REJECT accordingly. Remember that if the machine reaches a state for which it has no transition rule, it should reject by default.

Example Output

Here are a couple of example runs of the Turing Machine for the above sample code:

Turing Machine Simulator
Rules File: C:\Users\bob\Desktop\rules1.txt
Input String: 0001

Processing:
0. <start>0001
1. 0<zero>001
2. 00<zero>01
3. 000<zero>1
4. 0001<one>
5. 0001_<accept>
ACCEPT

Turing Machine Simulator
Rules File: C:\Users\bob\Desktop\rules1.txt
Input String: 0100

Processing:
0. <start>0100
1. 0<zero>100
2. 01<one>00
3. 010<reject>0
REJECT

Hints

You'll want to break this program up into small parts, get each part working, then move on to the next part.
Don't forget that your Turing machine should have infinite space on both sides of the input string. While we can't have truly "infinite" space in a modern computer, you should be able to move to the left of the first symbol of the input string if necessary (which it will be to complete the extra credit).

Extra Credit (20 Points)

Write a program that allows your Turing Machine to add two number together using the algorithm we discussed in class on Friday (continually decrease one number by 1 while increasing the other).

Your program should work with any two numbers of arbitrary length so long as they are separated by one blank.

Example

For the string: 12 15, the Turing machine's final configuration before accepting should be:

27 00<accept>

For the input string: 199 1, the Turing machine's final configuration before accepting should be:

200 0<accept>

For the input string: 99 10, the Turing machine's final configuration before accepting should be:

109 00<accept>

Starter Code

The following starter code contains functions for loading the rules file, and breaking each rule up into a vector of strings (a process called "tokenizing"):

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>

using std::fstream;
using std::string;
using std::vector;
using std::cout;
using std::endl;
using std::cin;

vector<string> loadInstructions() {

    vector<string> instructions;

    string filename;
    cout << "Rules File: ";
    getline(cin, filename);

    fstream fin(filename.c_str());
    if(!fin) {
        cout << "Error opening file " << filename << endl;
        return instructions;
    }

    string line;
    while(getline(fin, line)) {
        if(line.length() > 0 && line.at(0) != '#') {
            instructions.push_back(line);
        }
    }

    fin.close();
    return instructions;
}

vector<string> tokenizeString(string & str) {

    vector<string> tokens;

    int start = 0;
    for(int i = 0; i < str.length(); i++) {
        if(str.at(i) == ',') {
            tokens.push_back(str.substr(start, i - start));
            start = i + 1;
        }
        else if(i == str.length() - 1) {
            tokens.push_back(str.substr(start));
        }
    }

    return tokens;

}

int main() {

    // Get the rules
    vector<string> instructions = loadInstructions();

    // At this point instructions[0] should contain the 
    // start, accept, and reject state names
    //
    // instructions[1] to instructions[n] should contain the transition
    // instructions.

    // Print out the rules for verification:
    for(int i = 0; i < instructions.size(); i++) {
        cout << instructions[i] << endl;
    }

    // You can use the tokenizeString function to break each line up
    // into a vector of strings:

    // Example: tokenize rule 1:
    vector<string> ruleOneTokens = tokenizeString(instructions[0]);

    // Print out the tokens for verification:
    for(int i = 0; i < ruleOneTokens.size(); i++) {
        cout << ruleOneTokens[i] << endl;
    }

}

Grading

Out of 100 Points:

Your program sucessfully reads the input file: 30 Points.
Your Turing Machine sort of works: 20 Points.
Your Turing Machine works with the sample cases above: 50 Points.
You completed the Adder program and it works in your Turing Machine: 120 Points.

Submission

To submit your assignment, zip your C++ file(s) and upload them to mySVU.

CSC 240