Chapter 6: Context-Free Languages l;! 217
Step 3 UVH'.\j' = a"hllc ll , As 1 :s; I vx I :s; n, v or x cannot contain all the three
symbols a. h, c. So. (i) v or x is of the form aih i (or bic i ) for some i, j such that
i + j :s; n. Or (ii) v or x is a string formed by the repetition of only one symbol
among a. b, c.
When v or x is of the form ailJ, v~ = (/lJaih i (or x~ = dbi(/lJ). As v~ is a
substring of llV~WX~Y. we cannot have uv~·wx\ of the form a"'b"'c"', So,
lIv~wx~y E L
When both v and x are formed by the repetition of a single symbol (e,g,
U =a
i and v =b i for some i andj. i:S; n, j:S; n), the string IfWy will contain the
remaining symbol, say al' Also, a;' will be a substring of uwy as al does not
occur in v or x. The number of occurrences of one of the other two symbols
in lIWv is less than n (recallllvwxv =a"b"c"), and n is the number of occurrences
of a j.' So llVOWXOy = lIHy E L .
Thus for any choice of i' or x, we get a contradiction. Therefore, L is not
context-free,
EXAMPLE 6.19
Show that L = {d' Ipis a prime} is not a context-free language,
Solution
We use the following property of L: If H' E L then I W I is a pnme,
Step 1 Suppose L = UG) is context-free, Let n be the natural number
obtained by using the pumping lemma,
Step 2 Let p be a plime number greater than 11, Then:::: = al' E L. We wlite
:::: = lI1'WXV,
Step 3 By pumping lemma, llVO,LC
C
\, = lrwy E L So' luwy I is a prime
number, say q, Let I 1'X I = 1', Then, IllV'iWX'iy I = q + qr, As q + qr is not a
prime. lll''fiVX'f" E L. This is a contradiction. Therefore, L is not context-f.ree,
6.6 DECISION ALGORITHMS FOR CONTEXT-FREE
LANGUAGES
In this section we give some decision algorithms for context-ti'ee languages and
regular sets.
(i) Algorithm for deciding whether a context}ree language L is empty.
We can apply the construction given in Theorem 6.3 for getting
V;, = Wk' L is nonempty if and only if S E Wk'
tii) Algorithm for deciding whether a context-free language L is finite.
Construct a non-redundant context-free grammar G in CNF generating
L - {A}. We draw a directed graph whose vertices are variables in
G. If A --+ Be is a production. there are directed edges from A to B
and A to C L is finite if and only if the directed graph has no cycles.
Step 3 UVH'.\j' = a"hllc ll , As 1 :s; I vx I :s; n, v or x cannot contain all the three
symbols a. h, c. So. (i) v or x is of the form aih i (or bic i ) for some i, j such that
i + j :s; n. Or (ii) v or x is a string formed by the repetition of only one symbol
among a. b, c.
When v or x is of the form ailJ, v~ = (/lJaih i (or x~ = dbi(/lJ). As v~ is a
substring of llV~WX~Y. we cannot have uv~·wx\ of the form a"'b"'c"', So,
lIv~wx~y E L
When both v and x are formed by the repetition of a single symbol (e,g,
U =a
i and v =b i for some i andj. i:S; n, j:S; n), the string IfWy will contain the
remaining symbol, say al' Also, a;' will be a substring of uwy as al does not
occur in v or x. The number of occurrences of one of the other two symbols
in lIWv is less than n (recallllvwxv =a"b"c"), and n is the number of occurrences
of a j.' So llVOWXOy = lIHy E L .
Thus for any choice of i' or x, we get a contradiction. Therefore, L is not
context-free,
EXAMPLE 6.19
Show that L = {d' Ipis a prime} is not a context-free language,
Solution
We use the following property of L: If H' E L then I W I is a pnme,
Step 1 Suppose L = UG) is context-free, Let n be the natural number
obtained by using the pumping lemma,
Step 2 Let p be a plime number greater than 11, Then:::: = al' E L. We wlite
:::: = lI1'WXV,
Step 3 By pumping lemma, llVO,LC
C
\, = lrwy E L So' luwy I is a prime
number, say q, Let I 1'X I = 1', Then, IllV'iWX'iy I = q + qr, As q + qr is not a
prime. lll''fiVX'f" E L. This is a contradiction. Therefore, L is not context-f.ree,
6.6 DECISION ALGORITHMS FOR CONTEXT-FREE
LANGUAGES
In this section we give some decision algorithms for context-ti'ee languages and
regular sets.
(i) Algorithm for deciding whether a context}ree language L is empty.
We can apply the construction given in Theorem 6.3 for getting
V;, = Wk' L is nonempty if and only if S E Wk'
tii) Algorithm for deciding whether a context-free language L is finite.
Construct a non-redundant context-free grammar G in CNF generating
L - {A}. We draw a directed graph whose vertices are variables in
G. If A --+ Be is a production. there are directed edges from A to B
and A to C L is finite if and only if the directed graph has no cycles.