Chapter 4: Formal Languages J;! 125
From the point (v) it follows that W E L(G) (i.e. S ~ w) if and only if
W E W~. Also. Wi, W 2 , •.• , W k can be constructed in a finite number of steps.
We give the required algorithm as follows:
Algorithm to test whether w E L(G). 1. Construct Wi, W 2 • ... using the
points (i) and (ii). We terminate the construction when W k +] = W k for the first
time.
2. If yi' E W k , then W E L(G). Otherwise, W E L(G). (As IW k Is N, testing
whether W is in W k requires at most N steps.)
I
EXAM PlE 4.18
Consider the grammar G given by S ~ OSA]2. S ~ 012, 2A) ~ A]2,
lA] ~ 11. Test whether (a) 00112 E L(G) and (b) 001122 E L(G).
Solution
(a) To test whether w =00112 E L(G), we construct the sets W o , WI, W 2
etc. Iwl = 5.
W o = {S}
W] = {012, S, OSA]2}
Wo = {012, S, OSA I 2}
As W 2 = WI, we terminate. (Although OSA]2 => 0012A]2, we cannot
include 0012A]2 in W] as its length is> 5.) Then 00112 E WI' Hence,
00112 E LCG).
(b) To test whether w =001122 E L(G). Here, Iw 1= 6. We construct W o ,
WI. W 2 , etc.
W o = {S}
W] = {012. S, OSA]2}
Wo = {012, S, OSA]2, 0012A]2}
W 3 = {OIl, S. OSA]2. 0012A]2, 001A]22}
W 4 = {012. S, OSA]2, 0012A]2. 001A]22, 001122}
W 5 = {012, S. OSA]2. 0012A]2, 001A]22. 001122}
As W s = W 4 , we terminate. Then 001122 E W 4 . Thus. 001122 E L(G).
The following theorem is of theoretical interest, and shows that there
exists a recursive set over {O, I} which is not a context-sensitive language. The
proof is by the diagonalization method which is used quite often in set theory.
1 neorem 4.4 There exists a recursive set which is not a context-sensitive
language over {O, I}.
Proof Let 2: = {O, I}. We write the elements of 2:* as a sequence (i.e. the
elements of 2:* are enumerated as the first element, second element, etc.) For