Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The right quotient of two languages is defined as

$$L_1/L_2=\{ x \mid xy \in L_1 \text{ and } y \in L_2 \}.$$

$L_1=\{ab,aab,baa\}$ and $L_2=\{b\}.$

I read somewhere that $L_1/L_2=\{a,aa,\varepsilon\}$ but I cannot understand why $\varepsilon$ is contained in the quotient.

share|cite|improve this question
$\varepsilon$ is not in $L_1/L_2$. – A.Schulz Dec 7 '12 at 17:28
I see that my title edit was not perfect, but it was likely too nondescriptive to begin with. Perhaps we need to include a proper question in the post too? – The Unfun Cat Dec 7 '12 at 17:36

In words, your definition says "The right quotient, written $L_1 / L_2$, is defined to be the set of all strings $x$ such that $xy$ is a string in $L_1$ for some string $y$ in $L_2$." According to this definition, the empty string is a member of the right quotient if and only if there is a common string in the two languages. In symbols, $\epsilon \in L_1 / L_2 \iff L_1 \cap L_2 \neq \emptyset$. In particular, this is not the case in your example, hence, the empty string is not in your right quotient.

share|cite|improve this answer
simply awesome answer. thanks a lot – user1771809 Dec 7 '12 at 18:10

Your Answer


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.