Let $L, M \subseteq \Sigma^*$ be regular languages. I need to prove that $$N = \{x \in \Sigma^* \; | \; \exists y \in L : xy \in M\}$$ is as well a regular language.
My favored approach is to find a finite state machine that recognizes that language. I thought about the FSM that recognizes M and $\lambda$-transitions to the FSM of $L$, but this didn't help me on it. I don't know how to integrate the recognition of $L$ to each step of $M$ and am stuck.
Could you please help me with that?
Thanks in advance!
Take a state machine for $M$. Given a state $\alpha$ in that machine, we can say that $\alpha$ is $L$-complete if, for some string $y\in L$, starting at $\alpha$, yields a successful match.
Now, create a new machine that uses the same state machine as $M$, but that register a "match" only at the $L$-complete nodes.
You don't really need to know how to figure out which nodes are $L$-complete, you know just that they are some subset of the state nodes.
This is a non-constructive solution, in that it does not show you how to determine the $L$-complete nodes, so you cannot use this argument to make the machine for $N$ out of known machines for $L$ and $M$.
Indeed, this proof doesn't appear to need $L$ to be regular.