# Proving that a language build from two regular languages is regular as well

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.

-
This is what is known as the quotient of M and L, written M / L. It's well-known that the quotient of a regular language and any language whatsoever is regular. You're on the right track, by the way. – Rick Decker Jun 6 '12 at 20:06
The answers to this question might be helpful. – Raphael Jun 7 '12 at 11:24

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.