For a language L * and a string y *, the language L_y = {xz :...

   

Transcribed Image Text:

For a language L * and a string y *, the language L_y = {xz : x * and z * and xyz L} consists of all strings in L with the string y deleted from them. (a) Prove that if L is regular, then L-y is regular. Hint: make |y| + 1 copies of a DFA recognizing L. (b) Prove that if L is R.E., then L-y is R.E. For a language L * and a string y *, the language L_y = {xz : x * and z * and xyz L} consists of all strings in L with the string y deleted from them. (a) Prove that if L is regular, then L-y is regular. Hint: make |y| + 1 copies of a DFA recognizing L. (b) Prove that if L is R.E., then L-y is R.E.