4
$\begingroup$

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.

  • 0
    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.2010-12-10

1 Answers 1

4

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.

  • 0
    But, how can we determine wether exists such $y\in L$ or not? What if L is undecidable for example?2015-03-18
  • 1
    @AstroNauft: You don't need to determine anything. It is a non-constructive proof. $L$ could be any language.2015-03-18