# 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.

Could you please help me with that?

Thanks in advance!

-
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
add comment

## 1 Answer

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.

-
add comment