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!

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jun 6, 2012 at 20:06
  • $\begingroup$ The answers to this question might be helpful. $\endgroup$ Commented Jun 7, 2012 at 11:24

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.