Let L be a regular language, $L'= \{xz \space | \space \exists y \space \in \sum^* : xyz \in L\}$ Prove that L' is regular

477 Views Asked by At

Let L be a regular language and let $M=<Q, \Sigma, \delta, s, A>$ be a DFA for L.

Consider $L'= \{xz \space | \space \exists y \space \in \Sigma^* : xyz \in L\}$

Where $x,z \in \Sigma^*$

After some thinking time we found that there is a relation between L' and $L_{Suffix} , L_{Prefix}$ but we couldn't point the exact relation between them.

Is it true that $L' = L_{Suffix} \cup L_{Prefix}$ ?

If the answer is yes, how would one prove that claim ?

Otherwise, I will be glad for some directions of proving L' is regular.

Thanks.