Consider the language of arithmetic expressions as a string of additions and/or

subtractions of natural numbers. For example, 23+6-25+0 or 990 or 1-2 are

valid expressions.

(a) Outline an implementation-level description of a Turing Machine to recog-

nise this language. Remember that for an implementation-level description

you do not have to give a formal specication of the machine's moves, but

only to explain the algorithm in plain English explaining the series of steps

the machine would use for this calculation.

(b) Draw a diagrammatic state machine model showing all the moves of your

Turing Machine.

(c) State carefully any assumptions you have made.