Part 1 (12.5 points) D = {0,1,2,3,5}, V = {a,e,i,o,u}, C = {d,f,g,h,j}, ? = D ? V ? C, and L = { w : #D(w)

Use the CF pumping theorem, and the fact that the CFLs are closed under intersection with a regular language, to show that L ? CFLs. When using the CF pumping theorem, express w in terms of the symbols in ?, not in terms of the D, V, and C subsets. You may also find it helpful to divide w into regions and use the shorthand notation for v and y. (m,n) means that v is entirely within region m and y is entirely within region n; it does not necessarily mean that vxy extends from region m into region n. (m,m) means that vxy is entirely contained in region m, and either v or y could be ?, but not both.

Part 2 (12.5 points) Write a characteristic function for the language accepted by the TM represented in the macro language diagram below. Do not give details of the TM's operation, such as traversing the tape looking for a particular symbol. ? = {a,b}, ? = {a,b,#,$,?}, H= {y,n}, and the characteristic function can define any language over ?. Note that the characteristic function should not mention $ or #, because those symbols are not in ?.

CSC 520 HW #3 Part 1 (12.5 points) D = {0,1,2,3,5), V = {a,e, i,o,u), C = {a,f,g,h, j), ? = Du Vu C, and L = { w : #o(w) y y