4
$\begingroup$

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!

  • 0
    The answers to [this question](http://cs.stackexchange.com/q/1886/98) might be helpful.2012-06-07

1 Answers 1

4

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.