CM20019Computation III:
Formal Logic and Semantics
2007
Exercise sheet 2Solutions
Problem 1
=========
(P,B), where
P = { B > BB ,
B > BaB ,
B > b } .
Problem 2
=========
Yes. By definition, there exists a Turing machine M associated to the given computable function. We can simulate M by a string rewriting system P as follows.
1) Consider the nonblank portion of the input tape of M as a string S, and suppose that the head of M reads the leftmost symbol of S.
2) To every state in M, associate a unique symbol, outside of the tape alphabet.
3) For every transition in M such that the head moves towards the right or stays put, associate a rule in P: for example, rule qa > br stands for: when in state q, reading a, write b, move right and get into state r.
4) For every transition in M such that the head moves left, and for every symbol in the tape alphabet, associate a rule in P: for example, rule cqa > rcb stands for: when in state q, reading a, write b, move left and get into state r.
5) No rules in P exists, corresponding to final states of M.
This way, given string qS, where q is the initial state of M and S is its initial tape string, each transition of P corresponds to a transition of M, and the string obtained is terminal iff M is in a terminal state. The output of the function is the terminal string so obtained, minus the symbol of the final state. (If that symbol disturbs, it can be moved away by rules that move it to the left, or right.)
Problem 3
=========
P = { a > cH ,
H1 > 1OH ,
Hb > de ,
O1 > 1O ,
Od > d1 } .
Problem 4
=========
Let and be two consecutive Fibonacci numbers, expressed in unary form as a sequence of 1s, for example, and can be 11111 and 11111111.
We design a grammar that produces strings according to the following scheme, whose main mechanism (vertically, in the picture) is an L moving to the right, becoming an R, moving to the left, becoming an L, etc.:
L b c > P b c >*

V
a b R > a b Q >*
 .
V
L b c > P b c >*

V
...
The horizontal derivations produce terminal strings corresponding to unary Fibonacci numbers. So, we interpret L, R, P and Q as commands:
L: copy from the left or end left;
R: copy from the right or end right;
P: end left;
Q: end right.
We can write the following rules for `end left' and `end right':
S1 = { L > P , R > Q ,
P1 > 1P , 1Q > Q1 ,
Pb1 > Pb , 1bQ > bQ ,
1Pbc > 1 , abQ1 > 1 } .
We can write the following rules for `copy from the left' and `copy from the right' (see previous exercise):
S2 = { L > aCH , R > KDc ,
H1 > 1OH , 1K > KO1 ,
Hb > BU , bK > VB ,
O1 > 1O , 1O > O1 ,
OB > B1 , BO > 1B ,
C1 > 1C , 1D > D1 ,
CB > b , BD > b ,
U1 > 1U , 1V > V1 ,
Uc > R , aV > L } .
The interpretation of O is `a 1 that must be on the other side of b'. The purpose of C and D is to make sure that all Os became 1s on the right side, when B is transformed into b.
The requested grammar is (S1 U S2, ab1R).