Problem Solving in Automata, Languages, and Complexity

4.8 Partial Recursive Functions 217

Case 1. There exists an integer j, 0 < j < n, such that ij < k and
it = k for alI e = O,l,.. .,j - 1. That is, G = ~7 n •~i~+~si~sk l sk. Then,
Y = sin •*~i~+~~i~+l~l l. l sl. We verify that

n j-1

kj e=o

n j n j

- - ~i~=ke+~ke=~,i~~ke+~loke-l,

kj kl kj e=o

It follows that

cl(y) = 2

j-l

it l k” + (ij + 1) l kj + x 1 l k”.

kj+l A!=0

Case 2. x = sksk l l ‘Sk (of length 1x1 = n-t-l). Then, we have y = SlSl l l l Sl

(of length lyl = n + 2). By the inductive hypothesis,

n n+l

and so
n+l
r’(y) = x 1 l ke.
e=o

cl

In practice, we may view the string si,si,-,... sil siO as a new base-k rep-
resentation of the integer m = LC~ (x). We illustrate this idea in the following
example.

Example 4.41 (a) Suppose C = { 1,2,... ,8,9, X} with the ordering 1 4 2 4

-+8+9+X. Th en, we may treat every word in C* that contains no X as

the ordinary decimal expansion of an integer. For instance, let x be the string

3897. Then, from the above theorem, L-‘(X) = 3103+8102+910+7 = 3897.
      If a string x E C contains symbol X, we can still easily calculate L-~(X) by
      treating X as 10. For instance, ~-l(3XX7) = 3103+10102+10*10+7 = 4107.

(b) Suppose C = {O,l} and 0 4 1. Th en, L(n) is just the ordinary binary

expansion of n+ 1 with the leading 1 removed. For instance, let n = 89. Then

the ordinary binary expansion of n+ 1 is 1011010 (i.e., n + 1 = 1. 26 + 1 l 24 +

1. 23 + 1. 2 = 90). By identifying 0 as s1 and 1 as ~2, we can verify that

L-1(011010) = 1*25+2*24+2*23+1*22+2*2+1

=1*25+1*24+1*23+1*22+1*2+1

+ 1 l 24 + 1 l 23 + 1 l 2

=l~26+1~24+1~23+1~2-1=n.