Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.