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.

According to wikipedia the right quotient of a regular language with ANY other language is regular. I have not been able to find a proof of this fact. All the sources talk about quotient with another regular language. Can somebody point me to a proof?

P.S. Definition from Wikipedia: The right quotient (or simply quotient) of a formal language $L_1$ with a formal language $L_2$ is the language consisting of strings $w$ such that $wx$ is in $L_1$ for some string $x$ in $L_2$. In symbols, we write: $$L_1 / L_2 = \{w \ | \ \exists x ((x \in L_2) \land (wx \in L_1)) \}$$ In other words, each string in L1 / L2 is the prefix of a string wx in L1, with the remainder of the word being a string in L2.

share|improve this question
    
It suffices to show that the set of strings in L_2 which can be suffices of strings in L_1 is regular. This seems plausible, though I'm not sure how to prove it. –  Qiaochu Yuan Dec 10 '10 at 7:29

1 Answer 1

up vote 3 down vote accepted

You can find a proof in this book: Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman, 1979 edition.

The short and non-constructive proof appears on page 63.

Here is a snapshot (which I got from google books by searching for quotient in that book):

alt text

Only the last line of the proof is incomplete in the above snapshot, which reads:

Thus $M'$ accepts $R/L$.

Here $R$ is a regular language and $L$ is an arbitrary language.

share|improve this answer

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.