156 CONTEXT-FREE LANGUAGES
(3) for any n > 0, uvnxynz E L.- For each of the following languages, determine whether it is context-free,
and present a proof for your answer.
(a) {aibkk 1 i < j < k}.
(b) {uitick.. 1 i # j,j # k, k # i}.
(c) {u”bJc” 1 i < j or k < j}.
(d) {ui@ck 1 i < j and k < j}.
(e) {aibhk 1 i < j 3 k < j}.
(f) {uitick I i < j H k < j}.
(g) {uib%w 1 i,j > 0).
(h) {uibjcidj I ;,j > 0).
(i) {u%Wdi I ;,j > 0). -- In the following, consider each binary string in A = l(0 + l)* + 0 as
a binary representation of a natural number. For each of the following
languages, determine whether it is context-free, and present a proof for
your answer.
( > a
v4
( > CCd)
( > e(f)
(4
P-4{X#Y I x:, Y E 4 x = Y + 3).
{x#yR 1 x:, y E A, x = y + 3).
{X#Y I X:Y E Ax = 3~). [Hint: Consider a string y = lKOK,
where Ii’ is the constant of the pumping lemma.]
{X#YR I XxtY E Ax = 3Y)*
{X#Y#Z lX,Y,Z =4x= y + z}. [Hint: Use the closure property
to reduce this problem to (a) above.]
{x#yR#zR 1 x, y, z E A, x = y + x).
{X#Y#Z I x7 Y, x E A 2 = Y l 4
{x#yR#zR ( x, y, z E A, x = y l x}.
*4. For each of the following lang
and present a proof for youruages,
answedetermine whether it is context-free,
r.(a) {xyx I xx = y for some x, y,x E (0, l}*}. [Hint: Consider
the intersection of this language with the regular language
10100+11+10100+11+. Note that then y must begin with 101.1
(b) {xyz I x:x = yR for some x, y, 2 E {O,l}*}.
(c) {xyz 1 x:x = yx for some x, y, 2 E {O,l}*}.
(4 { xxRwwR 1 x, w E {o,1}*}.
(4 -i xwxRwR 1 x, w E {O,l}“}.
(f) 1 xwwRxR 1 x, w E {o,1}*}.- Recall that #a(x) d enotes the number of occurrences of the letter a in
string x. For each of the following languages, determine whether it is
context-free, and present a proof for your answer.