Please do part b

Suppose M = (Q, 2,5,5,A) is a DFA. For states p,q EQ (p can be same as q) argue that Lpq = {w | 8*(p, w) =q} is regular. Recall that PREFIX(L) = {w|wx Lx 2*} is the set of all prefixes of strings in L. Express PREFIX(L(M)) as UgezLs,q for a suitable set of states Z SQ. Why does this prove that PREFIX(L(M)) is regular whenever L is regular? For a language L let MID(L)={w|xwy L,x,y 2*}. Prove that MID(L) is regular if L is regular For a language L let SUFFIX(L)={y|3x 3*, xy L} be the set of suffixes of strings in L. Let PSUFFIX(L) = {y 13x 2*, x] 2 1,xy L} be the set of proper suffixes of strings in L. (a) Prove that if L is regular then PSUFFIX(L) is regular via the following technique. Let M=(Q,2,5,5,A) be a DFA accepting L. Describe a NFA N in terms of M that accepts PSUFFIX(L). Explain the construction of your NFA. (b) Prove that if L is regular then PSUFFIX(L) is regular via the following alternate technique. Let r be a regular expression. We will develop an algorithm that given r constructs a regular expression r' such that l(r') = PSUFFIX(L(r)). Assume = {0,1). No correctness proof is required but a brief explanation of the derivation would help you get partial credit in case of mistakes. i. For each of the base cases of regular expressions 0,e and {a}, a describe a regular expression for PSUFFIX(L(r)). ii. Suppose ry and r2 are regular expressions, and r and r'a are regular expressions for the languages PSUFFIX(L(r)) and PSUFFIX(L(r2)) respectively. Describe a regular expression for the language PSUFFIX(L(r +r2)) using r1, 82, 81, r. iii. Same as the previous part but now consider L(rr2). iv. Same as the previous part but now consider L((11)*). v. Apply your construction to the regular expression r = 0* +(01)* +011*0 to obtain a regular expression for the language PSUFFIX(L(r)). Suppose M = (Q, 2,5,5,A) is a DFA. For states p,q EQ (p can be same as q) argue that Lpq = {w | 8*(p, w) =q} is regular. Recall that PREFIX(L) = {w|wx Lx 2*} is the set of all prefixes of strings in L. Express PREFIX(L(M)) as UgezLs,q for a suitable set of states Z SQ. Why does this prove that PREFIX(L(M)) is regular whenever L is regular? For a language L let MID(L)={w|xwy L,x,y 2*}. Prove that MID(L) is regular if L is regular For a language L let SUFFIX(L)={y|3x 3*, xy L} be the set of suffixes of strings in L. Let PSUFFIX(L) = {y 13x 2*, x] 2 1,xy L} be the set of proper suffixes of strings in L. (a) Prove that if L is regular then PSUFFIX(L) is regular via the following technique. Let M=(Q,2,5,5,A) be a DFA accepting L. Describe a NFA N in terms of M that accepts PSUFFIX(L). Explain the construction of your NFA. (b) Prove that if L is regular then PSUFFIX(L) is regular via the following alternate technique. Let r be a regular expression. We will develop an algorithm that given r constructs a regular expression r' such that l(r') = PSUFFIX(L(r)). Assume = {0,1). No correctness proof is required but a brief explanation of the derivation would help you get partial credit in case of mistakes. i. For each of the base cases of regular expressions 0,e and {a}, a describe a regular expression for PSUFFIX(L(r)). ii. Suppose ry and r2 are regular expressions, and r and r'a are regular expressions for the languages PSUFFIX(L(r)) and PSUFFIX(L(r2)) respectively. Describe a regular expression for the language PSUFFIX(L(r +r2)) using r1, 82, 81, r. iii. Same as the previous part but now consider L(rr2). iv. Same as the previous part but now consider L((11)*). v. Apply your construction to the regular expression r = 0* +(01)* +011*0 to obtain a regular expression for the language PSUFFIX(L(r))