Prove that whenever L is a regular language so is HasPrefix(L)

132 Views Asked by At

For a language $L$ over an alphabet $\Sigma$, define the language $\operatorname{HasPrefix}(L)$ as follows: $$\operatorname{HasPrefix}(L) = \{xy\mid x,y \in\Sigma^*, x \in L, xy \in L, |y|> 0\}$$ Note the last condition, which requires that y be nonempty.

I want to prove that if $L$ is regular, then so is $\operatorname{HasPrefix}(L)$.

Any suggestions on how to approach this? I want to prove it by making DFAs for the language L and HasPrefix(L) to show that they're both regular.