Answer Happy

Problem 3 : [10 points] [Regular Languages + Context Free Languages] Given a language L S {0,1}*, CUT(L) is defined as the language CUT(L) = {yx | € {0,1}*, y € {0,1}* and xy EL }. Notice that I and y are strings in {0,1}* (and hence possibly e). Therefore if w = 0011 € L, by cutting and rearranging w at different positions in the strings, we get that all the following strings 0011 (1 = E), 0110 (1 = 0), 1100 (1 = 00), 1001 (1 = 001), and 0011 (1 = 0011) belong to CUT(L). (a) Given the context free language B = {0"1" n >0}, describe precisely using set notation, what CUT(B) is. [4 points] (b) Show that CUT(B) is context free by giving the PDA or by giving the context free grammar for it. [4 points) Hint: Count the number of Os and is in the strings in CUT(B).
= (©) Given the regular language A = L(1*0*1*), describe precisely using set notation, what CUT(A) is. [2 points)