12 A. YU. OLSHANSKII AND M. V. SAPIR

We also define the set of basic letters X which consists of letters Zj where

z G {K, L, P, i?}, j = 1,..., N. Letters from

X~l

are also called basic letters.

There exists a natural map from X U X~l to X U X~~l which forgets indexes

r and i. If z is a basic letter, r E £, i E {1,2,3,4,5} then z(r, i) G X. If

J7 is a word in X and other letters, r E £, i E {1,2,3,4,5} then U(r,i) is

a word obtained from U by replacing every letter z E X by z{r,i). The

parameters r and i in the letter z(r,i) or in the word U(r,i) will be called

the £-coordinate and the ^-coordinate of the word.

The set A of tape letters of the machine S consists of letters a{(z) where

i = l, ...,m, z G X. For every z G X we define ^l(^) as the set of all di(z),

i = 1, ...,m.

Let E be the following word (considered as a cyclic word):

K^^R^-'R^P-'L^KSLSPSRSK^1

K~l

/ ?

- 1

P

_ 1

T

_ 1

(2.2)

Notice that for every basic letter z precisely one of z and z

_ 1

occurs in the

word E. The word E = E(0,1) will be called the hub.

For every z G Xl}X~l by Z- we denote the letter immediately preceding

z in the cyclic word E or in E

_ 1

. This definition is correct because every

basic letter occurs exactly once in the word E or its inverse (see remark

above). If z' — Z- then we set z —

zf+.

Similarly we define Z- and z+ for

z G X. Notice that for every j = 1,..., iV,

(LJ

and

(Rjh =

Kj

Kilr

Kili

Kj

if j is odd,

if j is even.

if j is odd,

if j is even.

To simplify the notation and avoid extra parentheses, we shall denote {Lj)-

by Lj and (i?j)+ by Kj. We also define A(z"1) for z G X by setting ^ ( z - 1 ) =

A(zJ).

The language of admissible words of the machine S consists of all reduced

words of the form W = yiUiy2U2...ytUtyt+i where yi, ...,yt+i ^

X±:L,

'Ui are

words in A(yi)1 2 = 1,2,..., t, and for every i = 1, 2,..., t, either ^

+

i = (yz)+

or i/i+i =

y~l.

(Here = is the letter-for-letter, or graphical, equality of

words.) The projection of yi...yt+i onto X will be called the base of the

admissible word W. The subword yiuiyi+i is called the yiyi+i-sector of the

admissible word W, i = 1,2 The word u\ is called the inner part of the

yiyi+i-sectov. We assume that the inner part of any zLj-, zPj- or i?j2:-sector

of W and W~l is a positive word (z G X), that is it does not contain a~1

for any a £ A. Notice that if W is an admissible word for S then W~l is an

admissible word as well.