T Naughton, NUIM
Back to SE307 home

Lab 4 - Mechanical reasoning about machines

In this lab you will begin work on the concept of using a machine to analyse another machine.

Consider the following programming language. Each valid program (P) contains an initialiser statement (I) followed by a list of statements (L). I assigns to a variable a nonzero value in unary. L is a (possibly empty) list of increment statements. There is only one variable; it is called x. There are no spaces (or carriage returns) in valid programs.

Here is the grammar that defines the programming language. The green symbols denote nonterminals and black symbols denote terminals. As usual, e is the empty string.

P -> IL
I -> V=N;
L -> e | S | SL
S -> V++;
V -> x
N -> 1 | NN

For example, the following are valid programs: x=1111;x++;x++; (assign x the value 4 and increment twice), x=1;x++; (assign x the value one and increment once), and x=111; (assign x the value 3 and halt). We would say that each of these programs are "words in the language of valid programs".

Problem 4.1 Write a TM to syntax check programs from this programming language. Append a `T' to a program supplied as input if its syntax is correct and append an `F' otherwise. Assume that all inputs will be words over the alphabet {x, =, +, ;, 1}.

Problem 4.2 Write a TM to execute any program from this programming language and calculate the resulting value of the variable x. Initially, the tape head will be positioned at the beginning of the input. At halt, the value of x in unary should be written on the tape and the tape head positioned at the beginning of the value. For example, if presented with the following symbols on its input tape x=11;x++;x++; your TM should transform them into x=11;x++;x++;1111 before halting. Assume all programs passed as input to your TM are free of syntax errors.

Problem 4.3 In problem 4.1 you were effectively asked to write a TM to accept the language of valid programs. What language does your TM from problem 4.2 accept?