CSC344 – Assignment 1

Microproject

Write a C program which reads input from the user and based on their input creates and populates a two dimensional array of structs. The array represents locations on a shelving unit (rows = shelves, columns = locations on the shelves). The struct will represent an item, and include name and quantity. Once users have finished entering the items, they should be able to retrieve them, and have them printed to the screen, using some command. 

Main Project

In this assignment you will implement a Turing Machine (TM) in C. A TM consists of:

• An infinite tape, divided into cells
• A read/write head, which is capable of reading the current cell, writing new values in the current cell, and moving left or right
• A state register
• A finite table of instructions which, given the current state of the machine, and the currently being read tape cell, tells the machine to: 
  1. Write some (possibly the same) item into the cell
  2. Move the head left or right
  3. Change to some (possibly the same) state

For a tape, you will implement a doubly linked list. As you move the tape head, you will update a reference to the current cell seen by the tape head. Initial tape contents will be provided by an input file. If you need more cells during processing you should create them on the fly. You may use the ASCII character ‘B’ to indicate a blank cell. The set of instructions will also be provided in the input file. The table of instructions will be represented as a two dimensional array, where the rows are states and the columns are ASCII characters read from the tape. Given the current state and the current character being read by the read/write head, the machine looks up an instruction in this array.

Below is a sample input file which adds two unary numbers together. Given an initial tape input of 111B1111, representing the numbers 3 and 4 separated by a blank, the machine walks to the end of the tape, changing the middle B to a 1, and changing the last 1 to a B. The result is 1111111, unary 7. 

The input file has the following specification:
Line 1: Initial tape content
Line 2: Number of states
Line 3: Start state
Line 4: End state
Remaining lines represent the state machine. Each line is has 5 parts:
State, ReadVal, WriteVal, MoveDirection, NewState

Your program should take a single command line argument, the name of the file to be read.

Given the above input file, the program should output unary 7, perhaps with some blanks on each end of the tape. My version produces the following:

You may use any built-in C library functions in your program, but you must implement the linked list yourself. You may not use code found on the internet.

Suggested Development Environment

CLion (free for students)