编程代写|CS 3500 – Programming Languages & Translators Exam #3

这是一篇来自英国的关于高级对象定向C语言的C语言代写

 

Coursework 1 – C++

What to submit: You are meant to submit 10 files (ordered by which task asks you to start implementing them) – in each case, you are meant to submit a .h file and the corresponding .cpp file for each of the below:

  • TuringMachineState
  • DenseTuringMachine
  • TuringTape
  • MenuSystem
  • SparseTuringMachine

Note, submitting the .h file is mainly meant to be a help for you, since it will let you add in other methods and so on into the classes if you so wish and a baseline .h (except for TuringMachineState, where part of the task is to write one) is provided that contains everything required, but again, you may wish to add more. You should in general not remove anything from the .h files however, since, as mentioned, they just contain the code required for each task. You may add in any number of additional method/constructor/similar you wish, but if it is not required to have a constructor and you add one, also add in an empty constructor, because otherwise the way it will be marked might fail and you will lose points. Besides the mentioned files you submit,your program will be compiled with two additional files, namely TuringMachine.h and Main.cpp (the latter only intuitively – it will really be compiled with a subset, depending on which task you completed – this is to ensure that you can get points for having done e.g. only the first task, even though the Main file provided will require all parts to be done). Penalties for late work will be applied following the Code of Practice on Assessment. Your grade and penalty are based on your last submission.

Work alone: You must work alone on the assignment. Plagiarism checks will be run!

Tests and grading: Each task will have associated some public tests and some private tests (besides the final task, task 9, which will only have private tests). The public tests are described in secondary files, one for each task, but you will be graded based on how you do on the private tests (mainly to ensure you are not hardcoding the answer, except for the last task, task 9, where figuring out what to look for is also important). Each task also gives some % of the mark for this assignment, mentioned in the title of the task.

You will be told (by CodeGrade) which of the public tests you passed whenever you submit – it will take a few minutes to run, depending on the number of people trying to submit at the same time. You are therefore heavily suggested to submit a number of times – before the deadline – and change your submission based on how it went! Your grade will be based on the outcome of the tests on your last submission.

The compilation of your code will be done using clang++ with the options:

-Wall -std=c++11

The former gives more warnings, and the latter ensures you can only do C++11 as is the case by the baseline setup of Visual Studio 2019 you were meant to install/which is installed in the labs.

Tests cannot be done without some assumed behaviour. Some of the tests for different tasks (both public and private) assume that you have done the earlier tasks.

If you have not, it is unlikely that you can succeed on that test/task. This was kept to a minimum, but still necessary at times. Each task will tell you which previous task (if any) you need to have done.

Project Overview

You will create a small interactive program to input a Turing Machine and run it, while being able to display the tape and current state). The project consists of 9 tasks, see below. It is likely easier to do the tasks in order (and besides that, as mentioned, some of the tests for some of the tasks assume this has been done). Each task builds on the previous ones. Do as much as you can and then package your project for submission. Begin by downloading the Visual Studio project template for this assessment.

Read through this entire document before you start coding, so you’re aware of all parts and the overall structure of the program. Your solution should demonstrate your knowledge of C++. Important: Each task requires you to add extra code and each part is expected to work also at the end.

Task 1 – TuringMachineState Class Definition – 5%

Create a TuringMachineState class (incl. both a .h file and a .cpp file) that stores:

  • a current state (a non-negative integer, implemented as an integer)
  • a current content (a non-negative integer, implemented as an integer)
  • a next state (a non-negative integer, implemented as an integer)
  • a next content (a non-negative integer, implemented as an integer)
  • a move direction (either the string “->” or the string “<-“)

Note, while the parameters describe some requirements for the different parameters,you do not need to check that, but may simply assume that the input is such.

Declare and define a public constructor TuringMachineState that takes each parameter, in that order, and stores them in the object.

Create also public methods: getCurrentState(), getCurrentContent(), getNextState(), getNextContent(), getMoveDirection(). They should return the value of the corresponding parameter.

Task 2 – Turing machine state I/O – 5%

Implement the << and >> operators so you can output and input a Turing Machine state object with the following string format:

2 5 4 3 ->

In other words, the Turing machine states are output/input by outputting/inputting the parameters in order. For this task, you do not need to do any input validation or error handling. Assume the input has been validated elsewhere. For obvious reasons, you should do task 1 before this one.

Task 3 – Comparison Operators – 5%

Implement comparison operators (<, >, and ==) for the TuringMachineState class.

These should work lexicographically based on current state and current content: I.e. if the current state differs, then if first current state > second current state, then the first > second. Otherwise, if the current states are equal, if the first current content > second current content, then first > second (similar for the others – equality requires just that they have equal current state and current content). For obvious reasons, you should do task 1 before this one.

About Turing machines

In the remaining parts of the assessment, we are looking at Turing machines.

A Turing machine is a set of Turing machine states, where, for each pair of numbers x, y, there is at most one TuringMachineState with current state x and current content y (i.e. getCurrentState()=x and getCurrentContent()=y). You then also have a tape (for this assessment, initially filled with 0s) and a current position of the tape head and a current state of the Turing machine (for this assessment, both are initially 0 – you may assume that both can be stored in ints). It then repeatedly does a step as follows, until termination, (or indefinitely if that does not happen):

  1. Check that the current position of the tape head is at least 0 and below the size of the tape (the latter only if the tape is supposed to be finite). If not, you are done and should terminate with an error message.
  1. Find the TuringMachineState with current state (i.e. the output of getCurrentState()) equally to the current state of the Turing machine (i.e. the first time you should find state 0) and the current content equal to the content of the tape at the position of the tape head. If there is no such state, you are done and can terminate with an error message.
  1. Update the current state of the Turing machine to be the next state of the TuringMachineState (i.e. getNextState()), the content at the current position of the tape head to be the next content of the TuringMachineState (i.e. getNextContent()), and afterwards increment the position of the tape head if the move direction of the TuringMachineState is -> otherwise, if it is <-, decrement

The remaining tasks are about implementing the storage of the TuringMachineStates so that we can do item 2 fast and implementing the finite/unbounded tape so that we can do item 3 fast (item 1 should be quite straightforward).

Task 4 – DenseTuringMachine – 10%+5%=15%

In this task, we are trying to implement item 2 in the case where, if you put

TuringMachineState

into entry (2,5) – i.e. the entry of the same current state and current content – of a matrix and similar for the other TuringMachineStates, you would get a dense matrix (meaning that a large fraction of entries contains a TuringMachineState).

The implementation should be done in the files for DenseTuringMachine.cpp and a corresponding .h file is provided (that you may wish to modify), should implement DenseTuringMachine, which should be a child of the abstract class TuringMachine. In particular, it should implement the following constructor and functions:

  • DenseTuringMachine(int x, int y), creates a new DenseTuringMachine in which each TuringMachineState has current state <= x and current content <= y (when x and y are non-negative).
  • TuringMachineState* find(int x, int y), which should return the TuringMachineState that has current state x and current content y or NULL if no such TuringMachineState exist at the time the command is run
  • void add(TuringMachineState s), which should add s to the states that could be found.
  • vector<TuringMachineState>* getAll(), which should return a pointer to the vector of all TuringMachineStates, in some order.

You are meant to implement these so that the total time to run the constructor followed by any z functions runs in total time O(xy+z). This will be verified by hand and gives 10%. You won’t get the 10% if the functions aren’t implemented basically correctly (i.e.if nearly correct, then fine, but if it is not close to correct then no).

Besides that, you also need to implement the functions correctly and will receive the last 5% for that. For obvious reasons, you should do task 1 before this one.

Task 5 – TuringTape – 10%+5%=15%

In this task, we implement a finite Turing Tape (we will do the infinite one later in task 8).

The implementation should be done in the file TuringTape.cpp (a corresponding .h file is provided, but you may wish to add more code to it), which should implement TuringTape and the following constructor and virtual functions:

TuringTape(int n), which should construct a tape for a Turing machine with n spaces, initially all 0 and initially with current position 0. n should be positive (or, later, -1).

  • bool moveRight(), which should increment the current position and output false iff the current position afterwards is >n (or <0)
  • bool moveLeft(), which should decrement the current position and output false iff the current position is <0 (or >n)
  • int getContent() which should return the content at the current position. If the current position is outside the tape, return 0.
  • void setContent(int c), which should set the current content to c. If outside the tape, this should do nothing.
  • int getPosition(), which should return the current position.
  • operator<<(std::ostream& out,const TuringTape& T), which should output the content of the tape from 0 until the highest position that has been/is the current position (you will likely need a variable for this – we do this instead of always outputting the full tape to make the change to infinite tape easier). Note that this should be a friend and not actually a part of TuringTape.

It is expected to be based on an iterator that can move left and right in O(1) time (output does not necessarily need to use the same iterator though). You will get 10% for doing so and this will be checked by hand. Like in Task 4, you won’t get the 10% if the functions aren’t implemented basically correctly.

You will get the remaining 5% for implementing the functions correctly.

Task 6 – Menu – 25%

In this task, we are implementing a command line program for creating and executing Turing machines and is expected to be based on the earlier classes. You should do the implementation in main.cpp and a corresponding .h file is provided, but you may wish to add more code, and the program should run when void menu() is called.

Specifically, you are meant to create a program that initially displays:

And then waits for input of an int. You are then expected to use that to create the tape.

You would also be expected to create a variable for the current state, which should initially be 1.