124 Q Theory ofComputer Science
4.4 RECURSIVE AND RECURSIVELY ENUMERABLE SETS
The results given in this section will be used to prove £cs1 e" £0 in Section 9.7.
For defining recursive sets, we need the definition of a procedure and an
algorithm.
A procedure for solving a problem is a finite sequence of instructions
which can be mechanically carried out given any input.
An algorithm is a procedure that terminates after a finite number of steps
for any input.
Definition 4.14 A set X is recursive if we have an algorithm to determine
whether a given element belongs to X or not.
Defmition 4.15 A recursively enumerable set is a set X for which we have
a procedure to determine whether a given element belongs to X or not.
It is clear that a recursive set is recursively enumerable.
Theorem 4.3 A context-sensitive language is recursive.
Proof Let G = (V iV , I, P, S) and ,v E I*. We have to construct an algorithm
to test whether W E L(G) or not. If w = A, then W E L(G) iff S ~ A is in
P. As there are only a finite number of productions in P, we have to test
whether S ~ A is in P or not.
Let Iw I =n 2:: 1. The algorithm is based on the construction of a sequence
{Wd of subsets of (Vv u I)*. Wi is simply the set of all sentential forms of
length less than or equal to n. derivable in at most i steps. The construction
is done recursively as follows:
(i) W o = is}.
(ii) W i + 1 = Wi U {f3 E (Vv u I)*I there exists a in Wi such that a=:;> f3
and I f3 I ::;; n}.
W;'s satisfy the following:
(iii) Wi ~ W i + 1 for all i 2:: O.
(iv) There exists k such that W k = W k +!.
(v) If k is the smallest integer such that W k = W k + 1 , then W k =
{a E CVv u I}*IS :b a and lal : : ; ; n}.
The point (iii) follows from the point (ii). To prove the point (iv), we
consider the number N of strings over Vv u I of length less than or equal to
11. If IVv u I I = 111, then N = 1 + m + 111
2 + ... + mil since m
i is the number
of strings of length i over Vv U L. i.e. N =(m"+ I - 1)/(m - 1), and N is fixed
as it depends only on 11 and m. As any string in Wi is of length at most 11,
IWi I ::;; N. Therefore, W k = W k + 1 for some k ::;; N. This proves the point (iv).
From point (ii) it follows that W k = W k + 1 implies W k + 1 = Wk+2'
{a E CVv U L)* IS :b a. Ia I ::;; n} = WI U W 2 U
U W k U lV k + 1 ...
= W 1 U W 2 U
U W k
=W k from point (iii)
This proves the point (v).
4.4 RECURSIVE AND RECURSIVELY ENUMERABLE SETS
The results given in this section will be used to prove £cs1 e" £0 in Section 9.7.
For defining recursive sets, we need the definition of a procedure and an
algorithm.
A procedure for solving a problem is a finite sequence of instructions
which can be mechanically carried out given any input.
An algorithm is a procedure that terminates after a finite number of steps
for any input.
Definition 4.14 A set X is recursive if we have an algorithm to determine
whether a given element belongs to X or not.
Defmition 4.15 A recursively enumerable set is a set X for which we have
a procedure to determine whether a given element belongs to X or not.
It is clear that a recursive set is recursively enumerable.
Theorem 4.3 A context-sensitive language is recursive.
Proof Let G = (V iV , I, P, S) and ,v E I*. We have to construct an algorithm
to test whether W E L(G) or not. If w = A, then W E L(G) iff S ~ A is in
P. As there are only a finite number of productions in P, we have to test
whether S ~ A is in P or not.
Let Iw I =n 2:: 1. The algorithm is based on the construction of a sequence
{Wd of subsets of (Vv u I)*. Wi is simply the set of all sentential forms of
length less than or equal to n. derivable in at most i steps. The construction
is done recursively as follows:
(i) W o = is}.
(ii) W i + 1 = Wi U {f3 E (Vv u I)*I there exists a in Wi such that a=:;> f3
and I f3 I ::;; n}.
W;'s satisfy the following:
(iii) Wi ~ W i + 1 for all i 2:: O.
(iv) There exists k such that W k = W k +!.
(v) If k is the smallest integer such that W k = W k + 1 , then W k =
{a E CVv u I}*IS :b a and lal : : ; ; n}.
The point (iii) follows from the point (ii). To prove the point (iv), we
consider the number N of strings over Vv u I of length less than or equal to
11. If IVv u I I = 111, then N = 1 + m + 111
2 + ... + mil since m
i is the number
of strings of length i over Vv U L. i.e. N =(m"+ I - 1)/(m - 1), and N is fixed
as it depends only on 11 and m. As any string in Wi is of length at most 11,
IWi I ::;; N. Therefore, W k = W k + 1 for some k ::;; N. This proves the point (iv).
From point (ii) it follows that W k = W k + 1 implies W k + 1 = Wk+2'
{a E CVv U L)* IS :b a. Ia I ::;; n} = WI U W 2 U
U W k U lV k + 1 ...
= W 1 U W 2 U
U W k
=W k from point (iii)
This proves the point (v).