Suppose M = (0,2,5,5,A) is a DFA. For states p, q EQ (p can be same as q) argue that Lp,4 = {w | 8*(p,w) =q} is regular. Recall that PREFIX(L)={w|wx L, X 2*} is the set of all prefixes of strings in L. Express PREFIX(L(M)) as uqez Ls,q for a suitable set of states 2 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 X*}. Prove that MID(L) is regular if L is regular For a language L let SUFFIX(L)={y|3x 2*, xy EL} be the set of suffixes of strings in L. Let PSUFFIX(L)={y | 3x 3*, |x| 21,xy E 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,3,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 E= {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 e describe a regular expression for PSUFFIX(L(r)). ii. Suppose ry and r2 are regular expressions, and rand rare 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,12,11,7- iii. Same as the previous part but now consider L(rr). iv. Same as the previous part but now consider L((r)*). 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 = (0,2,5,5,A) is a DFA. For states p, q EQ (p can be same as q) argue that Lp,4 = {w | 8*(p,w) =q} is regular. Recall that PREFIX(L)={w|wx L, X 2*} is the set of all prefixes of strings in L. Express PREFIX(L(M)) as uqez Ls,q for a suitable set of states 2 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 X*}. Prove that MID(L) is regular if L is regular For a language L let SUFFIX(L)={y|3x 2*, xy EL} be the set of suffixes of strings in L. Let PSUFFIX(L)={y | 3x 3*, |x| 21,xy E 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,3,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 E= {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 e describe a regular expression for PSUFFIX(L(r)). ii. Suppose ry and r2 are regular expressions, and rand rare 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,12,11,7- iii. Same as the previous part but now consider L(rr). iv. Same as the previous part but now consider L((r)*). v. Apply your construction to the regular expression r = 0* +(01)* +011*0 to obtain a regular expression for the language PSUFFIX(L(r))
