224 TURING MACHINES
4. Show that the following functions defined on (a, b)* are primitive recur-
sive:
(a) fi(x,y) = [z is a subsequence of y], where x = 1x111~12 l **xk is a
subsequence of y = yry2 l l. ym if there exists a sequence of integers
1 < - nl < n2 < l l l <nk<msuchthaty, - i =xifori=l,...,k.
(b) f2(x, Y) = th e number of occurrences of x as a substring in y.
(c) f3(2) = the string obtained from x by replacing each occurrence
of ba in x by ub. For instance, jā,,(babab) = ububb.
(d) f4(x) = the length of the longest w such that both w and wR
occur as substrings of x.
5. Show that every context-free language is primitive recursive.
6. Let f(k,O) = lek], and f(k,n) = th e nth digit to the right of the decimal
point of the decimal expansion of ek, where e = C,ā-, l/n!. Show that
f is a recursive function. Is f a primitive recursive function?
7. Let G be a grammar over alphabet C. Show that the following functions
gl, g2, g3 are partial recursive:
( 1 a
(b)
( ) C
cd)
g1 cx> = the minimum number of steps in a derivation of x if
x c L(G), and gl(x) f, otherwise.
g2 (4 = the minimum length (the number of symbols) of a deriva-
tion of x if x E L(G), and 92(x) t, otherwise.
93(x, Y) = 1 if there is a derivation of x that is shorter than any
derivation of y, if both x and y are in L(G), and 93(x, y) T, other-
wise.
1 if!l3(& Y) 4,Let 94(x, Y) = { (^0) otherwise. Is g4 a recursive function?
8. (Ackermunn function) Define a function A : N2 + N as follows:
A(O,n) = {