Problem Solving in Automata, Languages, and Complexity

3.6 Pumping Lemmas for Context-Free Languages 157

* 6. Show that the language {uibjc”de ( [i = j, k = !] or [; = !,j = k]} is

inherently ambiguous.

* 7. Apply Parikh’s lemma

context-free:

to show that the following languages are not

(a) {umbn I n # am}.

(b) {u”bV I q # n-m}. [Hint: Use the approach of Example 3.58.

First prove that there must be a triple (O,O, r) in one of the gen-

erating set Ii.1

(c) {umbncQ 1 q2 # r-n3 or q2 # n3}.

8. Let (x)~ denote the string obtained from binary string x by changing 0
   to 1 and 1 to 0. For each of the following languages, determine whether
   it is context-free, and present a proof for your answer.

(a> -w+ I x (5 {0,1)*)*

(b) {w E {O,l}* 1 w # x(x), for any x E (0, I}“}.

(4 cxc4P I x E -to7 1)*1*

(d) {w E {O,l}* 1 w # x(x): for any x E {O,l}*}.

9. (a) Recall the language operation @ defined in Exercise 2 of Section

2.6. Show that context-free languages are not closed under the

operation $.

(b) Show that context-free languages are not closed under the oper-

ation MIN (L) = {x E L I x does not have a proper prefix in

L).

* (c) Consider operation REV(L) = {xy% I xyx E L} and language

L = (0” l”0” 1” I m, n > 0). Show that L is a context-free

language, but REV(L) is nit.

* (d) Find a context-free language L such that L 1 = {x I (3~) 1x1 =

(y] and xy E L} is not a context-free language.

• 
  
  
  
  10. Assume that L
      ing statements:
  
  
  
  

is a context-free language. Prove or disprove the follow-

(a) If L1 is regular, then L1 \ L is context-free.

(b) {x I xxR E L} is context-free.

(c) {xxR ( x E L or xR E L} is context-free.